X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Futil%2Fcontainer_heap.c;h=0f63f957dd5d46acf5755c614aae0b224e0a0d83;hb=fdbe690beeec04066f18302401096eb5212c3f6a;hp=051b85a2517c5ebacbb4ff70aa6cf4314cf8e572;hpb=d9d94d0e53d26af75ec8241383d166544ebd79f3;p=oweals%2Fgnunet.git

diff --git a/src/util/container_heap.c b/src/util/container_heap.c
index 051b85a25..0f63f957d 100644
--- a/src/util/container_heap.c
+++ b/src/util/container_heap.c
@@ -4,7 +4,7 @@
 
   GNUnet is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published
-  by the Free Software Foundation; either version 2, or (at your
+  by the Free Software Foundation; either version 3, or (at your
   option) any later version.
 
   GNUnet is distributed in the hope that it will be useful, but
@@ -30,7 +30,7 @@
 
 #define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
 
-#define DEBUG 0
+#define EXTRA_CHECKS 0
 
 /**
  * Node in the heap.
@@ -104,7 +104,7 @@ struct GNUNET_CONTAINER_Heap
 };
 
 
-#if DEBUG
+#if EXTRA_CHECKS
 /**
  * Check if internal invariants hold for the given node.
  *
@@ -116,10 +116,10 @@ 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));
+                 ((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);
 }
@@ -198,7 +198,7 @@ GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap)
  */
 GNUNET_CONTAINER_HeapCostType
 GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
-				     * node)
+                                     *node)
 {
   return node->cost;
 }
@@ -214,8 +214,8 @@ GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
  */
 static int
 node_iterator (const struct GNUNET_CONTAINER_Heap *heap,
-	       struct GNUNET_CONTAINER_HeapNode *node,
-	       GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
+               struct GNUNET_CONTAINER_HeapNode *node,
+               GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
 {
   if (node == NULL)
     return GNUNET_YES;
@@ -238,8 +238,8 @@ node_iterator (const struct GNUNET_CONTAINER_Heap *heap,
  */
 void
 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
-			       GNUNET_CONTAINER_HeapIterator iterator,
-			       void *iterator_cls)
+                               GNUNET_CONTAINER_HeapIterator iterator,
+                               void *iterator_cls)
 {
   (void) node_iterator (heap, heap->root, iterator, iterator_cls);
 }
@@ -269,9 +269,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;
 }
 
@@ -286,51 +286,51 @@ GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
  */
 static void
 insert_node (struct GNUNET_CONTAINER_Heap *heap,
-	     struct GNUNET_CONTAINER_HeapNode *pos,
-	     struct GNUNET_CONTAINER_HeapNode *node)
+             struct GNUNET_CONTAINER_HeapNode *pos,
+             struct GNUNET_CONTAINER_HeapNode *node)
 {
   struct GNUNET_CONTAINER_HeapNode *parent;
 
   GNUNET_assert (node->parent == NULL);
   while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >=
-							     node->cost)
-	 : (pos->cost <= node->cost))
+                                                             node->cost)
+         : (pos->cost <= node->cost))
+  {
+    /* node is descendent of pos */
+    pos->tree_size += (1 + node->tree_size);
+    if (pos->left_child == NULL)
     {
-      /* 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;
+      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;
+  }
   /* 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);
@@ -346,9 +346,8 @@ 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;
 
@@ -384,27 +383,29 @@ 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);
-#if DEBUG
+#if EXTRA_CHECKS
   GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
-		 (heap->size == heap->root->tree_size + 1));
+                 (heap->size == heap->root->tree_size + 1));
   CHECK (heap->root);
 #endif
   return ret;
@@ -436,43 +437,43 @@ 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)
     {
-      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;
-	}
+      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
+    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);
-	}
+      heap->root = node->right_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->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);
     }
+  }
   node->parent = NULL;
   node->left_child = NULL;
   node->right_child = NULL;
@@ -503,10 +504,10 @@ GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node)
   if (heap->walk_pos == node)
     heap->walk_pos = NULL;
   GNUNET_free (node);
-#if DEBUG
+#if EXTRA_CHECKS
   CHECK (heap->root);
   GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
-		 (heap->size == heap->root->tree_size + 1));
+                 (heap->size == heap->root->tree_size + 1));
 #endif
   return ret;
 }
@@ -521,29 +522,29 @@ GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node)
  */
 void
 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
-				   struct GNUNET_CONTAINER_HeapNode *node,
-				   GNUNET_CONTAINER_HeapCostType new_cost)
+                                   struct GNUNET_CONTAINER_HeapNode *node,
+                                   GNUNET_CONTAINER_HeapCostType new_cost)
 {
-#if DEBUG
+#if EXTRA_CHECKS
   GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
-		 (heap->size == heap->root->tree_size + 1));
+                 (heap->size == heap->root->tree_size + 1));
   CHECK (heap->root);
 #endif
   remove_node (node);
-#if DEBUG
+#if EXTRA_CHECKS
   CHECK (heap->root);
   GNUNET_assert (((heap->size == 1) && (heap->root == NULL)) ||
-		 (heap->size == heap->root->tree_size + 2));
+                 (heap->size == heap->root->tree_size + 2));
 #endif
   node->cost = new_cost;
   if (heap->root == NULL)
     heap->root = node;
   else
     insert_node (heap, heap->root, node);
-#if DEBUG
+#if EXTRA_CHECKS
   CHECK (heap->root);
   GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
-		 (heap->size == heap->root->tree_size + 1));
+                 (heap->size == heap->root->tree_size + 1));
 #endif
 }