src/util/peer.c

   1 /*
   2       This file is part of GNUnet
   3      Copyright (C) 2006, 2008, 2009 GNUnet e.V.
   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 util/peer.c
  21  * @brief peer-ID table that assigns integer IDs to peer-IDs to save memory
  22  * @author Christian Grothoff
  23  */
  24 #include "platform.h"
  25 #include "gnunet_peer_lib.h"
  26
  27 #define LOG(kind,...) GNUNET_log_from (kind, "util-peer", __VA_ARGS__)
  28
  29
  30 struct PeerEntry
  31 {
  32   /**
  33    * The identifier itself
  34    */
  35   struct GNUNET_PeerIdentity id;
  36
  37   /**
  38    * Short version of the identifier; if the RC==0, then index of next
  39    * free slot in table, otherwise equal to this slot in the table.
  40    */
  41   GNUNET_PEER_Id pid;
  42
  43   /**
  44    * Reference counter, 0 if this slot is not used.
  45    */
  46   unsigned int rc;
  47 };
  48
  49
  50 /**
  51  * Table with our interned peer IDs.
  52  */
  53 static struct PeerEntry **table;
  54
  55 /**
  56  * Peermap of PeerIdentities to "struct PeerEntry"
  57  * (for fast lookup).  NULL until the library
  58  * is actually being used.
  59  */
  60 static struct GNUNET_CONTAINER_MultiPeerMap *map;
  61
  62 /**
  63  * Size of the "table".
  64  */
  65 static unsigned int size;
  66
  67 /**
  68  * Index of the beginning of the free list in the table; set to "size"
  69  * if no slots are free in the table.
  70  */
  71 static unsigned int free_list_start;
  72
  73
  74 /**
  75  * Search for a peer identity. The reference counter is not changed.
  76  *
  77  * @param pid identity to find
  78  * @return the interned identity or 0.
  79  */
  80 GNUNET_PEER_Id
  81 GNUNET_PEER_search (const struct GNUNET_PeerIdentity *pid)
  82 {
  83   struct PeerEntry *e;
  84
  85   if (NULL == pid)
  86     return 0;
  87   if (NULL == map)
  88     return 0;
  89   e = GNUNET_CONTAINER_multipeermap_get (map, pid);
  90   if (NULL == e)
  91     return 0;
  92   GNUNET_assert (e->rc > 0);
  93   return e->pid;
  94 }
  95
  96
  97 /**
  98  * Intern an peer identity.  If the identity is already known, its
  99  * reference counter will be increased by one.
 100  *
 101  * @param pid identity to intern
 102  * @return the interned identity.
 103  */
 104 GNUNET_PEER_Id
 105 GNUNET_PEER_intern (const struct GNUNET_PeerIdentity *pid)
 106 {
 107   GNUNET_PEER_Id ret;
 108   struct PeerEntry *e;
 109   unsigned int i;
 110
 111   if (NULL == pid)
 112     return 0;
 113   if (NULL == map)
 114     map = GNUNET_CONTAINER_multipeermap_create (32, GNUNET_YES);
 115   e = GNUNET_CONTAINER_multipeermap_get (map, pid);
 116   if (NULL != e)
 117   {
 118     GNUNET_assert (e->rc > 0);
 119     e->rc++;
 120     return e->pid;
 121   }
 122   ret = free_list_start;
 123   if (ret == size)
 124   {
 125     GNUNET_array_grow (table, size, size + 16);
 126     for (i = ret; i < size; i++)
 127     {
 128       table[i] = GNUNET_new (struct PeerEntry);
 129       table[i]->pid = i + 1;
 130     }
 131   }
 132   if (0 == ret)
 133   {
 134     memset (&table[0]->id, 0, sizeof (struct GNUNET_PeerIdentity));
 135     table[0]->pid = 0;
 136     table[0]->rc = 1;
 137     ret = 1;
 138   }
 139   GNUNET_assert (ret < size);
 140   GNUNET_assert (0 == table[ret]->rc);
 141   free_list_start = table[ret]->pid;
 142   table[ret]->id = *pid;
 143   table[ret]->rc = 1;
 144   table[ret]->pid = ret;
 145   GNUNET_break (GNUNET_OK ==
 146                 GNUNET_CONTAINER_multipeermap_put (map,
 147                                                    &table[ret]->id,
 148                                                    table[ret],
 149                                                    GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
 150   return ret;
 151 }
 152
 153
 154 /**
 155  * Decrement multiple RCs of peer identities by one.
 156  *
 157  * @param ids array of PIDs to decrement the RCs of
 158  * @param count size of the ids array
 159  */
 160 void
 161 GNUNET_PEER_decrement_rcs (const GNUNET_PEER_Id *ids, unsigned int count)
 162 {
 163   int i;
 164   GNUNET_PEER_Id id;
 165
 166   if (0 == count)
 167     return;
 168   for (i = count - 1; i >= 0; i--)
 169   {
 170     id = ids[i];
 171     if (0 == id)
 172       continue;
 173     GNUNET_assert (id < size);
 174     GNUNET_assert (table[id]->rc > 0);
 175     table[id]->rc--;
 176     if (0 == table[id]->rc)
 177     {
 178       GNUNET_break (GNUNET_OK ==
 179                     GNUNET_CONTAINER_multipeermap_remove (map,
 180                                                           &table[id]->id,
 181                                                           table[id]));
 182       table[id]->pid = free_list_start;
 183       free_list_start = id;
 184     }
 185   }
 186 }
 187
 188
 189 /**
 190  * Change the reference counter of an interned PID.
 191  *
 192  * @param id identity to change the RC of
 193  * @param delta how much to change the RC
 194  */
 195 void
 196 GNUNET_PEER_change_rc (GNUNET_PEER_Id id, int delta)
 197 {
 198   if (0 == id)
 199     return;
 200   GNUNET_assert (id < size);
 201   GNUNET_assert (table[id]->rc > 0);
 202   GNUNET_assert ( (delta >= 0) ||
 203                   (table[id]->rc >= (unsigned int) (-delta)) );
 204   table[id]->rc += delta;
 205   if (0 == table[id]->rc)
 206   {
 207     GNUNET_break (GNUNET_OK ==
 208                   GNUNET_CONTAINER_multipeermap_remove (map,
 209                                                         &table[id]->id,
 210                                                         table[id]));
 211     table[id]->pid = free_list_start;
 212     free_list_start = id;
 213   }
 214 }
 215
 216
 217 /**
 218  * Convert an interned PID to a normal peer identity.
 219  *
 220  * @param id interned PID to convert
 221  * @param pid where to write the normal peer identity
 222  */
 223 void
 224 GNUNET_PEER_resolve (GNUNET_PEER_Id id, struct GNUNET_PeerIdentity *pid)
 225 {
 226   if (0 == id)
 227   {
 228     memset (pid, 0, sizeof (struct GNUNET_PeerIdentity));
 229     return;
 230   }
 231   GNUNET_assert (id < size);
 232   GNUNET_assert (table[id]->rc > 0);
 233   *pid = table[id]->id;
 234 }
 235
 236
 237 /**
 238  * Convert an interned PID to a normal peer identity.
 239  *
 240  * @param id interned PID to convert
 241  * @return pointer to peer identity, valid as long 'id' is valid
 242  */
 243 const struct GNUNET_PeerIdentity *
 244 GNUNET_PEER_resolve2 (GNUNET_PEER_Id id)
 245 {
 246   GNUNET_assert (id < size);
 247   GNUNET_assert (table[id]->rc > 0);
 248   return &table[id]->id;
 249 }
 250
 251
 252
 253 /* end of peer.c */