container_heap.c

Go to the documentation of this file.

/*
   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
 */
 
#include "platform.h"
#include "gnunet_util_lib.h"
 
#define LOG(kind, ...) GNUNET_log_from (kind, "util-container-heap", \
                                        __VA_ARGS__)
 
#define EXTRA_CHECKS 0
 
struct GNUNET_CONTAINER_HeapNode
{
  struct GNUNET_CONTAINER_Heap *heap;
 
  struct GNUNET_CONTAINER_HeapNode *parent;
 
  struct GNUNET_CONTAINER_HeapNode *left_child;
 
  struct GNUNET_CONTAINER_HeapNode *right_child;
 
  void *element;
 
  GNUNET_CONTAINER_HeapCostType cost;
 
  unsigned int tree_size;
};
 
struct GNUNET_CONTAINER_Heap
{
  struct GNUNET_CONTAINER_HeapNode *root;
 
  struct GNUNET_CONTAINER_HeapNode *walk_pos;
 
  unsigned int size;
 
  enum GNUNET_CONTAINER_HeapOrder order;
};
 
 
#if EXTRA_CHECKS
static void
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);
}
 
 
#define CHECK(n) check (n)
#else
#define CHECK(n) do {} while (0)
#endif
 
 
struct GNUNET_CONTAINER_Heap *
GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order)
{
  struct GNUNET_CONTAINER_Heap *heap;
 
  heap = GNUNET_new (struct GNUNET_CONTAINER_Heap);
  heap->order = order;
  return heap;
}
 
 
void
GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
{
  GNUNET_break (heap->size == 0);
  GNUNET_free (heap);
}
 
 
void *
GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap)
{
  if (heap->root == NULL)
    return NULL;
  return heap->root->element;
}
 
 
int
GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap,
                             void **element,
                             GNUNET_CONTAINER_HeapCostType *cost)
{
  if (NULL == heap->root)
    return GNUNET_NO;
  if (NULL != element)
    *element = heap->root->element;
  if (NULL != cost)
    *cost = heap->root->cost;
  return GNUNET_YES;
}
 
 
unsigned int
GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap)
{
  return heap->size;
}
 
 
GNUNET_CONTAINER_HeapCostType
GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
                                     *node)
{
  return node->cost;
}
 
 
static int
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))
    return GNUNET_NO;
  if (GNUNET_YES !=
      node_iterator (heap, node->right_child, iterator, iterator_cls))
    return GNUNET_NO;
  return iterator (iterator_cls, node, node->element, node->cost);
}
 
 
void
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 *
GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
{
  struct GNUNET_CONTAINER_HeapNode *pos;
  void *element;
 
  if (heap->root == NULL)
    return NULL;
  pos = heap->walk_pos;
  if (pos == NULL)
    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;
  return element;
}
 
 
static void
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);
  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;
    }
    /* 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;
  }
  else
  {
    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);
}
 
 
struct GNUNET_CONTAINER_HeapNode *
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->heap = heap;
  node->element = element;
  node->cost = cost;
  heap->size++;
  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);
  return node;
}
 
 
void *
GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap)
{
  void *ret;
  struct GNUNET_CONTAINER_HeapNode *root;
 
  if (NULL == (root = heap->root))
    return 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;
  }
  else if (root->right_child == 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);
  }
  if (heap->walk_pos == root)
    heap->walk_pos = heap->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);
#endif
  return ret;
}
 
 
static void
remove_node (struct GNUNET_CONTAINER_HeapNode *node)
{
  struct GNUNET_CONTAINER_HeapNode *ancestor;
  struct GNUNET_CONTAINER_Heap *heap = node->heap;
 
  /* update 'size' of the ancestors */
  ancestor = node;
  while (NULL != (ancestor = ancestor->parent))
    ancestor->tree_size--;
 
  /* update 'size' of node itself */
  if (node->left_child != NULL)
    node->tree_size -= (1 + node->left_child->tree_size);
  if (node->right_child != NULL)
    node->tree_size -= (1 + node->right_child->tree_size);
 
  /* 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;
    }
  }
  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;
  GNUNET_assert (node->tree_size == 0);
  CHECK (heap->root);
}
 
 
void *
GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node)
{
  void *ret;
  struct GNUNET_CONTAINER_Heap *heap;
 
  heap = node->heap;
  CHECK (heap->root);
  if (heap->walk_pos == 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);
#if EXTRA_CHECKS
  CHECK (heap->root);
  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
                 (heap->size == heap->root->tree_size + 1));
#endif
  return ret;
}
 
 
void
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);
  node->cost = new_cost;
  if (NULL == heap->root)
    heap->root = node;
  else
    insert_node (heap,
                 heap->root,
                 node);
}
 
 
/* end of heap.c */