priority_queue.h File Reference

A general purpose priority queue. More...

Go to the source code of this file.

## Macros

#define | PRIORITY_QUEUE_BASE_ITERATE(pq, idx, data, iter_count, iter_depth)
| Utility macro to simplify common case of iterating over a priority queue.

## Functions

struct priority_queue * | priority_queue_create (int init_capacity)
| Create a new priority queue.
int | priority_queue_size (struct priority_queue *pq)
| Count the elements in a priority queue.
int | priority_queue_push (struct priority_queue *pq, void *data, double priority)
| Push an element into a priority queue.
void * | priority_queue_pop (struct priority_queue *pq)
| Pop the element with the highest priority from a priority queue.
void * | priority_queue_peek_top (struct priority_queue *pq)
| Get the element with the highest priority from a priority queue.
void * | priority_queue_peek_at (struct priority_queue *pq, int index)
| Get an element from a priority queue by a specified index.
double | priority_queue_get_priority_at (struct priority_queue *pq, int index)
| Get the priority of an element at a specified index.
double | priority_queue_get_top_priority (struct priority_queue *pq)
| Get the priority of the top element in a priority queue.
int | priority_queue_update_priority (struct priority_queue *pq, void *data, double new_priority)
| Update the priority of an element in a priority queue.
int | priority_queue_find_idx (struct priority_queue *pq, void *data)
| Find the index of an element in a priority queue.
int | priority_queue_static_next (struct priority_queue *pq)
| Advance the static_cursor to the next element and return the index.
void | priority_queue_base_reset (struct priority_queue *pq)
| Reset the base_cursor to 0.
int | priority_queue_base_next (struct priority_queue *pq)
| Advance the base_cursor to the next element and return the index.
void | priority_queue_rotate_reset (struct priority_queue *pq)
| Reset the rotate_cursor to 0.
int | priority_queue_rotate_next (struct priority_queue *pq)
| Advance the rotate_cursor to the next element and return the index.
int | priority_queue_remove (struct priority_queue *pq, int idx)
| Remove the element with the specified index from a priority queue.
void | priority_queue_delete (struct priority_queue *pq)
| Delete a priority queue.

## Detailed Description

A general purpose priority queue.

This priority queue module is implemented as a complete binary heap that manages elements with associated priorities. Each element in the priority queue has a priority, and the queue ensures that the element with the highest priority can be accessed in constant time.

Operation complexity:

- Create: O(n)
- Push: O(log n)
- Pop: O(log n)
- Get head: O(1)
- Get element: O(1)
- Get max priority: O(1)
- Get min priority: O(n)
- Remove element: O(log n)

If all elements have the same priority, the priority queue behaves differently from a standard queue or stack. For example, a priority has elements with (priority, data) tuples [(1, "a"), (1, "b"), (1, "c"), (1, "d"), (1, "e")] When the first time to pop, the last element "e" will take over the top of the heap and the sink operation is applied. The contents are - [(1, "e"), (1, "b"), (1, "c"), (1, "d")] Then, the second time to pop, the last element "d" will take over as the top and he contents are - [(1, "d"), (1, "b"), (1, "c")] Similarly, the third time to pop - [(1, "c"), (1, "b")] The fourth - [(1, "b")] As seen, after the first element is popped, the access order is reversed from the input order.

When the elements have different priorities, the index order is not the same as the priority order. For example, a priority is created with elements with (priority, data) tuples (1, "a") (2, "b") (3, "c") (4, "d") (5, "e") The order of elements are determined by priority_queue_push. The first time to push, the contents are - [(1, "a")] The second time to push, the priority of the root is less than the new element, the swim operation is applied to the new element - [(2, "b"), (1, "a")] The third time - [(3, "c"), (1, "a"), (2, "b")] The fourth time - [(4, "d"), (3, "c"), (2, "b"), (1, "a")] The fifth time - [(5, "e"), (4, "d"), (2, "b"), (1, "a"), (3, "c")] As seen, the iteration order of elements is not the same as the priority order.

An example to create a priority queue and manipulate its elements:

    struct priority_queue *pq;
    pq = priority_queue_create(10);

    int priority = 5;
    void *data = someDataPointer;

    priority_queue_push(pq, data, priority);
    data = priority_queue_pop(pq);
    void *headData = priority_queue_peek_top(pq);

To list all of the items in a priority queue, use a simple loop:

    for (int i = 0; i < priority_queue_size(pq); i++) {
        void *data = priority_queue_peek_at(pq, i);
        printf("Priority queue contains: %p\n", data);
    }

Or use the PRIORITY_QUEUE_BASE_ITERATE macro:

    int idx;
    void *data;
    int iter_count = 0;
    int iter_depth = priority_queue_size(q->ready_tasks);
    PRIORITY_QUEUE_BASE_ITERATE (pq, idx, data, iter_count, iter_depth) {
        printf("Data idx: %d\n", idx);
    }

## Macro Definition Documentation

## PRIORITY_QUEUE_BASE_ITERATE

#define PRIORITY_QUEUE_BASE_ITERATE | ( |  | pq,
|  |  | idx,
|  |  | data,
|  |  | iter_count,
|  |  | iter_depth )

Value:
iter_count = 0; \
priority_queue_base_reset(pq); \
while ((iter_count < iter_depth) && ((idx = priority_queue_base_next(pq)) >= 0) && (data = priority_queue_peek_at(pq, idx)) && (iter_count += 1))
priority_queue_base_next
int priority_queue_base_next(struct priority_queue *pq)
Advance the base_cursor to the next element and return the index.
priority_queue_peek_at
void * priority_queue_peek_at(struct priority_queue *pq, int index)
Get an element from a priority queue by a specified index.

Utility macro to simplify common case of iterating over a priority queue.

Use as follows:

    int idx;
    char *data;

    int iter_count = 0;
    int iter_depth = priority_queue_size(q->ready_tasks);

    PRIORITY_QUEUE_BASE_ITERATE(pq, idx, data, iter_count, iter_depth) {
            printf("Data idx: %d\n", idx);
    }

    int iter_count = 0;
    int iter_depth = 4;
    PRIORITY_QUEUE_STATIC_ITERATE( pq, idx, data, iter_count, iter_depth ) {
        printf("Has accessed %d of %d elements\n", iter_count, iter_depth);
        printf("Data idx: %d\n", idx);
    }

    iter_count = 0;
    iter_depth = 7;
    PRIORITY_QUEUE_ROTATE_ITERATE( pq, idx, data, iter_count, iter_depth ) {
        printf("Has accessed %d of %d elements\n", iter_count, iter_depth);
        printf("Data idx: %d\n", idx);
    }

## Function Documentation

## priority_queue_create()

struct priority_queue * priority_queue_create | ( | int | init_capacity | ) |

Create a new priority queue.

Element with a higher priority is at the top of the heap.

Parameters

  init_capacity | The initial number of elements in the queue. If zero, a default value will be used.

Returns
  A pointer to a new priority queue.

## priority_queue_size()

int priority_queue_size | ( | struct priority_queue * | pq | ) |

Count the elements in a priority queue.

Parameters

  pq | A pointer to a priority queue.

Returns
  The number of elements in the queue.

## priority_queue_push()

int priority_queue_push | ( | struct priority_queue * | pq,
|  | void * | data,
|  | double | priority )

Push an element into a priority queue.

The standard push operation. New elements are placed lower than existing elements of the same priority

Parameters

  pq | A pointer to a priority queue.
  data | A pointer to store in the queue.
  priority | The specified priority with the given object.

Returns
  The idex of data if the push succeeded, -1 on failure.

## priority_queue_pop()

void * priority_queue_pop | ( | struct priority_queue * | pq | ) |

Pop the element with the highest priority from a priority queue.

Parameters

  pq | A pointer to a priority queue.

Returns
  The pointer to the top of the queue if any, failure otherwise.

## priority_queue_peek_top()

void * priority_queue_peek_top | ( | struct priority_queue * | pq | ) |

Get the element with the highest priority from a priority queue.

Similar to priority_queue_pop, but the element is not removed.

Parameters

  pq | A pointer to a priority queue.

Returns
  The pointer to the top of the queue if any, failure otherwise

## priority_queue_peek_at()

void * priority_queue_peek_at | ( | struct priority_queue * | pq,
|  | int | index )

Get an element from a priority queue by a specified index.

The first accessible element is at index 0.

Parameters

  pq | A pointer to a priority queue.
  index | The index of the element to get.

Returns
  The pointer to the element if any, failure otherwise

## priority_queue_get_priority_at()

double priority_queue_get_priority_at | ( | struct priority_queue * | pq,
|  | int | index )

Get the priority of an element at a specified index.

Parameters

  pq | A pointer to a priority queue.
  index | The index of the element.

Returns
  The priority of the element if any, NAN on failure.

## priority_queue_get_top_priority()

double priority_queue_get_top_priority | ( | struct priority_queue * | pq | ) |

Get the priority of the top element in a priority queue.

Parameters

  pq | A pointer to a priority queue.

Returns
  The priority of the top element if any, NAN on failure.

## priority_queue_update_priority()

int priority_queue_update_priority | ( | struct priority_queue * | pq,
|  | void * | data,
|  | double | new_priority )

Update the priority of an element in a priority queue.

Parameters

  pq | A pointer to a priority queue.
  data | The pointer to the element to update.
  new_priority | The new priority of the element.

Returns
  The new index if the update succeeded, -1 on failure.

## priority_queue_find_idx()

int priority_queue_find_idx | ( | struct priority_queue * | pq,
|  | void * | data )

Find the index of an element in a priority queue.

Parameters

  pq | A pointer to a priority queue.
  data | The pointer to the element to find.

Returns
  The index of the element if found, -1 on failure.

## priority_queue_static_next()

int priority_queue_static_next | ( | struct priority_queue * | pq | ) |

Advance the static_cursor to the next element and return the index.

The static_cursor is used to globally iterate over the elements by sequential index. The position of the static_cursor is automatically remembered and never reset.

Parameters

  pq | A pointer to a priority queue.

Returns
  The index of the next element if any, -1 on failure.

## priority_queue_base_reset()

void priority_queue_base_reset | ( | struct priority_queue * | pq | ) |

Reset the base_cursor to 0.

The base_cursor is used in PRIORITY_QUEUE_BASE_ITERATE to iterate over the elements from the beginning.

Parameters

  pq | A pointer to a priority queue.

## priority_queue_base_next()

int priority_queue_base_next | ( | struct priority_queue * | pq | ) |

Advance the base_cursor to the next element and return the index.

Parameters

  pq | A pointer to a priority queue.

Returns
  The index of the next element if any, -1 on failure.

## priority_queue_rotate_reset()

void priority_queue_rotate_reset | ( | struct priority_queue * | pq | ) |

Reset the rotate_cursor to 0.

The rotate_cursor is used to iterate over the elements from the beginning, and reset on demand. In task scheduling, we tipically iterate over a amall number of tasks at a time. If there is no task to execute, we remember the position of the cursor and we can start from there the next time. If there are interesting events happening, we reset the cursor and start from the beginning.

Parameters

  pq | A pointer to a priority queue.

## priority_queue_rotate_next()

int priority_queue_rotate_next | ( | struct priority_queue * | pq | ) |

Advance the rotate_cursor to the next element and return the index.

Parameters

  pq | A pointer to a priority queue.

Returns
  The index of the next element if any, -1 on failure.

## priority_queue_remove()

int priority_queue_remove | ( | struct priority_queue * | pq,
|  | int | idx )

Remove the element with the specified index from a priority queue.

Parameters

  pq | A pointer to a priority queue.
  idx | The index of the element to remove.

Returns
  One if the remove succeeded, failure otherwise

## priority_queue_delete()

void priority_queue_delete | ( | struct priority_queue * | pq | ) |

Delete a priority queue.

Parameters

  pq | A pointer to a priority queue.