diff options
author | Vsevolod Stakhov <vsevolod@rspamd.com> | 2023-07-26 10:49:23 +0100 |
---|---|---|
committer | Vsevolod Stakhov <vsevolod@rspamd.com> | 2023-07-26 10:49:23 +0100 |
commit | 537a7180a0d5132c11636c4fd8b1450cd99d352c (patch) | |
tree | fb9f8c84955a411bdffbd6371ea32f2716fb3687 /src/libutil/heap.c | |
parent | 5fd7a90fdaa33f52c59bdb0ca84451e5c1e22365 (diff) | |
download | rspamd-537a7180a0d5132c11636c4fd8b1450cd99d352c.tar.gz rspamd-537a7180a0d5132c11636c4fd8b1450cd99d352c.zip |
[Rework] Use clang-format to unify formatting in all sources
No meaningful changes.
Diffstat (limited to 'src/libutil/heap.c')
-rw-r--r-- | src/libutil/heap.c | 128 |
1 files changed, 63 insertions, 65 deletions
diff --git a/src/libutil/heap.c b/src/libutil/heap.c index 601eb7893..8ce70cf71 100644 --- a/src/libutil/heap.c +++ b/src/libutil/heap.c @@ -21,16 +21,18 @@ struct rspamd_min_heap { GPtrArray *ar; }; -#define __SWAP(a, b) do { \ - __typeof__(a) _a = (a); \ - __typeof__(b) _b = (b); \ - a = _b; \ - b = _a; \ -} while (0) -#define heap_swap(h,e1,e2) do { \ - __SWAP((h)->ar->pdata[(e1)->idx - 1], (h)->ar->pdata[(e2)->idx - 1]); \ - __SWAP((e1)->idx, (e2)->idx); \ -} while (0) +#define __SWAP(a, b) \ + do { \ + __typeof__(a) _a = (a); \ + __typeof__(b) _b = (b); \ + a = _b; \ + b = _a; \ + } while (0) +#define heap_swap(h, e1, e2) \ + do { \ + __SWAP((h)->ar->pdata[(e1)->idx - 1], (h)->ar->pdata[(e2)->idx - 1]); \ + __SWAP((e1)->idx, (e2)->idx); \ + } while (0) #define min_elt(e1, e2) ((e1)->pri <= (e2)->pri ? (e1) : (e2)) @@ -38,16 +40,16 @@ struct rspamd_min_heap { * Swims element added (or changed) to preserve heap's invariant */ static void -rspamd_min_heap_swim (struct rspamd_min_heap *heap, - struct rspamd_min_heap_elt *elt) +rspamd_min_heap_swim(struct rspamd_min_heap *heap, + struct rspamd_min_heap_elt *elt) { struct rspamd_min_heap_elt *parent; while (elt->idx > 1) { - parent = g_ptr_array_index (heap->ar, elt->idx / 2 - 1); + parent = g_ptr_array_index(heap->ar, elt->idx / 2 - 1); if (parent->pri > elt->pri) { - heap_swap (heap, elt, parent); + heap_swap(heap, elt, parent); } else { break; @@ -59,18 +61,18 @@ rspamd_min_heap_swim (struct rspamd_min_heap *heap, * Sinks the element popped (or changed) to preserve heap's invariant */ static void -rspamd_min_heap_sink (struct rspamd_min_heap *heap, - struct rspamd_min_heap_elt *elt) +rspamd_min_heap_sink(struct rspamd_min_heap *heap, + struct rspamd_min_heap_elt *elt) { struct rspamd_min_heap_elt *c1, *c2, *m; while (elt->idx * 2 < heap->ar->len) { - c1 = g_ptr_array_index (heap->ar, elt->idx * 2 - 1); - c2 = g_ptr_array_index (heap->ar, elt->idx * 2); - m = min_elt (c1, c2); + c1 = g_ptr_array_index(heap->ar, elt->idx * 2 - 1); + c2 = g_ptr_array_index(heap->ar, elt->idx * 2); + m = min_elt(c1, c2); if (elt->pri > m->pri) { - heap_swap (heap, elt, m); + heap_swap(heap, elt, m); } else { break; @@ -78,122 +80,118 @@ rspamd_min_heap_sink (struct rspamd_min_heap *heap, } if (elt->idx * 2 - 1 < heap->ar->len) { - m = g_ptr_array_index (heap->ar, elt->idx * 2 - 1); + m = g_ptr_array_index(heap->ar, elt->idx * 2 - 1); if (elt->pri > m->pri) { - heap_swap (heap, elt, m); + heap_swap(heap, elt, m); } } } struct rspamd_min_heap * -rspamd_min_heap_create (gsize reserved_size) +rspamd_min_heap_create(gsize reserved_size) { struct rspamd_min_heap *heap; - heap = g_malloc (sizeof (*heap)); - heap->ar = g_ptr_array_sized_new (reserved_size); + heap = g_malloc(sizeof(*heap)); + heap->ar = g_ptr_array_sized_new(reserved_size); return heap; } -void -rspamd_min_heap_push (struct rspamd_min_heap *heap, - struct rspamd_min_heap_elt *elt) +void rspamd_min_heap_push(struct rspamd_min_heap *heap, + struct rspamd_min_heap_elt *elt) { - g_assert (heap != NULL); - g_assert (elt != NULL); + g_assert(heap != NULL); + g_assert(elt != NULL); /* Add to the end */ elt->idx = heap->ar->len + 1; - g_ptr_array_add (heap->ar, elt); + g_ptr_array_add(heap->ar, elt); /* Now swim it up */ - rspamd_min_heap_swim (heap, elt); + rspamd_min_heap_swim(heap, elt); } -struct rspamd_min_heap_elt* -rspamd_min_heap_pop (struct rspamd_min_heap *heap) +struct rspamd_min_heap_elt * +rspamd_min_heap_pop(struct rspamd_min_heap *heap) { struct rspamd_min_heap_elt *elt, *last; - g_assert (heap != NULL); + g_assert(heap != NULL); if (heap->ar->len == 0) { return NULL; } - elt = g_ptr_array_index (heap->ar, 0); - last = g_ptr_array_index (heap->ar, heap->ar->len - 1); + elt = g_ptr_array_index(heap->ar, 0); + last = g_ptr_array_index(heap->ar, heap->ar->len - 1); if (elt != last) { /* Now replace elt with the last element and sink it if needed */ - heap_swap (heap, elt, last); - g_ptr_array_remove_index_fast (heap->ar, heap->ar->len - 1); - rspamd_min_heap_sink (heap, last); + heap_swap(heap, elt, last); + g_ptr_array_remove_index_fast(heap->ar, heap->ar->len - 1); + rspamd_min_heap_sink(heap, last); } else { - g_ptr_array_remove_index_fast (heap->ar, heap->ar->len - 1); + g_ptr_array_remove_index_fast(heap->ar, heap->ar->len - 1); } return elt; } -void -rspamd_min_heap_update_elt (struct rspamd_min_heap *heap, - struct rspamd_min_heap_elt *elt, guint npri) +void rspamd_min_heap_update_elt(struct rspamd_min_heap *heap, + struct rspamd_min_heap_elt *elt, guint npri) { guint oldpri; - g_assert (heap != NULL); - g_assert (elt->idx > 0 && elt->idx <= heap->ar->len); + g_assert(heap != NULL); + g_assert(elt->idx > 0 && elt->idx <= heap->ar->len); oldpri = elt->pri; elt->pri = npri; if (npri > oldpri) { /* We might need to sink */ - rspamd_min_heap_sink (heap, elt); + rspamd_min_heap_sink(heap, elt); } else if (npri < oldpri) { /* We might need to swim */ - rspamd_min_heap_swim (heap, elt); + rspamd_min_heap_swim(heap, elt); } } -void -rspamd_min_heap_remove_elt (struct rspamd_min_heap *heap, - struct rspamd_min_heap_elt *elt) +void rspamd_min_heap_remove_elt(struct rspamd_min_heap *heap, + struct rspamd_min_heap_elt *elt) { struct rspamd_min_heap_elt *first; - g_assert (heap != NULL); - g_assert (elt->idx > 0 && elt->idx <= heap->ar->len); + g_assert(heap != NULL); + g_assert(elt->idx > 0 && elt->idx <= heap->ar->len); - first = g_ptr_array_index (heap->ar, 0); + first = g_ptr_array_index(heap->ar, 0); if (elt != first) { elt->pri = first->pri - 1; - rspamd_min_heap_swim (heap, elt); + rspamd_min_heap_swim(heap, elt); } /* Now the desired element is on the top of queue */ - (void)rspamd_min_heap_pop (heap); + (void) rspamd_min_heap_pop(heap); } -void -rspamd_min_heap_destroy (struct rspamd_min_heap *heap) +void rspamd_min_heap_destroy(struct rspamd_min_heap *heap) { if (heap) { - g_ptr_array_free (heap->ar, TRUE); - g_free (heap); + g_ptr_array_free(heap->ar, TRUE); + g_free(heap); } } -struct rspamd_min_heap_elt* -rspamd_min_heap_index (struct rspamd_min_heap *heap, guint idx) +struct rspamd_min_heap_elt * +rspamd_min_heap_index(struct rspamd_min_heap *heap, guint idx) { - g_assert (heap != NULL); - g_assert (idx < heap->ar->len); + g_assert(heap != NULL); + g_assert(idx < heap->ar->len); - return g_ptr_array_index (heap->ar, idx); + return g_ptr_array_index(heap->ar, idx); } |