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