chiark - git - mdw - tripe/blob - server/addrmap.c

   1 /* -*-c-*-
   2  *
   3  * Hashtables keyed by network addresses
   4  *
   5  * (c) 2007 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Trivial IP Encryption (TrIPE).
  11  *
  12  * TrIPE is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU General Public License as published by
  14  * the Free Software Foundation; either version 2 of the License, or
  15  * (at your option) any later version.
  16  *
  17  * TrIPE is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU General Public License
  23  * along with TrIPE; if not, write to the Free Software Foundation,
  24  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  25  */
  26
  27 /*----- Header files ------------------------------------------------------*/
  28
  29 #include "tripe.h"
  30
  31 #define AM_LOAD(n) (((n) * 3)/2)
  32
  33 /*----- Main code ---------------------------------------------------------*/
  34
  35 /* --- @am_create@ --- *
  36  *
  37  * Arguments:   @addrmap *m@ = pointer to map
  38  *
  39  * Returns:     ---
  40  *
  41  * Use:         Create an address map, properly set up.
  42  */
  43
  44 void am_create(addrmap *m)
  45 {
  46   hash_create(&m->t, 16);
  47   m->load = AM_LOAD(m->t.mask + 1);
  48 }
  49
  50 /* --- @am_destroy@ --- *
  51  *
  52  * Arguments:   @addrmap *m@ = pointer to map
  53  *
  54  * Returns:     ---
  55  *
  56  * Use:         Destroy an address map, throwing away all the entries.
  57  */
  58
  59 void am_destroy(addrmap *m)
  60 {
  61   hash_base *p;
  62   hash_iter i;
  63
  64   for (hash_mkiter(&i, &m->t); (p = hash_next(&i)) != 0; )
  65     x_free(m->t.a, p);
  66   hash_destroy(&m->t);
  67 }
  68
  69 /* --- @hash@ --- *
  70  *
  71  * Arguments:   @const addr *a@ = pointer to address
  72  *
  73  * Returns:     The hash of the address.
  74  */
  75
  76 uint32 hash(const addr *a)
  77 {
  78   switch (a->sa.sa_family) {
  79     case AF_INET:
  80       return (U32((AF_INET * 0x4eaac1b7ul) +
  81                   (a->sin.sin_addr.s_addr * 0xa5dbc837) +
  82                   (a->sin.sin_port * 0x3b049e83)));
  83     default:
  84       abort();
  85   }
  86 }
  87
  88 /* --- @addreq@ --- *
  89  *
  90  * Arguments:   @const addr *a, *b@ = pointer to addresses
  91  *
  92  * Returns:     Nonzero if the addresses are equal.
  93  */
  94
  95 int addreq(const addr *a, const addr *b)
  96 {
  97   if (a->sa.sa_family != b->sa.sa_family)
  98     return (0);
  99   switch (a->sa.sa_family) {
 100     case AF_INET:
 101       return (a->sin.sin_addr.s_addr == b->sin.sin_addr.s_addr &&
 102               a->sin.sin_port == b->sin.sin_port);
 103     default:
 104       abort();
 105   }
 106 }
 107
 108 /* --- @am_find@ --- *
 109  *
 110  * Arguments:   @addrmap *m@ = pointer to map
 111  *              @const addr *a@ = address to look up
 112  *              @size_t sz@ = size of block to allocate
 113  *              @unsigned *f@ = where to store flags
 114  *
 115  * Returns:     Pointer to found item, or null.
 116  *
 117  * Use:         Finds a record with the given IP address, set @*f@ nonzero
 118  *              and returns it.  If @sz@ is zero, and no match was found,
 119  *              return null; otherwise allocate a new block of @sz@ bytes,
 120  *              clear @*f@ to zero and return the block pointer.
 121  */
 122
 123 void *am_find(addrmap *m, const addr *a, size_t sz, unsigned *f)
 124 {
 125   uint32 h = hash(a);
 126   hash_base **b, **bb;
 127   addrmap_base *i;
 128
 129   bb = HASH_BIN(&m->t, h);
 130   for (b = bb; *b; b = &(*b)->next) {
 131     i = (addrmap_base *)*b;
 132     if (i->b.hash == h && addreq(a, &i->a)) {
 133       *b = i->b.next;
 134       i->b.next = *bb;
 135       *bb = &i->b;
 136       if (f) *f = 1;
 137       return (i);
 138     }
 139   }
 140
 141   if (f) *f = 0;
 142   if (!sz) return (0);
 143   i = x_alloc(m->t.a, sz);
 144   i->b.hash = h;
 145   i->b.next = *bb;
 146   *bb = &i->b;
 147   i->a = *a;
 148
 149   if (m->load)
 150     m->load--;
 151   if (!m->load && hash_extend(&m->t))
 152     m->load = AM_LOAD(m->t.mask + 1);
 153   return (i);
 154 }
 155
 156 /* --- @am_remove@ --- *
 157  *
 158  * Arguments:   @addrmap *m@ = pointer to map
 159  *              @void *i@ = pointer to the item
 160  *
 161  * Returns:     ---
 162  *
 163  * Use:         Removes an item from the map.
 164  */
 165
 166 void am_remove(addrmap *m, void *i)
 167 {
 168   hash_remove(&m->t, i);
 169   x_free(m->t.a, i);
 170 }
 171
 172 /*----- That's all, folks -------------------------------------------------*/