diff options
Diffstat (limited to 'src/basic/prioq.c')
| -rw-r--r-- | src/basic/prioq.c | 15 |
1 files changed, 13 insertions, 2 deletions
diff --git a/src/basic/prioq.c b/src/basic/prioq.c index b89888be0e..7590698911 100644 --- a/src/basic/prioq.c +++ b/src/basic/prioq.c @@ -19,8 +19,19 @@ along with systemd; If not, see <http://www.gnu.org/licenses/>. ***/ -#include "util.h" +/* + * Priority Queue + * The prioq object implements a priority queue. That is, it orders objects by + * their priority and allows O(1) access to the object with the highest + * priority. Insertion and removal are Θ(log n). Optionally, the caller can + * provide a pointer to an index which will be kept up-to-date by the prioq. + * + * The underlying algorithm used in this implementation is a Heap. + */ + +#include "alloc-util.h" #include "prioq.h" +#include "util.h" struct prioq_item { void *data; @@ -101,7 +112,7 @@ static unsigned shuffle_up(Prioq *q, unsigned idx) { k = (idx-1)/2; - if (q->compare_func(q->items[k].data, q->items[idx].data) < 0) + if (q->compare_func(q->items[k].data, q->items[idx].data) <= 0) break; swap(q, idx, k); |