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