git.meshlink.io Git - meshlink/blob - src/hash.c

   1 /*
   2     hash.c -- hash table management
   3     Copyright (C) 2014 Guus Sliepen <guus@meshlink.io>
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License along
  16     with this program; if not, write to the Free Software Foundation, Inc.,
  17     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include "system.h"
  21
  22 #include "hash.h"
  23 #include "xalloc.h"
  24
  25 /* Generic hash function */
  26
  27 static uint32_t hash_function(const void *p, size_t len) {
  28         const uint8_t *q = p;
  29         uint32_t hash = 0;
  30
  31         while(true) {
  32                 for(int i = len > 4 ? 4 : len; --i;) {
  33                         hash += q[len - i] << (8 * i);
  34                 }
  35
  36                 hash *= 0x9e370001UL; // Golden ratio prime.
  37
  38                 if(len <= 4) {
  39                         break;
  40                 }
  41
  42                 len -= 4;
  43         }
  44
  45         return hash;
  46 }
  47
  48 /* Map 32 bits int onto 0..n-1, without throwing away too many bits if n is 2^8 or 2^16 */
  49
  50 static uint32_t modulo(uint32_t hash, size_t n) {
  51         if(n == 0x100) {
  52                 return (hash >> 24) ^ ((hash >> 16) & 0xff) ^ ((hash >> 8) & 0xff) ^ (hash & 0xff);
  53         } else if(n == 0x10000) {
  54                 return (hash >> 16) ^ (hash & 0xffff);
  55         } else {
  56                 return hash % n;
  57         }
  58 }
  59
  60 /* (De)allocation */
  61
  62 hash_t *hash_alloc(size_t n, size_t size) {
  63         hash_t *hash = xzalloc(sizeof(*hash));
  64         hash->n = n;
  65         hash->size = size;
  66         hash->keys = xzalloc(hash->n * hash->size);
  67         hash->values = xzalloc(hash->n * sizeof(*hash->values));
  68         return hash;
  69 }
  70
  71 void hash_free(hash_t *hash) {
  72         free(hash->keys);
  73         free(hash->values);
  74         free(hash);
  75 }
  76
  77 /* Searching and inserting */
  78
  79 void hash_insert(hash_t *hash, const void *key, const void *value) {
  80         uint32_t i = modulo(hash_function(key, hash->size), hash->n);
  81         memcpy(hash->keys + i * hash->size, key, hash->size);
  82         hash->values[i] = value;
  83 }
  84
  85 void *hash_search(const hash_t *hash, const void *key) {
  86         uint32_t i = modulo(hash_function(key, hash->size), hash->n);
  87
  88         if(hash->values[i] && !memcmp(key, hash->keys + i * hash->size, hash->size)) {
  89                 return (void *)hash->values[i];
  90         }
  91
  92         return NULL;
  93 }
  94
  95 void *hash_search_or_insert(hash_t *hash, const void *key, const void *value) {
  96         uint32_t i = modulo(hash_function(key, hash->size), hash->n);
  97
  98         if(hash->values[i] && !memcmp(key, hash->keys + i * hash->size, hash->size)) {
  99                 return (void *)hash->values[i];
 100         }
 101
 102         memcpy(hash->keys + i * hash->size, key, hash->size);
 103         hash->values[i] = value;
 104         return NULL;
 105 }
 106
 107 /* Utility functions */
 108
 109 void hash_clear(hash_t *hash) {
 110         memset(hash->values, 0, hash->n * sizeof(*hash->values));
 111 }
 112
 113 void hash_resize(hash_t *hash, size_t n) {
 114         hash->keys = xrealloc(hash->keys, n * hash->size);
 115         hash->values = xrealloc(hash->values, n * sizeof(*hash->values));
 116
 117         if(n > hash->n) {
 118                 memset(hash->keys + hash->n * hash->size, 0, (n - hash->n) * hash->size);
 119                 memset(hash->values + hash->n, 0, (n - hash->n) * sizeof(*hash->values));
 120         }
 121 }