src/rps/gnunet-service-rps_custommap.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C)
   4
   5      GNUnet is free software: you can redistribute it and/or modify it
   6      under the terms of the GNU Affero General Public License as published
   7      by the Free Software Foundation, either version 3 of the License,
   8      or (at your option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      Affero General Public License for more details.
  14 */
  15
  16 /**
  17  * @file rps/gnunet-service-rps_custommap.c
  18  * @brief utilities for managing (information about) peers
  19  * @author Julius Bünger
  20  */
  21 #include "platform.h"
  22 #include "gnunet_util_lib.h"
  23 #include "gnunet-service-rps_custommap.h"
  24 #include <inttypes.h>
  25
  26 #define LOG(kind, ...) GNUNET_log_from(kind,"rps-peers",__VA_ARGS__)
  27
  28
  29 /**
  30  * Peer map to store peers with specialised use-cases (push_list, pull_list,
  31  * view, ...)
  32  *
  33  * It is aimed for use as unordered list-like structures that can be indexed.
  34  * Main use-case:
  35  *
  36  *  permut = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_STRONG,
  37  *                                         CustomPeerMap_size (peer_map));
  38  *  for (i = 0; i < some_border; i++)
  39  *    some_array[i] = *CustomPeerMap_get_peer_by_index (peer_map, permut[i]);
  40  *  for (i = some_border; i < CustomPeerMap_size (peer_map); i++)
  41  *    other_array[i-some_border] =
  42  *      *CustomPeerMap_get_peer_by_index (peer_map, permut[i]);
  43  *
  44  * This list is expected to
  45  * - be altered in small steps frequently
  46  * - be cleared regularily
  47  * - often being queried whether a peer is contained
  48  * - alter indices of peers
  49  * - contain continous indices 0 <= i < len
  50  * - not contain duplicate peers
  51  */
  52 struct CustomPeerMap
  53 {
  54   /**
  55    * Multihashmap to be able to access a random index
  56    */
  57   struct GNUNET_CONTAINER_MultiHashMap32 *hash_map;
  58
  59   /**
  60    * Peermap to quickly check whether a peer is contained
  61    */
  62   struct GNUNET_CONTAINER_MultiPeerMap *peer_map;
  63 };
  64
  65
  66 /**
  67  * Create an empty peermap.
  68  *
  69  * @param len the initial length for the internal maps
  70  *
  71  * @return the newly created custom peer map
  72  */
  73 struct CustomPeerMap *
  74 CustomPeerMap_create (unsigned int len)
  75 {
  76   struct CustomPeerMap *c_peer_map;
  77
  78   c_peer_map = GNUNET_new (struct CustomPeerMap);
  79   c_peer_map->hash_map = GNUNET_CONTAINER_multihashmap32_create (len);
  80   c_peer_map->peer_map = GNUNET_CONTAINER_multipeermap_create (len, GNUNET_NO);
  81   return c_peer_map;
  82 }
  83
  84 /**
  85  * Get the size of the custom peer map
  86  *
  87  * @param c_peer_map the custom peer map to look in
  88  *
  89  * @return size of the map
  90  */
  91 int
  92 CustomPeerMap_size (const struct CustomPeerMap *c_peer_map)
  93 {
  94   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
  95                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
  96   return GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map);
  97 }
  98
  99 /**
 100  * Insert peer into the custom peer map
 101  *
 102  * @param c_peer_map the custom peer map to insert peer
 103  * @param peer the peer to insert
 104  *
 105  * @return GNUNET_OK if map did not contain peer previously
 106  *         GNUNET_NO if map did contain peer previously
 107  */
 108 int
 109 CustomPeerMap_put (const struct CustomPeerMap *c_peer_map,
 110                    const struct GNUNET_PeerIdentity *peer)
 111 {
 112   uint32_t *index;
 113   struct GNUNET_PeerIdentity *p;
 114
 115   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 116                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 117   if (GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains (c_peer_map->peer_map,
 118                                                            peer))
 119   {
 120     /* Need to store the index of the peer in the peermap to be able to remove
 121      * it properly */
 122     index = GNUNET_new (uint32_t);
 123     *index = CustomPeerMap_size (c_peer_map);
 124     p = GNUNET_new (struct GNUNET_PeerIdentity);
 125     *p = *peer;
 126     GNUNET_assert (p != peer);
 127     GNUNET_assert (0 == memcmp (p, peer, sizeof(struct GNUNET_PeerIdentity)));
 128     GNUNET_CONTAINER_multipeermap_put (c_peer_map->peer_map, p, index,
 129         GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
 130     GNUNET_CONTAINER_multihashmap32_put (c_peer_map->hash_map, *index, p,
 131         GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
 132     GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 133                    GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 134     return GNUNET_OK;
 135   }
 136   return GNUNET_NO;
 137 }
 138
 139 /**
 140  * Check whether custom peer map contains a peer
 141  *
 142  * @param c_peer_map the custom peer map to look in
 143  * @param peer the peer to check for
 144  *
 145  * @return GNUNET_OK if map contains peer
 146  *         GNUNET_NO  otherwise
 147  */
 148 int
 149 CustomPeerMap_contains_peer (const struct CustomPeerMap *c_peer_map,
 150                              const struct GNUNET_PeerIdentity *peer)
 151 {
 152   return GNUNET_CONTAINER_multipeermap_contains (c_peer_map->peer_map, peer);
 153 }
 154
 155 /**
 156  * Get index of peer in custom peer map
 157  *
 158  * @param c_peer_map the custom peer map to look in
 159  * @param peer the peer to get the index from
 160  *
 161  * @return the index
 162  */
 163 static uint32_t *
 164 CustomPeerMap_get_index_pointer (const struct CustomPeerMap *c_peer_map,
 165                                  const struct GNUNET_PeerIdentity *peer)
 166 {
 167   uint32_t *index;
 168
 169   GNUNET_assert (GNUNET_YES == CustomPeerMap_contains_peer (c_peer_map, peer));
 170   index = GNUNET_CONTAINER_multipeermap_get (c_peer_map->peer_map, peer);
 171   return index;
 172 }
 173
 174 /**
 175  * Remove peer from custom peer map
 176  *
 177  * @param c_peer_map the custom peer map to remove the peer from
 178  * @param peer the peer to remove
 179  *
 180  * @return GNUNET_OK if map contained peer and removed it successfully
 181  *         GNUNET_NO if map does not contain peer
 182  */
 183 int
 184 CustomPeerMap_remove_peer (const struct CustomPeerMap *c_peer_map,
 185                            const struct GNUNET_PeerIdentity *peer)
 186 {
 187   uint32_t *index;
 188   struct GNUNET_PeerIdentity *p;
 189   uint32_t *last_index;
 190   struct GNUNET_PeerIdentity *last_p;
 191
 192   if (GNUNET_NO == CustomPeerMap_contains_peer (c_peer_map, peer))
 193   {
 194     return GNUNET_NO;
 195   }
 196   index = CustomPeerMap_get_index_pointer (c_peer_map, peer);
 197   GNUNET_assert (*index < CustomPeerMap_size (c_peer_map));
 198   /* Need to get the pointer stored in the hashmap to free it */
 199   p = GNUNET_CONTAINER_multihashmap32_get (c_peer_map->hash_map, *index);
 200   GNUNET_assert (NULL != p);
 201   GNUNET_CONTAINER_multihashmap32_remove_all (c_peer_map->hash_map, *index);
 202   GNUNET_CONTAINER_multipeermap_remove_all (c_peer_map->peer_map, peer);
 203   if (*index != CustomPeerMap_size (c_peer_map))
 204   { /* fill 'gap' with peer at last index */
 205     last_p =
 206       GNUNET_CONTAINER_multihashmap32_get (c_peer_map->hash_map,
 207                                            CustomPeerMap_size (c_peer_map));
 208     GNUNET_assert (NULL != last_p);
 209     last_index = GNUNET_CONTAINER_multipeermap_get (c_peer_map->peer_map, last_p);
 210     GNUNET_assert (NULL != last_index);
 211     GNUNET_assert (CustomPeerMap_size (c_peer_map) == *last_index);
 212     GNUNET_CONTAINER_multihashmap32_put (c_peer_map->hash_map, *index, last_p,
 213         GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
 214     GNUNET_CONTAINER_multihashmap32_remove_all (c_peer_map->hash_map, *last_index);
 215     *last_index = *index;
 216   }
 217   GNUNET_free (index);
 218   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 219                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 220   return GNUNET_OK;
 221 }
 222
 223 /**
 224  * Get a peer by index
 225  *
 226  * @param c_peer_map the custom peer map to look in
 227  * @param index the index of the peer to get
 228  *
 229  * @return peer to the corresponding index.
 230  *         if this index is not known, return NULL
 231  */
 232 struct GNUNET_PeerIdentity *
 233 CustomPeerMap_get_peer_by_index (const struct CustomPeerMap *c_peer_map,
 234                                  uint32_t index)
 235 {
 236   if (GNUNET_YES ==
 237       GNUNET_CONTAINER_multihashmap32_contains (c_peer_map->hash_map, index))
 238   {
 239     return GNUNET_CONTAINER_multihashmap32_get (c_peer_map->hash_map, index);
 240   }
 241   return NULL;
 242 }
 243
 244 /**
 245  * Remove peer from custom peer map by index
 246  *
 247  * @param c_peer_map the custom peer map to remove the peer from
 248  * @param index the index of the peer to remove
 249  *
 250  * @return GNUNET_OK if map contained peer and removed it successfully
 251  *         GNUNET_NO if map does not contain (index of) peer
 252  */
 253 int
 254 CustomPeerMap_remove_peer_by_index (const struct CustomPeerMap *c_peer_map,
 255                                     uint32_t index)
 256 {
 257   uint32_t *index_p;
 258   struct GNUNET_PeerIdentity *peer;
 259
 260   if (index >= CustomPeerMap_size (c_peer_map))
 261   {
 262     return GNUNET_NO;
 263   }
 264   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 265                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 266   if (GNUNET_NO ==
 267       GNUNET_CONTAINER_multihashmap32_contains (c_peer_map->hash_map, index))
 268   {
 269     return GNUNET_NO;
 270   }
 271   peer = CustomPeerMap_get_peer_by_index (c_peer_map, index);
 272   GNUNET_assert (NULL != peer);
 273   index_p = CustomPeerMap_get_index_pointer (c_peer_map, peer);
 274   GNUNET_assert (index == *index_p);
 275   CustomPeerMap_remove_peer (c_peer_map, peer);
 276   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 277                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 278   return GNUNET_OK;
 279 }
 280
 281 /**
 282  * Clear the custom peer map
 283  *
 284  * @param c_peer_map the custom peer map to look in
 285  *
 286  * @return size of the map
 287  */
 288 void
 289 CustomPeerMap_clear (const struct CustomPeerMap *c_peer_map)
 290 {
 291   while (0 < CustomPeerMap_size (c_peer_map))
 292   {
 293     GNUNET_assert (GNUNET_YES ==
 294         GNUNET_CONTAINER_multihashmap32_contains (c_peer_map->hash_map,
 295           CustomPeerMap_size (c_peer_map) -1));
 296     GNUNET_assert (GNUNET_OK ==
 297         CustomPeerMap_remove_peer_by_index (c_peer_map,
 298                                             CustomPeerMap_size (c_peer_map) -1));
 299   }
 300   GNUNET_assert (0 == CustomPeerMap_size (c_peer_map));
 301 }
 302
 303 /**
 304  * Destroy peermap.
 305  *
 306  * @param c_peer_map the map to destroy
 307  */
 308 void
 309 CustomPeerMap_destroy (struct CustomPeerMap *c_peer_map)
 310 {
 311   CustomPeerMap_clear (c_peer_map);
 312   GNUNET_CONTAINER_multihashmap32_destroy (c_peer_map->hash_map);
 313   GNUNET_CONTAINER_multipeermap_destroy   (c_peer_map->peer_map);
 314   GNUNET_free (c_peer_map);
 315 }
 316
 317 /* end of gnunet-service-rps_custommap.c */