- dont resend useless channel_destroy messages

[oweals/gnunet.git] / src / util / container_heap.c

diff --git a/src/util/container_heap.c b/src/util/container_heap.c
index 051b85a2517c5ebacbb4ff70aa6cf4314cf8e572..0f63f957dd5d46acf5755c614aae0b224e0a0d83 100644 (file)
--- 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
 
   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
   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 LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
 

-#define DEBUG 0
+#define EXTRA_CHECKS 0

 
 /**
  * Node in the heap.
 
 /**
  * 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.
  *
 /**
  * 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 ==
   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);
 }
   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
  */
 GNUNET_CONTAINER_HeapCostType
 GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode

-                                    * node)
+                                     *node)

 {
   return node->cost;
 }
 {
   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,
  */
 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;
 {
   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,
  */
 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);
 }
 {
   (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 =
     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;
 }
 
   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,
  */
 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 >=
 {
   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)
   /* make 'node' parent of 'pos' */
   parent = pos->parent;
   pos->parent = NULL;
   node->parent = parent;
   if (NULL == parent)

-    {
-      heap->root = node;
-    }
+  {
+    heap->root = node;
+  }

   else
   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 '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 *
  * @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;
 
 {
   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->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)
   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
   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 DEBUG
+#if EXTRA_CHECKS

   GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
   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;
   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)
 
   /* 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)
       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;
   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 (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)) ||
   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;
 }
 #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,
  */
 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)) ||
   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);
   CHECK (heap->root);
 #endif
   remove_node (node);

-#if DEBUG
+#if EXTRA_CHECKS

   CHECK (heap->root);
   GNUNET_assert (((heap->size == 1) && (heap->root == NULL)) ||
   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);
 #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)) ||
   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
 }
 
 #endif
 }