1 files changed, 162 insertions, 167 deletions

diff --git a/src/util/container_heap.c b/src/util/container_heap.c
index d5dca20ef..3c8e6ce58 100644
--- a/src/util/container_heap.c
+++ b/src/util/container_heap.c
@@ -1,22 +1,22 @@
 /*
-  This file is part of GNUnet.
-  Copyright (C) 2008, 2009 GNUnet e.V.
-
-  GNUnet is free software: you can redistribute it and/or modify it
-  under the terms of the GNU Affero General Public License as published
-  by the Free Software Foundation, either version 3 of the License,
-  or (at your option) any later version.
-
-  GNUnet is distributed in the hope that it will be useful, but
-  WITHOUT ANY WARRANTY; without even the implied warranty of
-  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-  Affero General Public License for more details.
- 
-  You should have received a copy of the GNU Affero General Public License
-  along with this program.  If not, see <http://www.gnu.org/licenses/>.
+   This file is part of GNUnet.
+   Copyright (C) 2008, 2009 GNUnet e.V.
+
+   GNUnet is free software: you can redistribute it and/or modify it
+   under the terms of the GNU Affero General Public License as published
+   by the Free Software Foundation, either version 3 of the License,
+   or (at your option) any later version.
+
+   GNUnet is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Affero General Public License for more details.
+
+   You should have received a copy of the GNU Affero General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
      SPDX-License-Identifier: AGPL3.0-or-later
-*/
+ */
 
 /**
  * @file util/container_heap.c
@@ -28,15 +28,14 @@
 #include "platform.h"
 #include "gnunet_container_lib.h"
 
-#define LOG(kind,...) GNUNET_log_from (kind, "util-container-heap", __VA_ARGS__)
+#define LOG(kind, ...) GNUNET_log_from(kind, "util-container-heap", __VA_ARGS__)
 
 #define EXTRA_CHECKS 0
 
 /**
  * Node in the heap.
  */
-struct GNUNET_CONTAINER_HeapNode
-{
+struct GNUNET_CONTAINER_HeapNode {
   /**
    * Heap this node belongs to.
    */
@@ -72,15 +71,12 @@ struct GNUNET_CONTAINER_HeapNode
    * (excluding this node itself).
    */
   unsigned int tree_size;
-
 };
 
 /**
  * Handle to a node in a heap.
  */
-struct GNUNET_CONTAINER_Heap
-{
-
+struct GNUNET_CONTAINER_Heap {
   /**
    * Root of the heap.
    */
@@ -100,7 +96,6 @@ struct GNUNET_CONTAINER_Heap
    * How is the heap sorted?
    */
   enum GNUNET_CONTAINER_HeapOrder order;
-
 };
 
 
@@ -111,17 +106,17 @@ struct GNUNET_CONTAINER_Heap
  * @param node subtree to check
  */
 static void
-check (const struct GNUNET_CONTAINER_HeapNode *node)
+check(const struct GNUNET_CONTAINER_HeapNode *node)
 {
   if (NULL == node)
     return;
-  GNUNET_assert (node->tree_size ==
-                 ((node->left_child ==
-                   NULL) ? 0 : 1 + node->left_child->tree_size) +
-                 ((node->right_child ==
-                   NULL) ? 0 : 1 + node->right_child->tree_size));
-  check (node->left_child);
-  check (node->right_child);
+  GNUNET_assert(node->tree_size ==
+                ((node->left_child ==
+                  NULL) ? 0 : 1 + node->left_child->tree_size) +
+                ((node->right_child ==
+                  NULL) ? 0 : 1 + node->right_child->tree_size));
+  check(node->left_child);
+  check(node->right_child);
 }
 
 
@@ -138,11 +133,11 @@ check (const struct GNUNET_CONTAINER_HeapNode *node)
  * @return handle to the heap
  */
 struct GNUNET_CONTAINER_Heap *
-GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order)
+GNUNET_CONTAINER_heap_create(enum GNUNET_CONTAINER_HeapOrder order)
 {
   struct GNUNET_CONTAINER_Heap *heap;
 
-  heap = GNUNET_new (struct GNUNET_CONTAINER_Heap);
+  heap = GNUNET_new(struct GNUNET_CONTAINER_Heap);
   heap->order = order;
   return heap;
 }
@@ -155,10 +150,10 @@ GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order)
  * @param heap heap to destroy
  */
 void
-GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
+GNUNET_CONTAINER_heap_destroy(struct GNUNET_CONTAINER_Heap *heap)
 {
-  GNUNET_break (heap->size == 0);
-  GNUNET_free (heap);
+  GNUNET_break(heap->size == 0);
+  GNUNET_free(heap);
 }
 
 
@@ -169,7 +164,7 @@ GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
  * @return Element at the root, or NULL if heap is empty.
  */
 void *
-GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap)
+GNUNET_CONTAINER_heap_peek(const struct GNUNET_CONTAINER_Heap *heap)
 {
   if (heap->root == NULL)
     return NULL;
@@ -187,9 +182,9 @@ GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap)
  *         #GNUNET_NO  if the heap is empty.
  */
 int
-GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap,
-                             void **element,
-                             GNUNET_CONTAINER_HeapCostType *cost)
+GNUNET_CONTAINER_heap_peek2(const struct GNUNET_CONTAINER_Heap *heap,
+                            void **element,
+                            GNUNET_CONTAINER_HeapCostType *cost)
 {
   if (NULL == heap->root)
     return GNUNET_NO;
@@ -208,7 +203,7 @@ GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap,
  * @return number of elements stored
  */
 unsigned int
-GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap)
+GNUNET_CONTAINER_heap_get_size(const struct GNUNET_CONTAINER_Heap *heap)
 {
   return heap->size;
 }
@@ -221,8 +216,8 @@ GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap)
  * @return cost of the node
  */
 GNUNET_CONTAINER_HeapCostType
-GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
-                                     *node)
+GNUNET_CONTAINER_heap_node_get_cost(const struct GNUNET_CONTAINER_HeapNode
+                                    *node)
 {
   return node->cost;
 }
@@ -238,19 +233,19 @@ GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
  * @return GNUNET_YES to continue to iterate
  */
 static int
-node_iterator (const struct GNUNET_CONTAINER_Heap *heap,
-               struct GNUNET_CONTAINER_HeapNode *node,
-               GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
+node_iterator(const struct GNUNET_CONTAINER_Heap *heap,
+              struct GNUNET_CONTAINER_HeapNode *node,
+              GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
 {
   if (node == NULL)
     return GNUNET_YES;
   if (GNUNET_YES !=
-      node_iterator (heap, node->left_child, iterator, iterator_cls))
+      node_iterator(heap, node->left_child, iterator, iterator_cls))
     return GNUNET_NO;
   if (GNUNET_YES !=
-      node_iterator (heap, node->right_child, iterator, iterator_cls))
+      node_iterator(heap, node->right_child, iterator, iterator_cls))
     return GNUNET_NO;
-  return iterator (iterator_cls, node, node->element, node->cost);
+  return iterator(iterator_cls, node, node->element, node->cost);
 }
 
 
@@ -262,11 +257,11 @@ node_iterator (const struct GNUNET_CONTAINER_Heap *heap,
  * @param iterator_cls closure for iterator
  */
 void
-GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
-                               GNUNET_CONTAINER_HeapIterator iterator,
-                               void *iterator_cls)
+GNUNET_CONTAINER_heap_iterate(const struct GNUNET_CONTAINER_Heap *heap,
+                              GNUNET_CONTAINER_HeapIterator iterator,
+                              void *iterator_cls)
 {
-  (void) node_iterator (heap, heap->root, iterator, iterator_cls);
+  (void)node_iterator(heap, heap->root, iterator, iterator_cls);
 }
 
 
@@ -282,7 +277,7 @@ GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
  *         NULL if the tree is empty.
  */
 void *
-GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
+GNUNET_CONTAINER_heap_walk_get_next(struct GNUNET_CONTAINER_Heap *heap)
 {
   struct GNUNET_CONTAINER_HeapNode *pos;
   void *element;
@@ -294,9 +289,9 @@ GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
     pos = heap->root;
   element = pos->element;
   heap->walk_pos =
-      (0 ==
-       GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
-                                 2)) ? pos->right_child : pos->left_child;
+    (0 ==
+     GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_WEAK,
+                              2)) ? pos->right_child : pos->left_child;
   return element;
 }
 
@@ -310,55 +305,55 @@ GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
  * @param node node to insert (which may be a subtree itself)
  */
 static void
-insert_node (struct GNUNET_CONTAINER_Heap *heap,
-             struct GNUNET_CONTAINER_HeapNode *pos,
-             struct GNUNET_CONTAINER_HeapNode *node)
+insert_node(struct GNUNET_CONTAINER_Heap *heap,
+            struct GNUNET_CONTAINER_HeapNode *pos,
+            struct GNUNET_CONTAINER_HeapNode *node)
 {
   struct GNUNET_CONTAINER_HeapNode *parent;
 
-  GNUNET_assert (node->parent == NULL);
+  GNUNET_assert(node->parent == NULL);
   while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >=
                                                              node->cost)
          : (pos->cost <= node->cost))
-  {
-    /* node is descendent of pos */
-    pos->tree_size += (1 + node->tree_size);
-    if (pos->left_child == NULL)
-    {
-      pos->left_child = node;
-      node->parent = pos;
-      return;
-    }
-    if (pos->right_child == NULL)
     {
-      pos->right_child = node;
-      node->parent = pos;
-      return;
+      /* node is descendent of pos */
+      pos->tree_size += (1 + node->tree_size);
+      if (pos->left_child == NULL)
+        {
+          pos->left_child = node;
+          node->parent = pos;
+          return;
+        }
+      if (pos->right_child == NULL)
+        {
+          pos->right_child = node;
+          node->parent = pos;
+          return;
+        }
+      /* keep it balanced by descending into smaller subtree */
+      if (pos->left_child->tree_size < pos->right_child->tree_size)
+        pos = pos->left_child;
+      else
+        pos = pos->right_child;
     }
-    /* keep it balanced by descending into smaller subtree */
-    if (pos->left_child->tree_size < pos->right_child->tree_size)
-      pos = pos->left_child;
-    else
-      pos = pos->right_child;
-  }
   /* make 'node' parent of 'pos' */
   parent = pos->parent;
   pos->parent = NULL;
   node->parent = parent;
   if (NULL == parent)
-  {
-    heap->root = node;
-  }
+    {
+      heap->root = node;
+    }
   else
-  {
-    if (parent->left_child == pos)
-      parent->left_child = node;
-    else
-      parent->right_child = node;
-  }
+    {
+      if (parent->left_child == pos)
+        parent->left_child = node;
+      else
+        parent->right_child = node;
+    }
   /* insert 'pos' below 'node' */
-  insert_node (heap, node, pos);
-  CHECK (pos);
+  insert_node(heap, node, pos);
+  CHECK(pos);
 }
 
 
@@ -371,12 +366,12 @@ insert_node (struct GNUNET_CONTAINER_Heap *heap,
  * @return node for the new element
  */
 struct GNUNET_CONTAINER_HeapNode *
-GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element,
-                              GNUNET_CONTAINER_HeapCostType cost)
+GNUNET_CONTAINER_heap_insert(struct GNUNET_CONTAINER_Heap *heap, void *element,
+                             GNUNET_CONTAINER_HeapCostType cost)
 {
   struct GNUNET_CONTAINER_HeapNode *node;
 
-  node = GNUNET_new (struct GNUNET_CONTAINER_HeapNode);
+  node = GNUNET_new(struct GNUNET_CONTAINER_HeapNode);
   node->heap = heap;
   node->element = element;
   node->cost = cost;
@@ -384,9 +379,9 @@ GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element,
   if (NULL == heap->root)
     heap->root = node;
   else
-    insert_node (heap, heap->root, node);
-  GNUNET_assert (heap->size == heap->root->tree_size + 1);
-  CHECK (heap->root);
+    insert_node(heap, heap->root, node);
+  GNUNET_assert(heap->size == heap->root->tree_size + 1);
+  CHECK(heap->root);
   return node;
 }
 
@@ -398,7 +393,7 @@ GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element,
  * @return element data stored at the root node, NULL if heap is empty
  */
 void *
-GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap)
+GNUNET_CONTAINER_heap_remove_root(struct GNUNET_CONTAINER_Heap *heap)
 {
   void *ret;
   struct GNUNET_CONTAINER_HeapNode *root;
@@ -408,30 +403,30 @@ GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap)
   heap->size--;
   ret = root->element;
   if (root->left_child == NULL)
-  {
-    heap->root = root->right_child;
-    if (root->right_child != NULL)
-      root->right_child->parent = NULL;
-  }
+    {
+      heap->root = root->right_child;
+      if (root->right_child != NULL)
+        root->right_child->parent = NULL;
+    }
   else if (root->right_child == NULL)
-  {
-    heap->root = root->left_child;
-    root->left_child->parent = NULL;
-  }
+    {
+      heap->root = root->left_child;
+      root->left_child->parent = NULL;
+    }
   else
-  {
-    root->left_child->parent = NULL;
-    root->right_child->parent = NULL;
-    heap->root = root->left_child;
-    insert_node (heap, heap->root, root->right_child);
-  }
+    {
+      root->left_child->parent = NULL;
+      root->right_child->parent = NULL;
+      heap->root = root->left_child;
+      insert_node(heap, heap->root, root->right_child);
+    }
   if (heap->walk_pos == root)
     heap->walk_pos = heap->root;
-  GNUNET_free (root);
+  GNUNET_free(root);
 #if EXTRA_CHECKS
-  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
-                 (heap->size == heap->root->tree_size + 1));
-  CHECK (heap->root);
+  GNUNET_assert(((heap->size == 0) && (heap->root == NULL)) ||
+                (heap->size == heap->root->tree_size + 1));
+  CHECK(heap->root);
 #endif
   return ret;
 }
@@ -444,7 +439,7 @@ GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap)
  * 'size' field of the tree.
  */
 static void
-remove_node (struct GNUNET_CONTAINER_HeapNode *node)
+remove_node(struct GNUNET_CONTAINER_HeapNode *node)
 {
   struct GNUNET_CONTAINER_HeapNode *ancestor;
   struct GNUNET_CONTAINER_Heap *heap = node->heap;
@@ -462,48 +457,48 @@ remove_node (struct GNUNET_CONTAINER_HeapNode *node)
 
   /* unlink 'node' itself and insert children in its place */
   if (node->parent == NULL)
-  {
-    if (node->left_child != NULL)
     {
-      heap->root = node->left_child;
-      node->left_child->parent = NULL;
-      if (node->right_child != NULL)
-      {
-        node->right_child->parent = NULL;
-        insert_node (heap, heap->root, node->right_child);
-      }
-    }
-    else
-    {
-      heap->root = node->right_child;
-      if (node->right_child != NULL)
-        node->right_child->parent = NULL;
+      if (node->left_child != NULL)
+        {
+          heap->root = node->left_child;
+          node->left_child->parent = NULL;
+          if (node->right_child != NULL)
+            {
+              node->right_child->parent = NULL;
+              insert_node(heap, heap->root, node->right_child);
+            }
+        }
+      else
+        {
+          heap->root = node->right_child;
+          if (node->right_child != NULL)
+            node->right_child->parent = NULL;
+        }
     }
-  }
   else
-  {
-    if (node->parent->left_child == node)
-      node->parent->left_child = NULL;
-    else
-      node->parent->right_child = NULL;
-    if (node->left_child != NULL)
     {
-      node->left_child->parent = NULL;
-      node->parent->tree_size -= (1 + node->left_child->tree_size);
-      insert_node (heap, node->parent, node->left_child);
-    }
-    if (node->right_child != NULL)
-    {
-      node->right_child->parent = NULL;
-      node->parent->tree_size -= (1 + node->right_child->tree_size);
-      insert_node (heap, node->parent, node->right_child);
+      if (node->parent->left_child == node)
+        node->parent->left_child = NULL;
+      else
+        node->parent->right_child = NULL;
+      if (node->left_child != NULL)
+        {
+          node->left_child->parent = NULL;
+          node->parent->tree_size -= (1 + node->left_child->tree_size);
+          insert_node(heap, node->parent, node->left_child);
+        }
+      if (node->right_child != NULL)
+        {
+          node->right_child->parent = NULL;
+          node->parent->tree_size -= (1 + node->right_child->tree_size);
+          insert_node(heap, node->parent, node->right_child);
+        }
     }
-  }
   node->parent = NULL;
   node->left_child = NULL;
   node->right_child = NULL;
-  GNUNET_assert (node->tree_size == 0);
-  CHECK (heap->root);
+  GNUNET_assert(node->tree_size == 0);
+  CHECK(heap->root);
 }
 
 
@@ -514,25 +509,25 @@ remove_node (struct GNUNET_CONTAINER_HeapNode *node)
  * @return element data stored at the node
  */
 void *
-GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node)
+GNUNET_CONTAINER_heap_remove_node(struct GNUNET_CONTAINER_HeapNode *node)
 {
   void *ret;
   struct GNUNET_CONTAINER_Heap *heap;
 
   heap = node->heap;
-  CHECK (heap->root);
+  CHECK(heap->root);
   if (heap->walk_pos == node)
-    (void) GNUNET_CONTAINER_heap_walk_get_next (heap);
-  remove_node (node);
+    (void)GNUNET_CONTAINER_heap_walk_get_next(heap);
+  remove_node(node);
   heap->size--;
   ret = node->element;
   if (heap->walk_pos == node)
     heap->walk_pos = NULL;
-  GNUNET_free (node);
+  GNUNET_free(node);
 #if EXTRA_CHECKS
-  CHECK (heap->root);
-  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
-                 (heap->size == heap->root->tree_size + 1));
+  CHECK(heap->root);
+  GNUNET_assert(((heap->size == 0) && (heap->root == NULL)) ||
+                (heap->size == heap->root->tree_size + 1));
 #endif
   return ret;
 }
@@ -545,19 +540,19 @@ GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node)
  * @param new_cost new cost for the node
  */
 void
-GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_HeapNode *node,
-                                   GNUNET_CONTAINER_HeapCostType new_cost)
+GNUNET_CONTAINER_heap_update_cost(struct GNUNET_CONTAINER_HeapNode *node,
+                                  GNUNET_CONTAINER_HeapCostType new_cost)
 {
   struct GNUNET_CONTAINER_Heap *heap = node->heap;
 
-  remove_node (node);
+  remove_node(node);
   node->cost = new_cost;
   if (NULL == heap->root)
     heap->root = node;
   else
-    insert_node (heap,
-                 heap->root,
-                 node);
+    insert_node(heap,
+                heap->root,
+                node);
 }