gnunet_container_lib.h

Go to the documentation of this file.

/*
     This file is part of GNUnet.
     Copyright (C) 2001-2015 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 "gnunet_common.h"
#if !defined (__GNUNET_UTIL_LIB_H_INSIDE__)
#error "Only <gnunet_util_lib.h> can be included directly."
#endif
 
#ifndef GNUNET_CONTAINER_LIB_H
#define GNUNET_CONTAINER_LIB_H
 
#ifdef __cplusplus
extern "C" {
#if 0 /* keep Emacsens' auto-indent happy */
}
#endif
#endif
 
 
/* add error and config prototypes */
 
#include "gnunet_crypto_lib.h"
 
 
int
GNUNET_try_compression (const char *data,
                        size_t old_size,
                        char **result,
                        size_t *new_size);
 
 
char *
GNUNET_decompress (const char *input, size_t input_size, size_t output_size);
 
 
/* ******************* bloomfilter ***************** */
 
struct GNUNET_CONTAINER_BloomFilter;
 
 
typedef int (*GNUNET_CONTAINER_HashCodeIterator) (void *cls,
                                                  struct GNUNET_HashCode *next);
 
 
struct GNUNET_CONTAINER_BloomFilter *
GNUNET_CONTAINER_bloomfilter_load (const char *filename,
                                   size_t size,
                                   unsigned int k);
 
 
struct GNUNET_CONTAINER_BloomFilter *
GNUNET_CONTAINER_bloomfilter_init (const char *data,
                                   size_t size,
                                   unsigned int k);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_bloomfilter_get_raw_data (
  const struct GNUNET_CONTAINER_BloomFilter *bf,
  char *data,
  size_t size);
 
 
bool
GNUNET_CONTAINER_bloomfilter_test (
  const struct GNUNET_CONTAINER_BloomFilter *bf,
  const struct GNUNET_HashCode *e);
 
 
void
GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf,
                                  const struct GNUNET_HashCode *e);
 
 
void
GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf,
                                     const struct GNUNET_HashCode *e);
 
 
struct GNUNET_CONTAINER_BloomFilter *
GNUNET_CONTAINER_bloomfilter_copy (
  const struct GNUNET_CONTAINER_BloomFilter *bf);
 
 
void
GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf);
 
 
size_t
GNUNET_CONTAINER_bloomfilter_get_element_addresses (
  const struct GNUNET_CONTAINER_BloomFilter *bf);
 
 
size_t
GNUNET_CONTAINER_bloomfilter_get_size (
  const struct GNUNET_CONTAINER_BloomFilter *bf);
 
 
void
GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
                                 const char *data,
                                 size_t size);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_bloomfilter_or2 (
  struct GNUNET_CONTAINER_BloomFilter *bf,
  const struct GNUNET_CONTAINER_BloomFilter *to_or);
 
 
void
GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf,
                                     GNUNET_CONTAINER_HashCodeIterator iterator,
                                     void *iterator_cls,
                                     size_t size,
                                     unsigned int k);
 
 
 
/* ******************************* HashMap **************************** */
 
struct GNUNET_CONTAINER_MultiHashMap;
 
struct GNUNET_CONTAINER_MultiHashMapIterator;
 
enum GNUNET_CONTAINER_MultiHashMapOption
{
  GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE,
 
  GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE,
 
  GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY,
 
  GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST
};
 
 
typedef enum GNUNET_GenericReturnValue
(*GNUNET_CONTAINER_MultiHashMapIteratorCallback)(
  void *cls,
  const struct GNUNET_HashCode *key,
  void *value);
 
 
struct GNUNET_CONTAINER_MultiHashMap *
GNUNET_CONTAINER_multihashmap_create (unsigned int len,
                                      int do_not_copy_keys);
 
 
void
GNUNET_CONTAINER_multihashmap_destroy (struct
                                       GNUNET_CONTAINER_MultiHashMap *map);
 
 
void *
GNUNET_CONTAINER_multihashmap_get (
  const struct GNUNET_CONTAINER_MultiHashMap *map,
  const struct GNUNET_HashCode *key);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map,
                                      const struct GNUNET_HashCode *key,
                                      const void *value);
 
int
GNUNET_CONTAINER_multihashmap_remove_all (
  struct GNUNET_CONTAINER_MultiHashMap *map,
  const struct GNUNET_HashCode *key);
 
 
unsigned int
GNUNET_CONTAINER_multihashmap_clear (struct GNUNET_CONTAINER_MultiHashMap *map);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multihashmap_contains (
  const struct GNUNET_CONTAINER_MultiHashMap *map,
  const struct GNUNET_HashCode *key);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multihashmap_contains_value (
  const struct GNUNET_CONTAINER_MultiHashMap *map,
  const struct GNUNET_HashCode *key,
  const void *value);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multihashmap_put (
  struct GNUNET_CONTAINER_MultiHashMap *map,
  const struct GNUNET_HashCode *key,
  void *value,
  enum GNUNET_CONTAINER_MultiHashMapOption opt);
 
unsigned int
GNUNET_CONTAINER_multihashmap_size (
  const struct GNUNET_CONTAINER_MultiHashMap *map);
 
 
int
GNUNET_CONTAINER_multihashmap_iterate (
  struct GNUNET_CONTAINER_MultiHashMap *map,
  GNUNET_CONTAINER_MultiHashMapIteratorCallback it,
  void *it_cls);
 
 
struct GNUNET_CONTAINER_MultiHashMapIterator *
GNUNET_CONTAINER_multihashmap_iterator_create (
  const struct GNUNET_CONTAINER_MultiHashMap *map);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multihashmap_iterator_next (
  struct GNUNET_CONTAINER_MultiHashMapIterator *iter,
  struct GNUNET_HashCode *key,
  const void **value);
 
 
void
GNUNET_CONTAINER_multihashmap_iterator_destroy (
  struct GNUNET_CONTAINER_MultiHashMapIterator *iter);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multihashmap_get_multiple (
  struct GNUNET_CONTAINER_MultiHashMap *map,
  const struct GNUNET_HashCode *key,
  GNUNET_CONTAINER_MultiHashMapIteratorCallback it,
  void *it_cls);
 
 
unsigned int
GNUNET_CONTAINER_multihashmap_get_random (
  const struct GNUNET_CONTAINER_MultiHashMap *map,
  GNUNET_CONTAINER_MultiHashMapIteratorCallback it,
  void *it_cls);
 
 
/* ***************** Version of Multihashmap for peer identities ****************** */
 
typedef enum GNUNET_GenericReturnValue
(*GNUNET_CONTAINER_PeerMapIterator)(
  void *cls,
  const struct GNUNET_PeerIdentity *key,
  void *value);
 
 
struct GNUNET_CONTAINER_MultiPeerMap;
 
 
struct GNUNET_CONTAINER_MultiPeerMap *
GNUNET_CONTAINER_multipeermap_create (unsigned int len, int do_not_copy_keys);
 
 
void
GNUNET_CONTAINER_multipeermap_destroy (
  struct GNUNET_CONTAINER_MultiPeerMap *map);
 
 
void *
GNUNET_CONTAINER_multipeermap_get (
  const struct GNUNET_CONTAINER_MultiPeerMap *map,
  const struct GNUNET_PeerIdentity *key);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map,
                                      const struct GNUNET_PeerIdentity *key,
                                      const void *value);
 
int
GNUNET_CONTAINER_multipeermap_remove_all (
  struct GNUNET_CONTAINER_MultiPeerMap *map,
  const struct GNUNET_PeerIdentity *key);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multipeermap_contains (
  const struct GNUNET_CONTAINER_MultiPeerMap *map,
  const struct GNUNET_PeerIdentity *key);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multipeermap_contains_value (
  const struct GNUNET_CONTAINER_MultiPeerMap *map,
  const struct GNUNET_PeerIdentity *key,
  const void *value);
 
 
int
GNUNET_CONTAINER_multipeermap_put (
  struct GNUNET_CONTAINER_MultiPeerMap *map,
  const struct GNUNET_PeerIdentity *key,
  void *value,
  enum GNUNET_CONTAINER_MultiHashMapOption opt);
 
 
unsigned int
GNUNET_CONTAINER_multipeermap_size (
  const struct GNUNET_CONTAINER_MultiPeerMap *map);
 
 
int
GNUNET_CONTAINER_multipeermap_iterate (
  struct GNUNET_CONTAINER_MultiPeerMap *map,
  GNUNET_CONTAINER_PeerMapIterator it,
  void *it_cls);
 
 
struct GNUNET_CONTAINER_MultiPeerMapIterator;
struct GNUNET_CONTAINER_MultiPeerMapIterator *
GNUNET_CONTAINER_multipeermap_iterator_create (
  const struct GNUNET_CONTAINER_MultiPeerMap *map);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multipeermap_iterator_next (
  struct GNUNET_CONTAINER_MultiPeerMapIterator *iter,
  struct GNUNET_PeerIdentity *key,
  const void **value);
 
 
void
GNUNET_CONTAINER_multipeermap_iterator_destroy (
  struct GNUNET_CONTAINER_MultiPeerMapIterator *iter);
 
 
int
GNUNET_CONTAINER_multipeermap_get_multiple (
  struct GNUNET_CONTAINER_MultiPeerMap *map,
  const struct GNUNET_PeerIdentity *key,
  GNUNET_CONTAINER_PeerMapIterator it,
  void *it_cls);
 
 
unsigned int
GNUNET_CONTAINER_multipeermap_get_random (
  const struct GNUNET_CONTAINER_MultiPeerMap *map,
  GNUNET_CONTAINER_PeerMapIterator it,
  void *it_cls);
 
 
/* ***************** Version of Multihashmap for short hashes ****************** */
 
typedef enum GNUNET_GenericReturnValue
(*GNUNET_CONTAINER_ShortmapIterator)(
  void *cls,
  const struct GNUNET_ShortHashCode *key,
  void *value);
 
 
struct GNUNET_CONTAINER_MultiShortmap;
 
 
struct GNUNET_CONTAINER_MultiShortmap *
GNUNET_CONTAINER_multishortmap_create (unsigned int len, int do_not_copy_keys);
 
 
void
GNUNET_CONTAINER_multishortmap_destroy (
  struct GNUNET_CONTAINER_MultiShortmap *map);
 
 
void *
GNUNET_CONTAINER_multishortmap_get (
  const struct GNUNET_CONTAINER_MultiShortmap *map,
  const struct GNUNET_ShortHashCode *key);
 
 
int
GNUNET_CONTAINER_multishortmap_remove (
  struct GNUNET_CONTAINER_MultiShortmap *map,
  const struct GNUNET_ShortHashCode *key,
  const void *value);
 
int
GNUNET_CONTAINER_multishortmap_remove_all (
  struct GNUNET_CONTAINER_MultiShortmap *map,
  const struct GNUNET_ShortHashCode *key);
 
 
int
GNUNET_CONTAINER_multishortmap_contains (
  const struct GNUNET_CONTAINER_MultiShortmap *map,
  const struct GNUNET_ShortHashCode *key);
 
 
int
GNUNET_CONTAINER_multishortmap_contains_value (
  const struct GNUNET_CONTAINER_MultiShortmap *map,
  const struct GNUNET_ShortHashCode *key,
  const void *value);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multishortmap_put (
  struct GNUNET_CONTAINER_MultiShortmap *map,
  const struct GNUNET_ShortHashCode *key,
  void *value,
  enum GNUNET_CONTAINER_MultiHashMapOption opt);
 
 
unsigned int
GNUNET_CONTAINER_multishortmap_size (
  const struct GNUNET_CONTAINER_MultiShortmap *map);
 
 
int
GNUNET_CONTAINER_multishortmap_iterate (
  struct GNUNET_CONTAINER_MultiShortmap *map,
  GNUNET_CONTAINER_ShortmapIterator it,
  void *it_cls);
 
 
struct GNUNET_CONTAINER_MultiShortmapIterator;
 
 
struct GNUNET_CONTAINER_MultiShortmapIterator *
GNUNET_CONTAINER_multishortmap_iterator_create (
  const struct GNUNET_CONTAINER_MultiShortmap *map);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multishortmap_iterator_next (
  struct GNUNET_CONTAINER_MultiShortmapIterator *iter,
  struct GNUNET_ShortHashCode *key,
  const void **value);
 
 
void
GNUNET_CONTAINER_multishortmap_iterator_destroy (
  struct GNUNET_CONTAINER_MultiShortmapIterator *iter);
 
 
int
GNUNET_CONTAINER_multishortmap_get_multiple (
  struct GNUNET_CONTAINER_MultiShortmap *map,
  const struct GNUNET_ShortHashCode *key,
  GNUNET_CONTAINER_ShortmapIterator it,
  void *it_cls);
 
 
unsigned int
GNUNET_CONTAINER_multishortmap_get_random (
  const struct GNUNET_CONTAINER_MultiShortmap *map,
  GNUNET_CONTAINER_ShortmapIterator it,
  void *it_cls);
 
 
/* ***************** Version of Multihashmap for UUIDs ****************** */
 
 
typedef enum GNUNET_GenericReturnValue
(*GNUNET_CONTAINER_MultiUuidmapIteratorCallback)(
  void *cls,
  const struct GNUNET_Uuid *key,
  void *value);
 
 
struct GNUNET_CONTAINER_MultiUuidmap;
 
 
struct GNUNET_CONTAINER_MultiUuidmap *
GNUNET_CONTAINER_multiuuidmap_create (unsigned int len, int do_not_copy_keys);
 
 
void
GNUNET_CONTAINER_multiuuidmap_destroy (
  struct GNUNET_CONTAINER_MultiUuidmap *map);
 
 
void *
GNUNET_CONTAINER_multiuuidmap_get (
  const struct GNUNET_CONTAINER_MultiUuidmap *map,
  const struct GNUNET_Uuid *key);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multiuuidmap_remove (struct GNUNET_CONTAINER_MultiUuidmap *map,
                                      const struct GNUNET_Uuid *key,
                                      const void *value);
 
int
GNUNET_CONTAINER_multiuuidmap_remove_all (
  struct GNUNET_CONTAINER_MultiUuidmap *map,
  const struct GNUNET_Uuid *key);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multiuuidmap_contains (
  const struct GNUNET_CONTAINER_MultiUuidmap *map,
  const struct GNUNET_Uuid *key);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multiuuidmap_contains_value (
  const struct GNUNET_CONTAINER_MultiUuidmap *map,
  const struct GNUNET_Uuid *key,
  const void *value);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multiuuidmap_put (
  struct GNUNET_CONTAINER_MultiUuidmap *map,
  const struct GNUNET_Uuid *key,
  void *value,
  enum GNUNET_CONTAINER_MultiHashMapOption opt);
 
 
unsigned int
GNUNET_CONTAINER_multiuuidmap_size (
  const struct GNUNET_CONTAINER_MultiUuidmap *map);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multiuuidmap_iterate (
  struct GNUNET_CONTAINER_MultiUuidmap *map,
  GNUNET_CONTAINER_MultiUuidmapIteratorCallback it,
  void *it_cls);
 
 
struct GNUNET_CONTAINER_MultiUuidmapIterator;
 
 
struct GNUNET_CONTAINER_MultiUuidmapIterator *
GNUNET_CONTAINER_multiuuidmap_iterator_create (
  const struct GNUNET_CONTAINER_MultiUuidmap *map);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multiuuidmap_iterator_next (
  struct GNUNET_CONTAINER_MultiUuidmapIterator *iter,
  struct GNUNET_Uuid *key,
  const void **value);
 
 
void
GNUNET_CONTAINER_multiuuidmap_iterator_destroy (
  struct GNUNET_CONTAINER_MultiUuidmapIterator *iter);
 
 
int
GNUNET_CONTAINER_multiuuidmap_get_multiple (
  struct GNUNET_CONTAINER_MultiUuidmap *map,
  const struct GNUNET_Uuid *key,
  GNUNET_CONTAINER_MultiUuidmapIteratorCallback it,
  void *it_cls);
 
 
unsigned int
GNUNET_CONTAINER_multiuuidmap_get_random (
  const struct GNUNET_CONTAINER_MultiUuidmap *map,
  GNUNET_CONTAINER_MultiUuidmapIteratorCallback it,
  void *it_cls);
 
 
/* Version of multihashmap with 32 bit keys */
 
struct GNUNET_CONTAINER_MultiHashMap32;
 
 
struct GNUNET_CONTAINER_MultiHashMap32Iterator;
 
 
typedef enum GNUNET_GenericReturnValue
(*GNUNET_CONTAINER_MultiHashMapIterator32Callback)(
  void *cls,
  uint32_t key,
  void *value);
 
 
struct GNUNET_CONTAINER_MultiHashMap32 *
GNUNET_CONTAINER_multihashmap32_create (unsigned int len);
 
 
void
GNUNET_CONTAINER_multihashmap32_destroy (
  struct GNUNET_CONTAINER_MultiHashMap32 *map);
 
 
unsigned int
GNUNET_CONTAINER_multihashmap32_size (
  const struct GNUNET_CONTAINER_MultiHashMap32 *map);
 
 
void *
GNUNET_CONTAINER_multihashmap32_get (
  const struct GNUNET_CONTAINER_MultiHashMap32 *map,
  uint32_t key);
 
 
int
GNUNET_CONTAINER_multihashmap32_iterate (
  struct GNUNET_CONTAINER_MultiHashMap32 *map,
  GNUNET_CONTAINER_MultiHashMapIterator32Callback it,
  void *it_cls);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multihashmap32_remove (
  struct GNUNET_CONTAINER_MultiHashMap32 *map,
  uint32_t key,
  const void *value);
 
 
int
GNUNET_CONTAINER_multihashmap32_remove_all (
  struct GNUNET_CONTAINER_MultiHashMap32 *map,
  uint32_t key);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multihashmap32_contains (
  const struct GNUNET_CONTAINER_MultiHashMap32 *map,
  uint32_t key);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multihashmap32_contains_value (
  const struct GNUNET_CONTAINER_MultiHashMap32 *map,
  uint32_t key,
  const void *value);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multihashmap32_put (
  struct GNUNET_CONTAINER_MultiHashMap32 *map,
  uint32_t key,
  void *value,
  enum GNUNET_CONTAINER_MultiHashMapOption opt);
 
 
int
GNUNET_CONTAINER_multihashmap32_get_multiple (
  struct GNUNET_CONTAINER_MultiHashMap32 *map,
  uint32_t key,
  GNUNET_CONTAINER_MultiHashMapIterator32Callback it,
  void *it_cls);
 
 
struct GNUNET_CONTAINER_MultiHashMap32Iterator *
GNUNET_CONTAINER_multihashmap32_iterator_create (
  const struct GNUNET_CONTAINER_MultiHashMap32 *map);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multihashmap32_iterator_next (
  struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
  uint32_t *key,
  const void **value);
 
 
void
GNUNET_CONTAINER_multihashmap32_iterator_destroy (
  struct GNUNET_CONTAINER_MultiHashMapIterator *iter);
 
 
/* ******************** doubly-linked list *************** */
/* To avoid mistakes: head->prev == tail->next == NULL     */
 
#define GNUNET_CONTAINER_DLL_insert(head, tail, element)                \
  do                                                                    \
  {                                                                     \
    GNUNET_assert (((element)->prev == NULL) && ((head) != (element))); \
    GNUNET_assert (((element)->next == NULL) && ((tail) != (element))); \
    (element)->next = (head);                                           \
    (element)->prev = NULL;                                             \
    if ((tail) == NULL)                                                 \
    (tail) = element;                                                 \
    else                                                                \
    (head)->prev = element;                                           \
    (head) = (element);                                                 \
  } while (0)
 
 
#define GNUNET_CONTAINER_DLL_insert_tail(head, tail, element)           \
  do                                                                    \
  {                                                                     \
    GNUNET_assert (((element)->prev == NULL) && ((head) != (element))); \
    GNUNET_assert (((element)->next == NULL) && ((tail) != (element))); \
    (element)->prev = (tail);                                           \
    (element)->next = NULL;                                             \
    if ((head) == NULL)                                                 \
    (head) = element;                                                 \
    else                                                                \
    (tail)->next = element;                                           \
    (tail) = (element);                                                 \
  } while (0)
 
 
#define GNUNET_CONTAINER_DLL_insert_after(head, tail, other, element)   \
  do                                                                    \
  {                                                                     \
    GNUNET_assert (((element)->prev == NULL) && ((head) != (element))); \
    GNUNET_assert (((element)->next == NULL) && ((tail) != (element))); \
    (element)->prev = (other);                                          \
    if (NULL == other)                                                  \
    {                                                                   \
      (element)->next = (head);                                         \
      (head) = (element);                                               \
    }                                                                   \
    else                                                                \
    {                                                                   \
      (element)->next = (other)->next;                                  \
      (other)->next = (element);                                        \
    }                                                                   \
    if (NULL == (element)->next)                                        \
    (tail) = (element);                                               \
    else                                                                \
    (element)->next->prev = (element);                                \
  } while (0)
 
 
#define GNUNET_CONTAINER_DLL_insert_before(head, tail, other, element)  \
  do                                                                    \
  {                                                                     \
    GNUNET_assert (((element)->prev == NULL) && ((head) != (element))); \
    GNUNET_assert (((element)->next == NULL) && ((tail) != (element))); \
    (element)->next = (other);                                          \
    if (NULL == other)                                                  \
    {                                                                   \
      (element)->prev = (tail);                                         \
      (tail) = (element);                                               \
    }                                                                   \
    else                                                                \
    {                                                                   \
      (element)->prev = (other)->prev;                                  \
      (other)->prev = (element);                                        \
    }                                                                   \
    if (NULL == (element)->prev)                                        \
    (head) = (element);                                               \
    else                                                                \
    (element)->prev->next = (element);                                \
  } while (0)
 
 
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)                \
  do                                                                    \
  {                                                                     \
    GNUNET_assert (((element)->prev != NULL) || ((head) == (element))); \
    GNUNET_assert (((element)->next != NULL) || ((tail) == (element))); \
    if ((element)->prev == NULL)                                        \
    (head) = (element)->next;                                         \
    else                                                                \
    (element)->prev->next = (element)->next;                          \
    if ((element)->next == NULL)                                        \
    (tail) = (element)->prev;                                         \
    else                                                                \
    (element)->next->prev = (element)->prev;                          \
    (element)->next = NULL;                                             \
    (element)->prev = NULL;                                             \
  } while (0)
 
 
/* ************ Multi-DLL interface, allows DLL elements to be
   in multiple lists at the same time *********************** */
 
#define GNUNET_CONTAINER_MDLL_insert(mdll, head, tail, element)                \
  do                                                                           \
  {                                                                            \
    GNUNET_assert (((element)->prev_ ## mdll == NULL) && ((head) != (element))); \
    GNUNET_assert (((element)->next_ ## mdll == NULL) && ((tail) != (element))); \
    (element)->next_ ## mdll = (head);                                           \
    (element)->prev_ ## mdll = NULL;                                             \
    if ((tail) == NULL)                                                        \
    (tail) = element;                                                        \
    else                                                                       \
    (head)->prev_ ## mdll = element;                                           \
    (head) = (element);                                                        \
  } while (0)
 
 
#define GNUNET_CONTAINER_MDLL_insert_tail(mdll, head, tail, element)           \
  do                                                                           \
  {                                                                            \
    GNUNET_assert (((element)->prev_ ## mdll == NULL) && ((head) != (element))); \
    GNUNET_assert (((element)->next_ ## mdll == NULL) && ((tail) != (element))); \
    (element)->prev_ ## mdll = (tail);                                           \
    (element)->next_ ## mdll = NULL;                                             \
    if ((head) == NULL)                                                        \
    (head) = element;                                                        \
    else                                                                       \
    (tail)->next_ ## mdll = element;                                           \
    (tail) = (element);                                                        \
  } while (0)
 
 
#define GNUNET_CONTAINER_MDLL_insert_after(mdll, head, tail, other, element)   \
  do                                                                           \
  {                                                                            \
    GNUNET_assert (((element)->prev_ ## mdll == NULL) && ((head) != (element))); \
    GNUNET_assert (((element)->next_ ## mdll == NULL) && ((tail) != (element))); \
    (element)->prev_ ## mdll = (other);                                          \
    if (NULL == other)                                                         \
    {                                                                          \
      (element)->next_ ## mdll = (head);                                         \
      (head) = (element);                                                      \
    }                                                                          \
    else                                                                       \
    {                                                                          \
      (element)->next_ ## mdll = (other)->next_ ## mdll;                           \
      (other)->next_ ## mdll = (element);                                        \
    }                                                                          \
    if (NULL == (element)->next_ ## mdll)                                        \
    (tail) = (element);                                                      \
    else                                                                       \
    (element)->next_ ## mdll->prev_ ## mdll = (element);                         \
  } while (0)
 
 
#define GNUNET_CONTAINER_MDLL_insert_before(mdll, head, tail, other, element)  \
  do                                                                           \
  {                                                                            \
    GNUNET_assert (((element)->prev_ ## mdll == NULL) && ((head) != (element))); \
    GNUNET_assert (((element)->next_ ## mdll == NULL) && ((tail) != (element))); \
    (element)->next_ ## mdll = (other);                                          \
    if (NULL == other)                                                         \
    {                                                                          \
      (element)->prev = (tail);                                                \
      (tail) = (element);                                                      \
    }                                                                          \
    else                                                                       \
    {                                                                          \
      (element)->prev_ ## mdll = (other)->prev_ ## mdll;                           \
      (other)->prev_ ## mdll = (element);                                        \
    }                                                                          \
    if (NULL == (element)->prev_ ## mdll)                                        \
    (head) = (element);                                                      \
    else                                                                       \
    (element)->prev_ ## mdll->next_ ## mdll = (element);                         \
  } while (0)
 
 
#define GNUNET_CONTAINER_MDLL_remove(mdll, head, tail, element)                \
  do                                                                           \
  {                                                                            \
    GNUNET_assert (((element)->prev_ ## mdll != NULL) || ((head) == (element))); \
    GNUNET_assert (((element)->next_ ## mdll != NULL) || ((tail) == (element))); \
    if ((element)->prev_ ## mdll == NULL)                                        \
    (head) = (element)->next_ ## mdll;                                         \
    else                                                                       \
    (element)->prev_ ## mdll->next_ ## mdll = (element)->next_ ## mdll;            \
    if ((element)->next_ ## mdll == NULL)                                        \
    (tail) = (element)->prev_ ## mdll;                                         \
    else                                                                       \
    (element)->next_ ## mdll->prev_ ## mdll = (element)->prev_ ## mdll;            \
    (element)->next_ ## mdll = NULL;                                             \
    (element)->prev_ ## mdll = NULL;                                             \
  } while (0)
 
 
#define GNUNET_CONTAINER_DLL_insert_sorted(TYPE,                            \
                                           comparator,                      \
                                           comparator_cls,                  \
                                           head,                            \
                                           tail,                            \
                                           element)                         \
  do                                                                        \
  {                                                                         \
    if ((NULL == head) || (0 < comparator (comparator_cls, element, head))) \
    {                                                                       \
      /* insert at head, element < head */                                  \
      GNUNET_CONTAINER_DLL_insert (head, tail, element);                    \
    }                                                                       \
    else                                                                    \
    {                                                                       \
      TYPE *pos;                                                            \
                                                                            \
      for (pos = head; NULL != pos; pos = pos->next)                        \
      if (0 < comparator (comparator_cls, element, pos))                  \
      break;     /* element < pos */                                        \
      if (NULL == pos)     /* => element > tail */                              \
      {                                                                     \
        GNUNET_CONTAINER_DLL_insert_tail (head, tail, element);             \
      }                                                                     \
      else     /* prev < element < pos */                                       \
      {                                                                     \
        GNUNET_CONTAINER_DLL_insert_after (head, tail, pos->prev, element); \
      }                                                                     \
    }                                                                       \
  } while (0)
 
 
/* ******************** Heap *************** */
 
 
typedef uint64_t GNUNET_CONTAINER_HeapCostType;
 
 
enum GNUNET_CONTAINER_HeapOrder
{
  GNUNET_CONTAINER_HEAP_ORDER_MAX,
 
  GNUNET_CONTAINER_HEAP_ORDER_MIN
};
 
 
struct GNUNET_CONTAINER_Heap;
 
 
struct GNUNET_CONTAINER_HeapNode;
 
 
struct GNUNET_CONTAINER_Heap *
GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order);
 
 
void
GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap);
 
 
void *
GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap);
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap,
                             void **element,
                             GNUNET_CONTAINER_HeapCostType *cost);
 
 
unsigned int
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);
 
 
typedef enum GNUNET_GenericReturnValue
(*GNUNET_CONTAINER_HeapIterator)(
  void *cls,
  struct GNUNET_CONTAINER_HeapNode *node,
  void *element,
  GNUNET_CONTAINER_HeapCostType cost);
 
 
void
GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
                               GNUNET_CONTAINER_HeapIterator iterator,
                               void *iterator_cls);
 
void *
GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap);
 
 
struct GNUNET_CONTAINER_HeapNode *
GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
                              void *element,
                              GNUNET_CONTAINER_HeapCostType cost);
 
 
void *
GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap);
 
 
void *
GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node);
 
 
void
GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_HeapNode *node,
                                   GNUNET_CONTAINER_HeapCostType new_cost);
 
 
#if 0 /* keep Emacsens' auto-indent happy */
{
#endif
#ifdef __cplusplus
}
#endif
 
 
/* ifndef GNUNET_CONTAINER_LIB_H */
#endif
 /* end of group addition */
 
/* end of gnunet_container_lib.h */