Browse Prior Art Database

Hybrid finite-queue / circular queue data structure

IP.com Disclosure Number: IPCOM000015286D
Original Publication Date: 2002-May-21
Included in the Prior Art Database: 2003-Jun-20
Document File: 1 page(s) / 37K

Publishing Venue

IBM

Abstract

Hybrid finite-queue circular queue data structure This publication describes a hybrid data structure that is a cross between a circular queue and an infinitely growable queue. The data structure starts out as an infinitely growing queue and when it reaches a certain size, it mutates into a circular queue. The total logical queue is made up of a set of fixed-size buffers. The original (and most obvious) use for this data structure was in logging events. Event logs often need to be of fixed size (because of resource limitations) and cannot grow arbitrarily large. But it is wasteful to pre-allocate the space if it is not yet in use. This data structure starts out empty and allocates space as needed (growing the buffers) up to its maximum size. Then it wraps the buffer back to the beginning. The nice part is that traversing the data structure is relatively independent of the state of the structure. In the actual application, a read routine had to traverse the structure in multiple calls. Each call had to remember the state of the traversal and continue on without knowing whether it was a growing or wrapping buffer. This proved to be surprisingly simple with this hybrid data structure. Traversing it in the circular case looks just like traversing a terminated case in which you are not at the end yet.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 89% of the total text.

Page 1 of 1

Hybrid finite-queue / circular queue data structure

This publication describes a hybrid data structure that is a cross between a circular queue and an infinitely growable queue. The data structure starts out as an infinitely growing queue and when it reaches a certain size, it mutates into a circular queue. The total logical queue is made up of a set of fixed-size buffers.

The original (and most obvious) use for this data structure was in logging events. Event logs often need to be of fixed size (because of resource limitations) and cannot grow arbitrarily large. But it is wasteful to pre-allocate the space if it is not yet in use. This data structure starts out empty and allocates space as needed (growing the buffers) up to its maximum size. Then it wraps the buffer back to the beginning.

The nice part is that traversing the data structure is relatively independent of the state of the structure. In the actual application, a read routine had to traverse the structure in multiple calls. Each call had to remember the state of the traversal and continue on without knowing whether it was a growing or wrapping buffer. This proved to be surprisingly simple with this hybrid data structure. Traversing it in the circular case looks just like traversing a terminated case in which you are not at the end yet.

struct Node* getNext(struct Node* cur) {


struct Node* p;

if (cur->next!=NULL) { p = kmalloc (sizeof(struct Node), GFP_KERNEL);

p = NULL;

}

return p;

}

The routine trave...