Priority queues

Discussion in 'C Programming' started by jacob navia, Apr 30, 2012.

  1. jacob navia

    jacob navia Guest

    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
     
    jacob navia, Apr 30, 2012
    #1
    1. Advertising

  2. jacob navia

    Joe keane Guest

    In article <jnl98c$6hk$>,
    jacob navia <> wrote:
    >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'.
     
    Joe keane, May 1, 2012
    #2
    1. Advertising

  3. jacob navia

    Ian Collins Guest

    On 04/30/12 05:51 PM, jacob navia wrote:
    > 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.

    --
    Ian Collins
     
    Ian Collins, May 1, 2012
    #3
  4. jacob navia

    jacob navia Guest

    Le 01/05/12 01:50, Joe keane a écrit :
    > In article<jnl98c$6hk$>,
    > jacob navia<> wrote:
    >> 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
     
    jacob navia, May 2, 2012
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Der Andere
    Replies:
    6
    Views:
    624
    Dietmar Kuehl
    Jun 5, 2004
  2. Der Andere

    Still priority queues and STL ...

    Der Andere, Jun 4, 2004, in forum: C++
    Replies:
    1
    Views:
    380
    David Harmon
    Jun 4, 2004
  3. Replies:
    0
    Views:
    292
  4. Delaney, Timothy C (Timothy)

    RE: On benchmarks, heaps, priority queues

    Delaney, Timothy C (Timothy), Jan 26, 2005, in forum: Python
    Replies:
    6
    Views:
    405
  5. Mason Kelsey
    Replies:
    7
    Views:
    382
    Josh Cheek
    Sep 21, 2009
Loading...

Share This Page