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      SPDX-License-Identifier: AGPL3.0-or-later
  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,
  86                                                                GNUNET_NO);
  87   return c_peer_map;
  88 }
  89
  90
  91 /**
  92  * Get the size of the custom peer map
  93  *
  94  * @param c_peer_map the custom peer map to look in
  95  *
  96  * @return size of the map
  97  */
  98 unsigned int
  99 CustomPeerMap_size (const struct CustomPeerMap *c_peer_map)
 100 {
 101   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 102                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 103   return GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map);
 104 }
 105
 106
 107 /**
 108  * Insert peer into the custom peer map
 109  *
 110  * @param c_peer_map the custom peer map to insert peer
 111  * @param peer the peer to insert
 112  *
 113  * @return GNUNET_OK if map did not contain peer previously
 114  *         GNUNET_NO if map did contain peer previously
 115  */
 116 int
 117 CustomPeerMap_put (const struct CustomPeerMap *c_peer_map,
 118                    const struct GNUNET_PeerIdentity *peer)
 119 {
 120   uint32_t *index;
 121   struct GNUNET_PeerIdentity *p;
 122
 123   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 124                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 125   if (GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains (c_peer_map->peer_map,
 126                                                            peer))
 127   {
 128     /* Need to store the index of the peer in the peermap to be able to remove
 129      * it properly */
 130     index = GNUNET_new (uint32_t);
 131     *index = CustomPeerMap_size (c_peer_map);
 132     p = GNUNET_new (struct GNUNET_PeerIdentity);
 133     *p = *peer;
 134     GNUNET_assert (p != peer);
 135     GNUNET_assert (0 == memcmp (p,
 136                                 peer,
 137                                 sizeof(struct GNUNET_PeerIdentity)));
 138     GNUNET_CONTAINER_multipeermap_put (c_peer_map->peer_map,
 139                                        p,
 140                                        index,
 141                                        GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
 142     GNUNET_CONTAINER_multihashmap32_put (c_peer_map->hash_map,
 143                                          *index,
 144                                          p,
 145                                          GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
 146     GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (
 147                      c_peer_map->hash_map) ==
 148                    GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 149     return GNUNET_OK;
 150   }
 151   return GNUNET_NO;
 152 }
 153
 154
 155 /**
 156  * Check whether custom peer map contains a peer
 157  *
 158  * @param c_peer_map the custom peer map to look in
 159  * @param peer the peer to check for
 160  *
 161  * @return GNUNET_OK if map contains peer
 162  *         GNUNET_NO  otherwise
 163  */
 164 int
 165 CustomPeerMap_contains_peer (const struct CustomPeerMap *c_peer_map,
 166                              const struct GNUNET_PeerIdentity *peer)
 167 {
 168   return GNUNET_CONTAINER_multipeermap_contains (c_peer_map->peer_map, peer);
 169 }
 170
 171
 172 /**
 173  * Get index of peer in custom peer map
 174  *
 175  * @param c_peer_map the custom peer map to look in
 176  * @param peer the peer to get the index from
 177  *
 178  * @return the index
 179  */
 180 static uint32_t *
 181 CustomPeerMap_get_index_pointer (const struct CustomPeerMap *c_peer_map,
 182                                  const struct GNUNET_PeerIdentity *peer)
 183 {
 184   uint32_t *index;
 185
 186   GNUNET_assert (GNUNET_YES == CustomPeerMap_contains_peer (c_peer_map, peer));
 187   index = GNUNET_CONTAINER_multipeermap_get (c_peer_map->peer_map, peer);
 188   return index;
 189 }
 190
 191
 192 /**
 193  * Remove peer from custom peer map
 194  *
 195  * @param c_peer_map the custom peer map to remove the peer from
 196  * @param peer the peer to remove
 197  *
 198  * @return GNUNET_OK if map contained peer and removed it successfully
 199  *         GNUNET_NO if map does not contain peer
 200  */
 201 int
 202 CustomPeerMap_remove_peer (const struct CustomPeerMap *c_peer_map,
 203                            const struct GNUNET_PeerIdentity *peer)
 204 {
 205   uint32_t *index;
 206   struct GNUNET_PeerIdentity *p;
 207   uint32_t *last_index;
 208   struct GNUNET_PeerIdentity *last_p;
 209
 210   if (GNUNET_NO == CustomPeerMap_contains_peer (c_peer_map,
 211                                                 peer))
 212   {
 213     return GNUNET_NO;
 214   }
 215   index = CustomPeerMap_get_index_pointer (c_peer_map,
 216                                            peer);
 217   GNUNET_assert (*index < CustomPeerMap_size (c_peer_map));
 218   /* Need to get the pointer stored in the hashmap to free it */
 219   p = GNUNET_CONTAINER_multihashmap32_get (c_peer_map->hash_map,
 220                                            *index);
 221   GNUNET_assert (NULL != p);
 222   GNUNET_CONTAINER_multihashmap32_remove_all (c_peer_map->hash_map,
 223                                               *index);
 224   // TODO wrong peerid?
 225   GNUNET_CONTAINER_multipeermap_remove_all (c_peer_map->peer_map,
 226                                             peer);
 227   if (*index != CustomPeerMap_size (c_peer_map))
 228   {   /* fill 'gap' with peer at last index */
 229     last_p =
 230       GNUNET_CONTAINER_multihashmap32_get (c_peer_map->hash_map,
 231                                            CustomPeerMap_size (c_peer_map));
 232     GNUNET_assert (NULL != last_p);
 233     last_index = GNUNET_CONTAINER_multipeermap_get (c_peer_map->peer_map,
 234                                                     last_p);
 235     GNUNET_assert (NULL != last_index);
 236     GNUNET_assert (CustomPeerMap_size (c_peer_map) == *last_index);
 237     GNUNET_CONTAINER_multihashmap32_put (c_peer_map->hash_map,
 238                                          *index, last_p,
 239                                          GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
 240     GNUNET_CONTAINER_multihashmap32_remove_all (c_peer_map->hash_map,
 241                                                 *last_index);
 242     *last_index = *index;
 243   }
 244   GNUNET_free (index);
 245   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 246                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 247   GNUNET_free (p);
 248   return GNUNET_OK;
 249 }
 250
 251
 252 /**
 253  * Get a peer by index
 254  *
 255  * @param c_peer_map the custom peer map to look in
 256  * @param index the index of the peer to get
 257  *
 258  * @return peer to the corresponding index.
 259  *         if this index is not known, return NULL
 260  */
 261 struct GNUNET_PeerIdentity *
 262 CustomPeerMap_get_peer_by_index (const struct CustomPeerMap *c_peer_map,
 263                                  uint32_t index)
 264 {
 265   if (GNUNET_YES ==
 266       GNUNET_CONTAINER_multihashmap32_contains (c_peer_map->hash_map, index))
 267   {
 268     return GNUNET_CONTAINER_multihashmap32_get (c_peer_map->hash_map, index);
 269   }
 270   return NULL;
 271 }
 272
 273
 274 /**
 275  * Remove peer from custom peer map by index
 276  *
 277  * @param c_peer_map the custom peer map to remove the peer from
 278  * @param index the index of the peer to remove
 279  *
 280  * @return GNUNET_OK if map contained peer and removed it successfully
 281  *         GNUNET_NO if map does not contain (index of) peer
 282  */
 283 int
 284 CustomPeerMap_remove_peer_by_index (const struct CustomPeerMap *c_peer_map,
 285                                     uint32_t index)
 286 {
 287   uint32_t *index_p;
 288   struct GNUNET_PeerIdentity *peer;
 289
 290   if (index >= CustomPeerMap_size (c_peer_map))
 291   {
 292     return GNUNET_NO;
 293   }
 294   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 295                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 296   if (GNUNET_NO ==
 297       GNUNET_CONTAINER_multihashmap32_contains (c_peer_map->hash_map, index))
 298   {
 299     return GNUNET_NO;
 300   }
 301   peer = CustomPeerMap_get_peer_by_index (c_peer_map, index);
 302   GNUNET_assert (NULL != peer);
 303   index_p = CustomPeerMap_get_index_pointer (c_peer_map, peer);
 304   GNUNET_assert (index == *index_p);
 305   CustomPeerMap_remove_peer (c_peer_map, peer);
 306   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 307                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 308   return GNUNET_OK;
 309 }
 310
 311
 312 /**
 313  * Clear the custom peer map
 314  *
 315  * @param c_peer_map the custom peer map to look in
 316  *
 317  * @return size of the map
 318  */
 319 void
 320 CustomPeerMap_clear (const struct CustomPeerMap *c_peer_map)
 321 {
 322   while (0 < CustomPeerMap_size (c_peer_map))
 323   {
 324     GNUNET_assert (GNUNET_YES ==
 325                    GNUNET_CONTAINER_multihashmap32_contains (
 326                      c_peer_map->hash_map,
 327                      CustomPeerMap_size (
 328                        c_peer_map) - 1));
 329     GNUNET_assert (GNUNET_OK ==
 330                    CustomPeerMap_remove_peer_by_index (c_peer_map,
 331                                                        CustomPeerMap_size (
 332                                                          c_peer_map) - 1));
 333   }
 334   GNUNET_assert (0 == CustomPeerMap_size (c_peer_map));
 335 }
 336
 337
 338 /**
 339  * Destroy peermap.
 340  *
 341  * @param c_peer_map the map to destroy
 342  */
 343 void
 344 CustomPeerMap_destroy (struct CustomPeerMap *c_peer_map)
 345 {
 346   CustomPeerMap_clear (c_peer_map);
 347   GNUNET_CONTAINER_multihashmap32_destroy (c_peer_map->hash_map);
 348   GNUNET_CONTAINER_multipeermap_destroy (c_peer_map->peer_map);
 349   GNUNET_free (c_peer_map);
 350 }
 351
 352
 353 /* end of gnunet-service-rps_custommap.c */