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 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   switch (a->sa.sa_family) {
  78     case AF_INET:
  79       return (U32((AF_INET * 0x4eaac1b7ul) +
  80                   (a->sin.sin_addr.s_addr * 0xa5dbc837) +
  81                   (a->sin.sin_port * 0x3b049e83)));
  82     default:
  83       abort();
  84   }
  85 }
  86
  87 /* --- @addreq@ --- *
  88  *
  89  * Arguments:   @const addr *a, *b@ = pointer to addresses
  90  *
  91  * Returns:     Nonzero if the addresses are equal.
  92  */
  93
  94 static int addreq(const addr *a, const addr *b)
  95 {
  96   if (a->sa.sa_family != b->sa.sa_family)
  97     return (0);
  98   switch (a->sa.sa_family) {
  99     case AF_INET:
 100       return (a->sin.sin_addr.s_addr == b->sin.sin_addr.s_addr &&
 101               a->sin.sin_port == b->sin.sin_port);
 102     default:
 103       abort();
 104   }
 105 }
 106
 107 /* --- @am_find@ --- *
 108  *
 109  * Arguments:   @addrmap *m@ = pointer to map
 110  *              @const addr *a@ = address to look up
 111  *              @size_t sz@ = size of block to allocate
 112  *              @unsigned *f@ = where to store flags
 113  *
 114  * Returns:     Pointer to found item, or null.
 115  *
 116  * Use:         Finds a record with the given IP address, set @*f@ nonzero
 117  *              and returns it.  If @sz@ is zero, and no match was found,
 118  *              return null; otherwise allocate a new block of @sz@ bytes,
 119  *              clear @*f@ to zero and return the block pointer.
 120  */
 121
 122 void *am_find(addrmap *m, const addr *a, size_t sz, unsigned *f)
 123 {
 124   uint32 h = hash(a);
 125   hash_base **b, **bb;
 126   addrmap_base *i;
 127
 128   bb = HASH_BIN(&m->t, h);
 129   for (b = bb; *b; b = &(*b)->next) {
 130     i = (addrmap_base *)*b;
 131     if (i->b.hash == h && addreq(a, &i->a)) {
 132       *b = i->b.next;
 133       i->b.next = *bb;
 134       *bb = &i->b;
 135       if (f) *f = 1;
 136       return (i);
 137     }
 138   }
 139
 140   if (f) *f = 0;
 141   if (!sz) return (0);
 142   i = x_alloc(m->t.a, sz);
 143   i->b.hash = h;
 144   i->b.next = *bb;
 145   *bb = &i->b;
 146   i->a = *a;
 147
 148   if (m->load)
 149     m->load--;
 150   if (!m->load && hash_extend(&m->t))
 151     m->load = AM_LOAD(m->t.mask + 1);
 152   return (i);
 153 }
 154
 155 /* --- @am_remove@ --- *
 156  *
 157  * Arguments:   @addrmap *m@ = pointer to map
 158  *              @void *i@ = pointer to the item
 159  *
 160  * Returns:     ---
 161  *
 162  * Use:         Removes an item from the map.
 163  */
 164
 165 void am_remove(addrmap *m, void *i)
 166 {
 167   hash_remove(&m->t, i);
 168   x_free(m->t.a, i);
 169 }
 170
 171 /*----- That's all, folks -------------------------------------------------*/