Priority queues

[jacob navia]

In computer science, a priority queue is an abstract data type which is
like a regular queue or stack data structure, but additionally, each
element is associated with a "priority".

Wikipedia

I have added this ADT to the containers library. I would like to discuss
with you the interface:

typedef struct _PQueue PQueue;

typedef struct tagPQueueInterface {
// Constructors
PQueue *(*Create)(size_t elementSize);
PQueue *(*CreateWithAllocator)(size_t elementSize,
ContainerMemoryManager *allocator);
// Returns the number of elements store
size_t (*Size)(PQueue *Q);
// Returns the number of bytes used
size_t (*Sizeof)(PQueue *Q);
// Adds a new element to the queue
int (*Push)(PQueue *Q,intptr_t key,void *Element);
// Erases all elements without erasing the queue
int (*Clear)(PQueue *Q);
// Destroys the queue
int (*Finalize)(PQueue *Q);
// Retrieves the element with the lowest priority
// and eliminates it from the queue. Returns the
// priority of the deleted element and its data in
// the "result" pointer
intptr_t (*Pop)(PQueue *Q,void *result);
// Retrieves the element with the lowest priority
// without erasing it from the queue
intptr_t (*Front)(PQueue *Q,void *result);
} PQueueInterface;

Note that this container doesn't have iterators, searching utility, and
other similar features. I thought that the interface should be kept to a
minimum, but I do not know if this is too small.

The type "intptr_t" is used for the key. This has several reasons:

1) Floating point comparisons are problematical
2) This type is the "bitness" of the underlying system: 32 bits in 32
bits systems, 64 bits in 64 bit systems.
3) Comparing elements of this type is very cheap.

The heap used to implement this container in the sample implementation
is the fibonacci heap.

jacob

 

[Joe keane]

typedef struct tagPQueueInterface {
// Constructors
PQueue *(*Create)(size_t elementSize);
PQueue *(*CreateWithAllocator)(size_t elementSize,
ContainerMemoryManager *allocator); [...]
// Destroys the queue
int (*Finalize)(PQueue *Q);
} PQueueInterface;

Some recent code:

--xxalloc.h
extern int xx_heap_create(int (*ualloc)(void *rock, size_t size, void **ret),
int (*ufree)(void *rock, size_t size, void *mem),
void *urock, size_t size, struct xx_heap **ret);
extern int xx_heap_delete(struct xx_heap *heap);

--xxdefault.h
#define xx_heap_create_default(SIZE, RET) \
xx_heap_create(xx_default_ualloc, xx_default_ufree, NULL, SIZE, RET)

extern int xx_default_ualloc(void *rock, size_t size, void **ret);
extern int xx_default_ufree(void *rock, size_t size, void *mem);

The latter two are simply patch cords for 'malloc' and 'free'.

 

[Ian Collins]

In computer science, a priority queue is an abstract data type which is
like a regular queue or stack data structure, but additionally, each
element is associated with a "priority".

Wikipedia

I have added this ADT to the containers library. I would like to discuss
with you the interface:

typedef struct _PQueue PQueue;

typedef struct tagPQueueInterface {
// Constructors
PQueue *(*Create)(size_t elementSize);
PQueue *(*CreateWithAllocator)(size_t elementSize,
ContainerMemoryManager *allocator);
// Returns the number of elements store
size_t (*Size)(PQueue *Q);
// Returns the number of bytes used
size_t (*Sizeof)(PQueue *Q);
// Adds a new element to the queue
int (*Push)(PQueue *Q,intptr_t key,void *Element);
// Erases all elements without erasing the queue
int (*Clear)(PQueue *Q);
// Destroys the queue
int (*Finalize)(PQueue *Q);
// Retrieves the element with the lowest priority
// and eliminates it from the queue. Returns the
// priority of the deleted element and its data in
// the "result" pointer
intptr_t (*Pop)(PQueue *Q,void *result);
// Retrieves the element with the lowest priority
// without erasing it from the queue
intptr_t (*Front)(PQueue *Q,void *result);
} PQueueInterface;

Note that this container doesn't have iterators, searching utility, and
other similar features. I thought that the interface should be kept to a
minimum, but I do not know if this is too small.

For a queue, what you have should be enough. Iterator functionality
could be implemented as free functions.

On a more general note, function and member names in the C standard
library have names beginning in lower case. From what I've seen, this
is the most common style (outside of windows?) and adopting it would be
one less objection for you to overcome.

 

[jacob navia]

Le 01/05/12 01:50, Joe keane a écrit :

typedef struct tagPQueueInterface {
// Constructors
PQueue *(*Create)(size_t elementSize);
PQueue *(*CreateWithAllocator)(size_t elementSize,
ContainerMemoryManager *allocator); [...]
// Destroys the queue
int (*Finalize)(PQueue *Q);
} PQueueInterface;

Some recent code:

--xxalloc.h
extern int xx_heap_create(int (*ualloc)(void *rock, size_t size, void **ret),
int (*ufree)(void *rock, size_t size, void *mem),
void *urock, size_t size, struct xx_heap **ret);
extern int xx_heap_delete(struct xx_heap *heap);

--xxdefault.h
#define xx_heap_create_default(SIZE, RET) \
xx_heap_create(xx_default_ualloc, xx_default_ufree, NULL, SIZE, RET)

extern int xx_default_ualloc(void *rock, size_t size, void **ret);
extern int xx_default_ufree(void *rock, size_t size, void *mem);

The latter two are simply patch cords for 'malloc' and 'free'.

I did not understand your answer. Can you explain?

I am proposing a priority queue for the containers library I am writing
in C. In that context I wanted to discuss its interface.

I do not see the relationship of your code with my message.

You can see the rest of the library and the documentation in

http://code.google.com/p/ccl/

jacob