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      You should have received a copy of the GNU Affero General Public License
  16      along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17 */
  18
  19 /**
  20  * @file rps/gnunet-service-rps_custommap.c
  21  * @brief utilities for managing (information about) peers
  22  * @author Julius Bünger
  23  */
  24 #include "platform.h"
  25 #include "gnunet_util_lib.h"
  26 #include "gnunet-service-rps_custommap.h"
  27 #include <inttypes.h>
  28
  29 #define LOG(kind, ...) GNUNET_log_from(kind,"rps-peers",__VA_ARGS__)
  30
  31
  32 /**
  33  * Peer map to store peers with specialised use-cases (push_list, pull_list,
  34  * view, ...)
  35  *
  36  * It is aimed for use as unordered list-like structures that can be indexed.
  37  * Main use-case:
  38  *
  39  *  permut = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_STRONG,
  40  *                                         CustomPeerMap_size (peer_map));
  41  *  for (i = 0; i < some_border; i++)
  42  *    some_array[i] = *CustomPeerMap_get_peer_by_index (peer_map, permut[i]);
  43  *  for (i = some_border; i < CustomPeerMap_size (peer_map); i++)
  44  *    other_array[i-some_border] =
  45  *      *CustomPeerMap_get_peer_by_index (peer_map, permut[i]);
  46  *
  47  * This list is expected to
  48  * - be altered in small steps frequently
  49  * - be cleared regularily
  50  * - often being queried whether a peer is contained
  51  * - alter indices of peers
  52  * - contain continous indices 0 <= i < len
  53  * - not contain duplicate peers
  54  */
  55 struct CustomPeerMap
  56 {
  57   /**
  58    * Multihashmap to be able to access a random index
  59    */
  60   struct GNUNET_CONTAINER_MultiHashMap32 *hash_map;
  61
  62   /**
  63    * Peermap to quickly check whether a peer is contained
  64    */
  65   struct GNUNET_CONTAINER_MultiPeerMap *peer_map;
  66 };
  67
  68
  69 /**
  70  * Create an empty peermap.
  71  *
  72  * @param len the initial length for the internal maps
  73  *
  74  * @return the newly created custom peer map
  75  */
  76 struct CustomPeerMap *
  77 CustomPeerMap_create (unsigned int len)
  78 {
  79   struct CustomPeerMap *c_peer_map;
  80
  81   c_peer_map = GNUNET_new (struct CustomPeerMap);
  82   c_peer_map->hash_map = GNUNET_CONTAINER_multihashmap32_create (len);
  83   c_peer_map->peer_map = GNUNET_CONTAINER_multipeermap_create (len, GNUNET_NO);
  84   return c_peer_map;
  85 }
  86
  87 /**
  88  * Get the size of the custom peer map
  89  *
  90  * @param c_peer_map the custom peer map to look in
  91  *
  92  * @return size of the map
  93  */
  94 int
  95 CustomPeerMap_size (const struct CustomPeerMap *c_peer_map)
  96 {
  97   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
  98                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
  99   return GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map);
 100 }
 101
 102 /**
 103  * Insert peer into the custom peer map
 104  *
 105  * @param c_peer_map the custom peer map to insert peer
 106  * @param peer the peer to insert
 107  *
 108  * @return GNUNET_OK if map did not contain peer previously
 109  *         GNUNET_NO if map did contain peer previously
 110  */
 111 int
 112 CustomPeerMap_put (const struct CustomPeerMap *c_peer_map,
 113                    const struct GNUNET_PeerIdentity *peer)
 114 {
 115   uint32_t *index;
 116   struct GNUNET_PeerIdentity *p;
 117
 118   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 119                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 120   if (GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains (c_peer_map->peer_map,
 121                                                            peer))
 122   {
 123     /* Need to store the index of the peer in the peermap to be able to remove
 124      * it properly */
 125     index = GNUNET_new (uint32_t);
 126     *index = CustomPeerMap_size (c_peer_map);
 127     p = GNUNET_new (struct GNUNET_PeerIdentity);
 128     *p = *peer;
 129     GNUNET_assert (p != peer);
 130     GNUNET_assert (0 == memcmp (p, peer, sizeof(struct GNUNET_PeerIdentity)));
 131     GNUNET_CONTAINER_multipeermap_put (c_peer_map->peer_map, p, 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   // TODO wrong peerid?
 206   GNUNET_CONTAINER_multipeermap_remove_all (c_peer_map->peer_map, peer);
 207   if (*index != CustomPeerMap_size (c_peer_map))
 208   { /* fill 'gap' with peer at last index */
 209     last_p =
 210       GNUNET_CONTAINER_multihashmap32_get (c_peer_map->hash_map,
 211                                            CustomPeerMap_size (c_peer_map));
 212     GNUNET_assert (NULL != last_p);
 213     last_index = GNUNET_CONTAINER_multipeermap_get (c_peer_map->peer_map, last_p);
 214     GNUNET_assert (NULL != last_index);
 215     GNUNET_assert (CustomPeerMap_size (c_peer_map) == *last_index);
 216     GNUNET_CONTAINER_multihashmap32_put (c_peer_map->hash_map, *index, last_p,
 217         GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
 218     GNUNET_CONTAINER_multihashmap32_remove_all (c_peer_map->hash_map, *last_index);
 219     *last_index = *index;
 220   }
 221   GNUNET_free (index);
 222   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 223                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 224   GNUNET_free (p);
 225   return GNUNET_OK;
 226 }
 227
 228 /**
 229  * Get a peer by index
 230  *
 231  * @param c_peer_map the custom peer map to look in
 232  * @param index the index of the peer to get
 233  *
 234  * @return peer to the corresponding index.
 235  *         if this index is not known, return NULL
 236  */
 237 struct GNUNET_PeerIdentity *
 238 CustomPeerMap_get_peer_by_index (const struct CustomPeerMap *c_peer_map,
 239                                  uint32_t index)
 240 {
 241   if (GNUNET_YES ==
 242       GNUNET_CONTAINER_multihashmap32_contains (c_peer_map->hash_map, index))
 243   {
 244     return GNUNET_CONTAINER_multihashmap32_get (c_peer_map->hash_map, index);
 245   }
 246   return NULL;
 247 }
 248
 249 /**
 250  * Remove peer from custom peer map by index
 251  *
 252  * @param c_peer_map the custom peer map to remove the peer from
 253  * @param index the index of the peer to remove
 254  *
 255  * @return GNUNET_OK if map contained peer and removed it successfully
 256  *         GNUNET_NO if map does not contain (index of) peer
 257  */
 258 int
 259 CustomPeerMap_remove_peer_by_index (const struct CustomPeerMap *c_peer_map,
 260                                     uint32_t index)
 261 {
 262   uint32_t *index_p;
 263   struct GNUNET_PeerIdentity *peer;
 264
 265   if (index >= CustomPeerMap_size (c_peer_map))
 266   {
 267     return GNUNET_NO;
 268   }
 269   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 270                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 271   if (GNUNET_NO ==
 272       GNUNET_CONTAINER_multihashmap32_contains (c_peer_map->hash_map, index))
 273   {
 274     return GNUNET_NO;
 275   }
 276   peer = CustomPeerMap_get_peer_by_index (c_peer_map, index);
 277   GNUNET_assert (NULL != peer);
 278   index_p = CustomPeerMap_get_index_pointer (c_peer_map, peer);
 279   GNUNET_assert (index == *index_p);
 280   CustomPeerMap_remove_peer (c_peer_map, peer);
 281   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 282                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 283   return GNUNET_OK;
 284 }
 285
 286 /**
 287  * Clear the custom peer map
 288  *
 289  * @param c_peer_map the custom peer map to look in
 290  *
 291  * @return size of the map
 292  */
 293 void
 294 CustomPeerMap_clear (const struct CustomPeerMap *c_peer_map)
 295 {
 296   while (0 < CustomPeerMap_size (c_peer_map))
 297   {
 298     GNUNET_assert (GNUNET_YES ==
 299         GNUNET_CONTAINER_multihashmap32_contains (c_peer_map->hash_map,
 300           CustomPeerMap_size (c_peer_map) -1));
 301     GNUNET_assert (GNUNET_OK ==
 302         CustomPeerMap_remove_peer_by_index (c_peer_map,
 303                                             CustomPeerMap_size (c_peer_map) -1));
 304   }
 305   GNUNET_assert (0 == CustomPeerMap_size (c_peer_map));
 306 }
 307
 308 /**
 309  * Destroy peermap.
 310  *
 311  * @param c_peer_map the map to destroy
 312  */
 313 void
 314 CustomPeerMap_destroy (struct CustomPeerMap *c_peer_map)
 315 {
 316   CustomPeerMap_clear (c_peer_map);
 317   GNUNET_CONTAINER_multihashmap32_destroy (c_peer_map->hash_map);
 318   GNUNET_CONTAINER_multipeermap_destroy   (c_peer_map->peer_map);
 319   GNUNET_free (c_peer_map);
 320 }
 321
 322 /* end of gnunet-service-rps_custommap.c */