aboutsummaryrefslogtreecommitdiffstats
path: root/src/libutil/heap.c
diff options
context:
space:
mode:
authorVsevolod Stakhov <vsevolod@rspamd.com>2023-07-26 10:49:23 +0100
committerVsevolod Stakhov <vsevolod@rspamd.com>2023-07-26 10:49:23 +0100
commit537a7180a0d5132c11636c4fd8b1450cd99d352c (patch)
treefb9f8c84955a411bdffbd6371ea32f2716fb3687 /src/libutil/heap.c
parent5fd7a90fdaa33f52c59bdb0ca84451e5c1e22365 (diff)
downloadrspamd-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.c128
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);
}