diff options
Diffstat (limited to 'src/libnm-glib-aux/nm-prioq.c')
| -rw-r--r-- | src/libnm-glib-aux/nm-prioq.c | 192 |
1 files changed, 136 insertions, 56 deletions
diff --git a/src/libnm-glib-aux/nm-prioq.c b/src/libnm-glib-aux/nm-prioq.c index 3448dcd9..e74b2b99 100644 --- a/src/libnm-glib-aux/nm-prioq.c +++ b/src/libnm-glib-aux/nm-prioq.c @@ -16,15 +16,38 @@ #include "nm-prioq.h" -#include <errno.h> -#include <stdlib.h> - /*****************************************************************************/ -struct _NMPrioqItem { +typedef struct _NMPrioqItem { void *data; unsigned *idx; -}; +} PrioqItem; + +/*****************************************************************************/ + +#define _nm_assert_q(q) \ + G_STMT_START \ + { \ + const NMPrioq *const _q2 = (q); \ + \ + nm_assert(_q2); \ + nm_assert(_q2->_priv.n_items == 0 || _q2->_priv.items); \ + nm_assert(_q2->_priv.compare_func); \ + } \ + G_STMT_END + +#define _nm_assert_item(q, item) \ + G_STMT_START \ + { \ + const NMPrioq *const _q = (q); \ + const PrioqItem *const _item = (item); \ + \ + _nm_assert_q(_q); \ + \ + nm_assert(_item >= _q->_priv.items); \ + nm_assert(_item < &_q->_priv.items[_q->_priv.n_items]); \ + } \ + G_STMT_END /*****************************************************************************/ @@ -72,6 +95,15 @@ nm_prioq_destroy(NMPrioq *q) if (!q || !q->_priv.compare_func) return; + _nm_assert_q(q); + + while (q->_priv.n_items > 0) { + PrioqItem *i = &q->_priv.items[--q->_priv.n_items]; + + if (i->idx) + *i->idx = NM_PRIOQ_IDX_NULL; + } + free(q->_priv.items); q->_priv.compare_func = NULL; } @@ -81,8 +113,7 @@ nm_prioq_destroy(NMPrioq *q) static int compare(NMPrioq *q, unsigned a, unsigned b) { - nm_assert(q); - nm_assert(q->_priv.compare_func); + _nm_assert_q(q); nm_assert(a != b); nm_assert(a < q->_priv.n_items); nm_assert(b < q->_priv.n_items); @@ -99,15 +130,13 @@ compare(NMPrioq *q, unsigned a, unsigned b) static void swap(NMPrioq *q, unsigned j, unsigned k) { - nm_assert(q); + _nm_assert_q(q); nm_assert(j < q->_priv.n_items); nm_assert(k < q->_priv.n_items); - nm_assert(!q->_priv.items[j].idx || *(q->_priv.items[j].idx) == j); nm_assert(!q->_priv.items[k].idx || *(q->_priv.items[k].idx) == k); - NM_SWAP(&q->_priv.items[j].data, &q->_priv.items[k].data); - NM_SWAP(&q->_priv.items[j].idx, &q->_priv.items[k].idx); + NM_SWAP(&q->_priv.items[j], &q->_priv.items[k]); if (q->_priv.items[j].idx) *q->_priv.items[j].idx = j; @@ -119,7 +148,7 @@ swap(NMPrioq *q, unsigned j, unsigned k) static unsigned shuffle_up(NMPrioq *q, unsigned idx) { - nm_assert(q); + _nm_assert_q(q); nm_assert(idx < q->_priv.n_items); while (idx > 0) { @@ -140,7 +169,7 @@ shuffle_up(NMPrioq *q, unsigned idx) static unsigned shuffle_down(NMPrioq *q, unsigned idx) { - nm_assert(q); + _nm_assert_q(q); for (;;) { unsigned j; @@ -184,19 +213,21 @@ nm_prioq_put(NMPrioq *q, void *data, unsigned *idx) { unsigned k; - nm_assert(q); + _nm_assert_q(q); + nm_assert(q->_priv.n_items < G_MAXUINT); - if (q->_priv.n_items >= q->_priv.n_allocated) { + if (G_UNLIKELY(q->_priv.n_items >= q->_priv.n_allocated)) { q->_priv.n_allocated = NM_MAX((q->_priv.n_items + 1u) * 2u, 16u); - q->_priv.items = g_renew(struct _NMPrioqItem, q->_priv.items, q->_priv.n_allocated); + q->_priv.items = g_renew(PrioqItem, q->_priv.items, q->_priv.n_allocated); } k = q->_priv.n_items++; - q->_priv.items[k] = (struct _NMPrioqItem){ + q->_priv.items[k] = (PrioqItem){ .data = data, .idx = idx, }; + if (idx) *idx = k; @@ -204,71 +235,88 @@ nm_prioq_put(NMPrioq *q, void *data, unsigned *idx) } static void -remove_item(NMPrioq *q, struct _NMPrioqItem *i) +remove_item(NMPrioq *q, PrioqItem *i) { - struct _NMPrioqItem *l; - unsigned k; + PrioqItem *l; + unsigned k; - nm_assert(q); - nm_assert(i); - nm_assert(q->_priv.n_items > 0); - nm_assert(i >= q->_priv.items); - nm_assert(i < &q->_priv.items[q->_priv.n_items]); + _nm_assert_item(q, i); - l = &q->_priv.items[q->_priv.n_items - 1u]; + if (i->idx) + *i->idx = NM_PRIOQ_IDX_NULL; + + q->_priv.n_items--; + + l = &q->_priv.items[q->_priv.n_items]; if (i == l) { - /* Last entry, let's just remove it */ - q->_priv.n_items--; + /* Last entry, nothing to do. */ return; } - /* Not last entry, let's replace the last entry with - * this one, and reshuffle */ + /* Not last entry, let's replace this entry with the last one, and + * reshuffle */ + k = i - q->_priv.items; *i = *l; + if (i->idx) *i->idx = k; - q->_priv.n_items--; k = shuffle_down(q, k); shuffle_up(q, k); } -_nm_pure static struct _NMPrioqItem * +static PrioqItem * find_item(NMPrioq *q, void *data, unsigned *idx) { - struct _NMPrioqItem *i; - - nm_assert(q); + PrioqItem *i; - if (q->_priv.n_items <= 0) - return NULL; + _nm_assert_q(q); - if (idx) { - if (*idx == NM_PRIOQ_IDX_NULL || *idx >= q->_priv.n_items) - return NULL; - - i = &q->_priv.items[*idx]; - if (i->data == data) - return i; - } else { + if (G_UNLIKELY(!idx)) { + /* We allow using NMPrioq without "idx". In that case, it does a linear + * search for the data. */ for (i = q->_priv.items; i < &q->_priv.items[q->_priv.n_items]; i++) { if (i->data == data) return i; } + return NULL; } - return NULL; + /* If the user however provides an "idx" pointer, then we assert that it is + * consistent. That is, if data is not in the queue, then we require that + * "*idx" is NM_PRIOQ_IDX_NULL, and otherwise we require that we really + * find "data" at index "*idx". + * + * This means, when the user calls nm_prioq_{remove,update,reshuffle}() + * with an "idx", then they must make sure that the index is consistent. + * Usually this means they are required to initialize the index to + * NM_PRIOQ_IDX_NULL while the data is not in the heap. + * + * This is done to assert more, and requires a stricter usage of the API + * (in the hope to find misuses of the index). */ + + if (*idx >= q->_priv.n_items) { + nm_assert(*idx == NM_PRIOQ_IDX_NULL); + return NULL; + } + + i = &q->_priv.items[*idx]; + + if (i->data != data) + return nm_assert_unreachable_val(NULL); + + return i; } gboolean nm_prioq_remove(NMPrioq *q, void *data, unsigned *idx) { - struct _NMPrioqItem *i; + PrioqItem *i; - nm_assert(q); + _nm_assert_q(q); i = find_item(q, data, idx); if (!i) @@ -278,28 +326,60 @@ nm_prioq_remove(NMPrioq *q, void *data, unsigned *idx) return TRUE; } +static void +reshuffle_item(NMPrioq *q, PrioqItem *i) +{ + unsigned k; + + _nm_assert_item(q, i); + + k = i - q->_priv.items; + k = shuffle_down(q, k); + shuffle_up(q, k); +} + gboolean nm_prioq_reshuffle(NMPrioq *q, void *data, unsigned *idx) { - struct _NMPrioqItem *i; - unsigned k; + PrioqItem *i; - nm_assert(q); + _nm_assert_q(q); i = find_item(q, data, idx); if (!i) return FALSE; - k = i - q->_priv.items; - k = shuffle_down(q, k); - shuffle_up(q, k); + reshuffle_item(q, i); return TRUE; } +void +nm_prioq_update(NMPrioq *q, void *data, unsigned *idx, bool queued /* or else remove */) +{ + PrioqItem *i; + + _nm_assert_q(q); + + i = find_item(q, data, idx); + + if (!i) { + if (queued) + nm_prioq_put(q, data, idx); + return; + } + + if (!queued) { + remove_item(q, i); + return; + } + + reshuffle_item(q, i); +} + void * nm_prioq_peek_by_index(NMPrioq *q, unsigned idx) { - nm_assert(q); + _nm_assert_q(q); if (idx >= q->_priv.n_items) return NULL; @@ -312,7 +392,7 @@ nm_prioq_pop(NMPrioq *q) { void *data; - nm_assert(q); + _nm_assert_q(q); if (q->_priv.n_items <= 0) return NULL; |