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   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     last_index = GNUNET_CONTAINER_multipeermap_get (c_peer_map->peer_map, last_p);
 213     GNUNET_assert (NULL != last_index);
 214     GNUNET_assert (CustomPeerMap_size (c_peer_map) == *last_index);
 215     GNUNET_CONTAINER_multihashmap32_put (c_peer_map->hash_map, *index, last_p,
 216         GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
 217     GNUNET_CONTAINER_multihashmap32_remove_all (c_peer_map->hash_map, *last_index);
 218     *last_index = *index;
 219   }
 220   GNUNET_free (index);
 221   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 222                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 223   return GNUNET_OK;
 224 }
 225
 226 /**
 227  * Get a peer by index
 228  *
 229  * @param c_peer_map the custom peer map to look in
 230  * @param index the index of the peer to get
 231  *
 232  * @return peer to the corresponding index.
 233  *         if this index is not known, return NULL
 234  */
 235 struct GNUNET_PeerIdentity *
 236 CustomPeerMap_get_peer_by_index (const struct CustomPeerMap *c_peer_map,
 237                                  uint32_t index)
 238 {
 239   if (GNUNET_YES ==
 240       GNUNET_CONTAINER_multihashmap32_contains (c_peer_map->hash_map, index))
 241   {
 242     return GNUNET_CONTAINER_multihashmap32_get (c_peer_map->hash_map, index);
 243   }
 244   return NULL;
 245 }
 246
 247 /**
 248  * Remove peer from custom peer map by index
 249  *
 250  * @param c_peer_map the custom peer map to remove the peer from
 251  * @param index the index of the peer to remove
 252  *
 253  * @return GNUNET_OK if map contained peer and removed it successfully
 254  *         GNUNET_NO if map does not contain (index of) peer
 255  */
 256 int
 257 CustomPeerMap_remove_peer_by_index (const struct CustomPeerMap *c_peer_map,
 258                                     uint32_t index)
 259 {
 260   uint32_t *index_p;
 261   struct GNUNET_PeerIdentity *peer;
 262
 263   if (index >= CustomPeerMap_size (c_peer_map))
 264   {
 265     return GNUNET_NO;
 266   }
 267   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 268                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 269   if (GNUNET_NO ==
 270       GNUNET_CONTAINER_multihashmap32_contains (c_peer_map->hash_map, index))
 271   {
 272     return GNUNET_NO;
 273   }
 274   peer = CustomPeerMap_get_peer_by_index (c_peer_map, index);
 275   GNUNET_assert (NULL != peer);
 276   index_p = CustomPeerMap_get_index_pointer (c_peer_map, peer);
 277   GNUNET_assert (index == *index_p);
 278   CustomPeerMap_remove_peer (c_peer_map, peer);
 279   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 280                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 281   return GNUNET_OK;
 282 }
 283
 284 /**
 285  * Clear the custom peer map
 286  *
 287  * @param c_peer_map the custom peer map to look in
 288  *
 289  * @return size of the map
 290  */
 291 void
 292 CustomPeerMap_clear (const struct CustomPeerMap *c_peer_map)
 293 {
 294   while (0 < CustomPeerMap_size (c_peer_map))
 295   {
 296     GNUNET_assert (GNUNET_YES ==
 297         GNUNET_CONTAINER_multihashmap32_contains (c_peer_map->hash_map,
 298           CustomPeerMap_size (c_peer_map) -1));
 299     GNUNET_assert (GNUNET_OK ==
 300         CustomPeerMap_remove_peer_by_index (c_peer_map,
 301                                             CustomPeerMap_size (c_peer_map) -1));
 302   }
 303   GNUNET_assert (0 == CustomPeerMap_size (c_peer_map));
 304 }
 305
 306 /**
 307  * Destroy peermap.
 308  *
 309  * @param c_peer_map the map to destroy
 310  */
 311 void
 312 CustomPeerMap_destroy (struct CustomPeerMap *c_peer_map)
 313 {
 314   CustomPeerMap_clear (c_peer_map);
 315   GNUNET_CONTAINER_multihashmap32_destroy (c_peer_map->hash_map);
 316   GNUNET_CONTAINER_multipeermap_destroy   (c_peer_map->peer_map);
 317   GNUNET_free (c_peer_map);
 318 }
 319
 320 /* end of gnunet-service-rps_custommap.c */