[GNUnet-SVN] r8367 - GNUnet/src/util/containers

[gnunet]

Author: nevans
Date: 2009-03-31 19:05:58 -0600 (Tue, 31 Mar 2009)
New Revision: 8367

Added:
   GNUnet/src/util/containers/heap.c
   GNUnet/src/util/containers/heaptest.c
Modified:
   GNUnet/src/util/containers/Makefile.am
   GNUnet/src/util/containers/bloomfilter.c
Log:
moved heap into containers

Modified: GNUnet/src/util/containers/Makefile.am
===================================================================
--- GNUnet/src/util/containers/Makefile.am      2009-04-01 01:05:29 UTC (rev 
8366)
+++ GNUnet/src/util/containers/Makefile.am      2009-04-01 01:05:58 UTC (rev 
8367)
@@ -11,7 +11,8 @@
 libcontainers_la_SOURCES = \
  bloomfilter.c \
  meta.c \
- multihashmap.c 
+ multihashmap.c \
+ heap.c
 
 libcontainers_la_LIBADD = \
  -lz \
@@ -20,7 +21,8 @@
 check_PROGRAMS = \
  bloomtest \
  maptest \
- metatest 
+ metatest \
+ heaptest
 
 TESTS = $(check_PROGRAMS)
 
@@ -38,3 +40,8 @@
  metatest.c
 metatest_LDADD = \
  $(top_builddir)/src/util/libgnunetutil.la 
+ 
+heaptest_SOURCES = \
+ heaptest.c
+heaptest_LDADD = \
+ $(top_builddir)/src/util/libgnunetutil.la 

Modified: GNUnet/src/util/containers/bloomfilter.c
===================================================================
--- GNUnet/src/util/containers/bloomfilter.c    2009-04-01 01:05:29 UTC (rev 
8366)
+++ GNUnet/src/util/containers/bloomfilter.c    2009-04-01 01:05:58 UTC (rev 
8367)
@@ -534,7 +534,7 @@
   bf->bitArraySize = size;
   bf->addressesPerElement = k;
   if (data != NULL)
-    memcpy(bf->bitArray, data, size);    
+    memcpy (bf->bitArray, data, size);
   else
     memset (bf->bitArray, 0, bf->bitArraySize);
   return bf;

Copied: GNUnet/src/util/containers/heap.c (from rev 8359, 
GNUnet/src/applications/dv/module/heap.c)
===================================================================
--- GNUnet/src/util/containers/heap.c                           (rev 0)
+++ GNUnet/src/util/containers/heap.c   2009-04-01 01:05:58 UTC (rev 8367)
@@ -0,0 +1,532 @@
+/*
+ This file is part of GNUnet.
+ (C) 2008 Christian Grothoff (and other contributing authors)
+
+ 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
+ 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
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GNUnet; see the file COPYING.  If not, write to the
+ Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA.
+ */
+
+/**
+ * @author Nathan Evans
+ * @file applications/dv/module/heap.c
+ * @brief Implementation of heap operations
+ */
+
+#include "platform.h"
+#include "gnunet_protocols.h"
+#include "gnunet_util.h"
+#include "gnunet_util_containers.h"
+
+/*
+ * Struct that is stored in hashmap, pointers to
+ * locations in min_heap and max_heap.
+ */
+struct GNUNET_CONTAINER_heap_info
+{
+  struct GNUNET_CONTAINER_heap_node *min_loc;
+
+  struct GNUNET_CONTAINER_heap_node *max_loc;
+
+};
+
+/*
+ * Generic heap node structure, contains pointer to parent
+ * left child, right child, and actual neighbor.
+ */
+struct GNUNET_CONTAINER_heap_node
+{
+  struct GNUNET_CONTAINER_heap_node *parent;
+
+  struct GNUNET_CONTAINER_heap_node *left_child;
+
+  struct GNUNET_CONTAINER_heap_node *right_child;
+
+  GNUNET_CostType cost;
+
+  void *element;
+
+};
+
+struct GNUNET_CONTAINER_Heap
+{
+  unsigned int size;
+
+  unsigned int max_size;
+
+  GNUNET_CONTAINER_HeapType type;
+
+  struct GNUNET_CONTAINER_heap_node *root;
+
+  struct GNUNET_CONTAINER_heap_node *traversal_pos;
+
+};
+
+void
+internal_print (struct GNUNET_CONTAINER_heap_node *root)
+{
+  fprintf (stdout, "%d\n", root->cost);
+  if (root->left_child != NULL)
+    {
+      fprintf (stdout, "LEFT of %d\n", root->cost);
+      internal_print (root->left_child);
+    }
+  if (root->right_child != NULL)
+    {
+      fprintf (stdout, "RIGHT of %d\n", root->cost);
+      internal_print (root->right_child);
+    }
+}
+
+void
+printTree (struct GNUNET_CONTAINER_Heap *root)
+{
+  internal_print (root->root);
+}
+
+struct GNUNET_CONTAINER_Heap *
+GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HeapType type)
+{
+  struct GNUNET_CONTAINER_Heap *heap;
+  heap = malloc (sizeof (struct GNUNET_CONTAINER_Heap));
+  heap->max_size = -1;
+  heap->type = type;
+  heap->root = NULL;
+  heap->traversal_pos = NULL;
+  heap->size = 0;
+
+  return heap;
+}
+
+void
+GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
+{
+  void *unused;
+  while (heap->size > 0)
+    {
+      unused = GNUNET_CONTAINER_heap_remove_root (heap);
+    }
+
+  GNUNET_free (heap);
+  return;
+}
+
+struct GNUNET_CONTAINER_heap_node *
+find_element (struct GNUNET_CONTAINER_heap_node *node, void *element)
+{
+  struct GNUNET_CONTAINER_heap_node *ret;
+  ret = NULL;
+  if ((node != NULL) && (node->element == element))
+    {
+      ret = node;
+    }
+
+  if ((ret == NULL) && (node->left_child != NULL))
+    {
+      ret = find_element (node->left_child, element);
+    }
+
+  if ((ret == NULL) && (node->right_child != NULL))
+    {
+      ret = find_element (node->right_child, element);
+    }
+
+  return ret;
+}
+
+static struct GNUNET_CONTAINER_heap_node *
+getNextPos (struct GNUNET_CONTAINER_Heap *root)
+{
+  struct GNUNET_CONTAINER_heap_node *ret;
+  struct GNUNET_CONTAINER_heap_node *parent;
+  int pos;
+  int depth;
+  int i;
+
+  ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_heap_node));
+  pos = root->size + 1;
+  depth = (int) log2 (pos);
+  ret->left_child = NULL;
+  ret->right_child = NULL;
+
+  if (depth == 0)
+    {
+      ret->parent = NULL;
+      root->root = ret;
+    }
+  else
+    {
+      parent = root->root;
+      for (i = depth; i > 1; i--)
+        {
+          if (((pos / (1 << (i - 1))) % 2) == 0)
+            parent = parent->left_child;
+          else
+            parent = parent->right_child;
+        }
+
+      ret->parent = parent;
+      if ((pos % 2) == 0)
+        parent->left_child = ret;
+      else
+        parent->right_child = ret;
+
+    }
+
+  return ret;
+
+}
+
+static struct GNUNET_CONTAINER_heap_node *
+getPos (struct GNUNET_CONTAINER_Heap *root, unsigned int pos)
+{
+  struct GNUNET_CONTAINER_heap_node *ret;
+
+  int depth;
+  int i;
+
+  depth = (int) log2 (pos);
+  ret = NULL;
+  if (pos > root->size)
+    {
+      return ret;
+    }
+  else
+    {
+      ret = root->root;
+      for (i = depth; i > 0; i--)
+        {
+          if (((pos / (1 << (i - 1))) % 2) == 0)
+            ret = ret->left_child;
+          else
+            ret = ret->right_child;
+        }
+    }
+
+  return ret;
+
+}
+
+void
+swapNodes (struct GNUNET_CONTAINER_heap_node *first,
+           struct GNUNET_CONTAINER_heap_node *second,
+           struct GNUNET_CONTAINER_Heap *root)
+{
+  void *temp_element;
+  GNUNET_CostType temp_cost;
+
+  temp_element = first->element;
+  temp_cost = first->cost;
+  first->element = second->element;
+  first->cost = second->cost;
+  second->element = temp_element;
+  second->cost = temp_cost;
+
+/*
+ * I still worry that there is some good reason for
+ * elements being location aware... but it eludes me
+ * for the moment...
+  if ((root->type == GNUNET_DV_MAX_HEAP))
+    {
+      first->neighbor->max_loc = first;
+      second->neighbor->max_loc = second;
+    }
+  else if ((root->type == GNUNET_DV_MIN_HEAP))
+    {
+      first->neighbor->min_loc = first;
+      second->neighbor->min_loc = second;
+    }
+*/
+  return;
+}
+
+void
+percolateHeap (struct GNUNET_CONTAINER_heap_node *pos,
+               struct GNUNET_CONTAINER_Heap *root)
+{
+
+  while ((pos->parent != NULL) &&
+         (((root->type == GNUNET_MAX_HEAP)
+           && (pos->parent->cost < pos->cost))
+          || ((root->type == GNUNET_MIN_HEAP)
+              && (pos->parent->cost > pos->cost))))
+    {
+      swapNodes (pos, pos->parent, root);
+      pos = pos->parent;
+    }
+
+  return;
+}
+
+
+
+void
+percolateDownHeap (struct GNUNET_CONTAINER_heap_node *pos,
+                   struct GNUNET_CONTAINER_Heap *root)
+{
+  struct GNUNET_CONTAINER_heap_node *switchNeighbor;
+
+  switchNeighbor = pos;
+
+  if ((root->type == GNUNET_MAX_HEAP))
+    {
+      if ((pos->left_child != NULL)
+          && (pos->left_child->cost > switchNeighbor->cost))
+        {
+          switchNeighbor = pos->left_child;
+        }
+
+      if ((pos->right_child != NULL)
+          && (pos->right_child->cost > switchNeighbor->cost))
+        {
+          switchNeighbor = pos->right_child;
+        }
+    }
+  else if ((root->type == GNUNET_MIN_HEAP))
+    {
+      if ((pos->left_child != NULL)
+          && (pos->left_child->cost < switchNeighbor->cost))
+        {
+          switchNeighbor = pos->left_child;
+        }
+
+      if ((pos->right_child != NULL)
+          && (pos->right_child->cost < switchNeighbor->cost))
+        {
+          switchNeighbor = pos->right_child;
+        }
+    }
+
+  if (switchNeighbor != pos)
+    {
+      swapNodes (switchNeighbor, pos, root);
+      percolateDownHeap (switchNeighbor, root);
+    }
+
+  return;
+}
+
+void *
+GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *root,
+                                   void *element)
+{
+  void *ret;
+  struct GNUNET_CONTAINER_heap_node *del_node;
+  struct GNUNET_CONTAINER_heap_node *last;
+  GNUNET_CostType old_cost;
+
+  del_node = NULL;
+  del_node = find_element (root->root, element);
+
+  if (del_node == NULL)
+    return NULL;
+
+  ret = del_node->element;
+  last = getPos (root, root->size);
+
+  old_cost = del_node->cost;
+  del_node->element = last->element;
+  del_node->cost = last->cost;
+
+  if (last->parent->left_child == last)
+    last->parent->left_child = NULL;
+  if (last->parent->right_child == last)
+    last->parent->right_child = NULL;
+
+  if (root->traversal_pos == last)
+    {
+      root->traversal_pos = root->root;
+    }
+  GNUNET_free (last);
+  root->size--;
+
+  if (del_node->cost > old_cost)
+    {
+      if (root->type == GNUNET_MAX_HEAP)
+        percolateHeap (del_node, root);
+      else if (root->type == GNUNET_MIN_HEAP)
+        percolateDownHeap (del_node, root);
+    }
+  else if (del_node->cost < old_cost)
+    {
+      if (root->type == GNUNET_MAX_HEAP)
+        percolateDownHeap (del_node, root);
+      else if (root->type == GNUNET_MIN_HEAP)
+        percolateHeap (del_node, root);
+    }
+
+  return ret;
+}
+
+int
+GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root,
+                              void *element, GNUNET_CostType cost)
+{
+  struct GNUNET_CONTAINER_heap_node *new_pos;
+  int ret;
+  ret = GNUNET_YES;
+
+  if (root->max_size > root->size)
+    {
+      new_pos = getNextPos (root);
+      new_pos->element = element;
+      new_pos->cost = cost;
+      root->size++;
+      /*We no longer can tolerate pointers between heaps :( */
+      /*if (root->type == GNUNET_DV_MIN_HEAP)
+         new_pos->neighbor->min_loc = new_pos;
+         else if (root->type == GNUNET_DV_MAX_HEAP)
+         new_pos->neighbor->max_loc = new_pos; */
+
+      percolateHeap (new_pos, root);
+    }
+  else
+    {
+      ret = GNUNET_NO;
+    }
+
+  return ret;
+}
+
+void *
+GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root)
+{
+  void *ret;
+  struct GNUNET_CONTAINER_heap_node *root_node;
+  struct GNUNET_CONTAINER_heap_node *last;
+
+  root_node = root->root;
+  ret = root_node->element;
+  last = getPos (root, root->size);
+
+  if (last->parent->left_child == last)
+    last->parent->left_child = NULL;
+  else if (last->parent->right_child == last)
+    last->parent->right_child = NULL;
+
+  root_node->element = last->element;
+  root_node->cost = last->cost;
+
+  if (root->traversal_pos == last)
+    {
+      root->traversal_pos = root->root;
+    }
+
+  GNUNET_free (last);
+  root->size--;
+  percolateDownHeap (root->root, root);
+  return ret;
+}
+
+static int
+updatedCost (struct GNUNET_CONTAINER_Heap *root,
+             struct GNUNET_CONTAINER_heap_node *node)
+{
+  struct GNUNET_CONTAINER_heap_node *parent;
+
+  if (node == NULL)
+    return GNUNET_SYSERR;
+
+  parent = node->parent;
+
+  if ((root->type == GNUNET_MAX_HEAP) && (parent != NULL)
+      && (node->cost > parent->cost))
+    percolateHeap (node, root);
+  else if ((root->type == GNUNET_MIN_HEAP) && (parent != NULL)
+           && (node->cost < parent->cost))
+    percolateHeap (node, root);
+  else if (root->type == GNUNET_MAX_HEAP)
+    percolateDownHeap (node, root);
+  else if (root->type == GNUNET_MIN_HEAP)
+    percolateDownHeap (node, root);
+
+  return GNUNET_YES;
+}
+
+
+int
+GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *root,
+                                   void *element, GNUNET_CostType new_cost)
+{
+  struct GNUNET_CONTAINER_heap_node *node;
+  int ret = GNUNET_YES;
+  node = find_element (root->root, element);
+  if (node == NULL)
+    return GNUNET_NO;
+
+  node->cost = new_cost;
+  ret = updatedCost (root, node);
+  return ret;
+}
+
+void
+internal_iterator (struct GNUNET_CONTAINER_Heap *root,
+                   struct GNUNET_CONTAINER_heap_node *node,
+                   GNUNET_CONTAINER_HeapIterator iterator, void *cls)
+{
+  if (node == NULL)
+    return;
+  internal_iterator (root, node->left_child, iterator, cls);
+  internal_iterator (root, node->right_child, iterator, cls);
+  iterator (node->element, node->cost, root, cls);
+}
+
+int
+GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
+                               GNUNET_CONTAINER_HeapIterator iterator,
+                               void *cls)
+{
+  internal_iterator (heap, heap->root, iterator, cls);
+  return GNUNET_OK;
+}
+
+void *
+GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *root)
+{
+  unsigned int choice;
+  void *element;
+
+  if ((root->traversal_pos == NULL) && (root->root != NULL))
+    {
+      root->traversal_pos = root->root;
+    }
+
+  if (root->traversal_pos == NULL)
+    return NULL;
+
+  element = root->traversal_pos->element;
+
+  choice = GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK, 2);
+
+  switch (choice)
+    {
+    case 1:
+      root->traversal_pos = root->traversal_pos->right_child;
+      break;
+    case 0:
+      root->traversal_pos = root->traversal_pos->left_child;
+      break;
+    }
+
+  return element;
+
+}
+
+unsigned int
+GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap)
+{
+  return heap->size;
+}
+
+/* end of heap.c */


Property changes on: GNUnet/src/util/containers/heap.c
___________________________________________________________________
Added: svn:mergeinfo
   + 

Copied: GNUnet/src/util/containers/heaptest.c (from rev 8359, 
GNUnet/src/applications/dv/module/heaptest.c)
===================================================================
--- GNUnet/src/util/containers/heaptest.c                               (rev 0)
+++ GNUnet/src/util/containers/heaptest.c       2009-04-01 01:05:58 UTC (rev 
8367)
@@ -0,0 +1,110 @@
+/*
+ This file is part of GNUnet.
+ (C) 2008 Christian Grothoff (and other contributing authors)
+
+ 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
+ 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
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GNUnet; see the file COPYING.  If not, write to the
+ Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA.
+ */
+
+/**
+ * @author Nathan Evans
+ * @file util/containers/heaptest.c
+ * @brief Test of heap operations
+ */
+
+#include "gnunet_util.h"
+#include "gnunet_util_containers.h"
+#include "dv.h"
+
+static int
+iterator_callback (void *element, GNUNET_CostType cost,
+                   struct GNUNET_CONTAINER_Heap *root, void *cls)
+{
+  struct GNUNET_dv_neighbor *node;
+  node = (struct GNUNET_dv_neighbor *) element;
+  fprintf (stdout, "%d\n", node->cost);
+  //fprintf (stdout, "%d\n", ((struct GNUNET_dv_neighbor *)element)->cost);
+
+  return GNUNET_OK;
+}
+
+
+int
+main (int argc, char **argv)
+{
+  struct GNUNET_CONTAINER_Heap *myHeap;
+  struct GNUNET_dv_neighbor *neighbor1;
+  struct GNUNET_dv_neighbor *neighbor2;
+  struct GNUNET_dv_neighbor *neighbor3;
+  struct GNUNET_dv_neighbor *neighbor4;
+  struct GNUNET_dv_neighbor *neighbor5;
+  struct GNUNET_dv_neighbor *neighbor6;
+
+  myHeap = GNUNET_CONTAINER_heap_create (GNUNET_MAX_HEAP);
+
+  neighbor1 = malloc (sizeof (struct GNUNET_dv_neighbor));
+  neighbor2 = malloc (sizeof (struct GNUNET_dv_neighbor));
+  neighbor3 = malloc (sizeof (struct GNUNET_dv_neighbor));
+  neighbor4 = malloc (sizeof (struct GNUNET_dv_neighbor));
+  neighbor5 = malloc (sizeof (struct GNUNET_dv_neighbor));
+  neighbor6 = malloc (sizeof (struct GNUNET_dv_neighbor));
+
+  neighbor1->cost = 60;
+  neighbor2->cost = 50;
+  neighbor3->cost = 70;
+  neighbor4->cost = 120;
+  neighbor5->cost = 100;
+  neighbor6->cost = 30;
+
+  GNUNET_CONTAINER_heap_insert (myHeap, neighbor1, neighbor1->cost);
+  GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
+
+  fprintf (stdout, "\n");
+  GNUNET_CONTAINER_heap_insert (myHeap, neighbor2, neighbor2->cost);
+
+  GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
+  fprintf (stdout, "\n");
+  GNUNET_CONTAINER_heap_insert (myHeap, neighbor3, neighbor3->cost);
+
+  GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
+  fprintf (stdout, "\n");
+  GNUNET_CONTAINER_heap_insert (myHeap, neighbor4, neighbor4->cost);
+
+  GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
+  fprintf (stdout, "\n");
+  GNUNET_CONTAINER_heap_insert (myHeap, neighbor5, neighbor5->cost);
+
+  GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
+  fprintf (stdout, "\n");
+  GNUNET_CONTAINER_heap_insert (myHeap, neighbor6, neighbor6->cost);
+
+  GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
+  fprintf (stdout, "\n");
+  GNUNET_CONTAINER_heap_remove_node (myHeap, neighbor5);
+
+  GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
+  fprintf (stdout, "\n");
+  GNUNET_CONTAINER_heap_remove_root (myHeap);
+
+  GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
+  fprintf (stdout, "\n");
+  GNUNET_CONTAINER_heap_update_cost (myHeap, neighbor6, 200);
+
+  GNUNET_CONTAINER_heap_iterate (myHeap, iterator_callback, NULL);
+  fprintf (stdout, "\n");
+  return 0;
+}
+
+/* end of heaptest.c */


Property changes on: GNUnet/src/util/containers/heaptest.c
___________________________________________________________________
Added: svn:mergeinfo
   +