X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?a=blobdiff_plain;f=src%2Fbasic%2Fprioq.c;h=4570b8e4baab44afa49ef667257833be54568fde;hb=f082899f180431f04553e4ee3b0968020ef59188;hp=b89888be0e8d5460313ffc3e9712856f214ce5d2;hpb=1cfc78c91965df340cdde100ad6cb3ed50b28927;p=elogind.git
diff --git a/src/basic/prioq.c b/src/basic/prioq.c
index b89888be0..4570b8e4b 100644
--- a/src/basic/prioq.c
+++ b/src/basic/prioq.c
@@ -1,5 +1,3 @@
-/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
-
/***
This file is part of systemd.
@@ -19,7 +17,21 @@
along with systemd; If not, see .
***/
-#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
+#include
+
+#include "alloc-util.h"
+#include "hashmap.h"
#include "prioq.h"
struct prioq_item {
@@ -50,9 +62,7 @@ Prioq* prioq_free(Prioq *q) {
return NULL;
free(q->items);
- free(q);
-
- return NULL;
+ return mfree(q);
}
int prioq_ensure_allocated(Prioq **q, compare_func_t compare_func) {
@@ -101,7 +111,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);