usr.sbin/nscd/hashtable.h

   1 /*-
   2  * Copyright (c) 2005 Michael Bushkov <bushman@rsu.ru>
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  *
  26  * $FreeBSD$
  27  */
  28
  29 #ifndef __CACHELIB_HASHTABLE_H__
  30 #define __CACHELIB_HASHTABLE_H__
  31
  32 #include <string.h>
  33
  34 #define HASHTABLE_INITIAL_ENTRIES_CAPACITY 8
  35 typedef unsigned int hashtable_index_t;
  36
  37 /*
  38  * This file contains queue.h-like macro definitions for hash tables.
  39  * Hash table is organized as an array of the specified size of the user
  40  * defined (with HASTABLE_ENTRY_HEAD) structures. Each hash table
  41  * entry (user defined structure) stores its elements in the sorted array.
  42  * You can place elements into the hash table, retrieve elements with
  43  * specified key, traverse through all elements, and delete them.
  44  * New elements are placed into the hash table by using the compare and
  45  * hashing functions, provided by the user.
  46  */
  47
  48 /*
  49  * Defines the hash table entry structure, that uses specified type of
  50  * elements.
  51  */
  52 #define HASHTABLE_ENTRY_HEAD(name, type) struct name {                  \
  53         type    *values;                                                \
  54         size_t capacity;                                                \
  55         size_t size;                                                    \
  56 }
  57
  58 /*
  59  * Defines the hash table structure, which uses the specified type of entries.
  60  * The only restriction for entries is that is that they should have the field,
  61  * defined with HASHTABLE_ENTRY_HEAD macro.
  62  */
  63 #define HASHTABLE_HEAD(name, entry) struct name {                       \
  64         struct entry    *entries;                                       \
  65         size_t          entries_size;                                   \
  66 }
  67
  68 #define HASHTABLE_ENTRIES_COUNT(table)                                  \
  69         ((table)->entries_size)
  70
  71 /*
  72  * Unlike most of queue.h data types, hash tables can not be initialized
  73  * statically - so there is no HASHTABLE_HEAD_INITIALIZED macro.
  74  */
  75 #define HASHTABLE_INIT(table, type, field, _entries_size)               \
  76         do {                                                            \
  77                 hashtable_index_t var;                                  \
  78                 (table)->entries = calloc(1,                            \
  79                         sizeof(*(table)->entries) * (_entries_size));   \
  80                 (table)->entries_size = (_entries_size);                \
  81                 for (var = 0; var < HASHTABLE_ENTRIES_COUNT(table); ++var) {\
  82                         (table)->entries[var].field.capacity =          \
  83                                 HASHTABLE_INITIAL_ENTRIES_CAPACITY;     \
  84                         (table)->entries[var].field.size = 0;           \
  85                         (table)->entries[var].field.values = malloc(    \
  86                                 sizeof(type) *                          \
  87                                 HASHTABLE_INITIAL_ENTRIES_CAPACITY);    \
  88                         assert((table)->entries[var].field.values != NULL);\
  89                 }                                                       \
  90         } while (0)
  91
  92 /*
  93  * All initialized hashtables should be destroyed with this macro.
  94  */
  95 #define HASHTABLE_DESTROY(table, field)                                 \
  96         do {                                                            \
  97                 hashtable_index_t var;                                  \
  98                 for (var = 0; var < HASHTABLE_ENTRIES_COUNT(table); ++var) {\
  99                         free((table)->entries[var].field.values);       \
 100                 }                                                       \
 101         } while (0)
 102
 103 #define HASHTABLE_GET_ENTRY(table, hash)                                \
 104         (&((table)->entries[hash]))
 105
 106 /*
 107  * Traverses through all hash table entries
 108  */
 109 #define HASHTABLE_FOREACH(table, var)                                   \
 110         for ((var) = &((table)->entries[0]);                            \
 111                 (var) < &((table)->entries[HASHTABLE_ENTRIES_COUNT(table)]);\
 112                 ++(var))
 113
 114 /*
 115  * Traverses through all elements of the specified hash table entry
 116  */
 117 #define HASHTABLE_ENTRY_FOREACH(entry, field, var)                      \
 118         for ((var) = &((entry)->field.values[0]);                       \
 119                 (var) < &((entry)->field.values[(entry)->field.size]);  \
 120                 ++(var))
 121
 122 #define HASHTABLE_ENTRY_CLEAR(entry, field)                             \
 123         ((entry)->field.size = 0)
 124
 125 #define HASHTABLE_ENTRY_SIZE(entry, field)                              \
 126         ((entry)->field.size)
 127
 128 #define HASHTABLE_ENTRY_CAPACITY(entry, field)                          \
 129         ((entry)->field.capacity)
 130
 131 #define HASHTABLE_ENTRY_CAPACITY_INCREASE(entry, field, type)           \
 132         do {                                                            \
 133                 (entry)->field.capacity *= 2;                           \
 134                 (entry)->field.values = realloc((entry)->field.values,  \
 135                          (entry)->field.capacity * sizeof(type));       \
 136         } while (0)
 137
 138 #define HASHTABLE_ENTRY_CAPACITY_DECREASE(entry, field, type)           \
 139         do {                                                            \
 140                 (entry)->field.capacity /= 2;                           \
 141                 (entry)->field.values = realloc((entry)->field.values,  \
 142                         (entry)->field.capacity * sizeof(type));        \
 143         } while (0)
 144
 145 /*
 146  * Generates prototypes for the hash table functions
 147  */
 148 #define HASHTABLE_PROTOTYPE(name, entry_, type)                         \
 149 hashtable_index_t name##_CALCULATE_HASH(struct name *, type *);         \
 150 void name##_ENTRY_STORE(struct entry_*, type *);                        \
 151 type *name##_ENTRY_FIND(struct entry_*, type *);                        \
 152 type *name##_ENTRY_FIND_SPECIAL(struct entry_ *, type *,                \
 153         int (*) (const void *, const void *));                          \
 154 void name##_ENTRY_REMOVE(struct entry_*, type *);
 155
 156 /*
 157  * Generates implementations of the hash table functions
 158  */
 159 #define HASHTABLE_GENERATE(name, entry_, type, field, HASH, CMP)        \
 160 hashtable_index_t name##_CALCULATE_HASH(struct name *table, type *data) \
 161 {                                                                       \
 162                                                                         \
 163         return HASH(data, table->entries_size);                         \
 164 }                                                                       \
 165                                                                         \
 166 void name##_ENTRY_STORE(struct entry_ *the_entry, type *data)           \
 167 {                                                                       \
 168                                                                         \
 169         if (the_entry->field.size == the_entry->field.capacity)         \
 170                 HASHTABLE_ENTRY_CAPACITY_INCREASE(the_entry, field, type);\
 171                                                                         \
 172         memcpy(&(the_entry->field.values[the_entry->field.size++]),     \
 173                 data,                                                   \
 174                 sizeof(type));                                          \
 175         qsort(the_entry->field.values, the_entry->field.size,           \
 176                 sizeof(type), CMP);                                     \
 177 }                                                                       \
 178                                                                         \
 179 type *name##_ENTRY_FIND(struct entry_ *the_entry, type *key)            \
 180 {                                                                       \
 181                                                                         \
 182         return ((type *)bsearch(key, the_entry->field.values,           \
 183                 the_entry->field.size, sizeof(type), CMP));             \
 184 }                                                                       \
 185                                                                         \
 186 type *name##_ENTRY_FIND_SPECIAL(struct entry_ *the_entry, type *key,    \
 187         int (*compar) (const void *, const void *))                     \
 188 {                                                                       \
 189         return ((type *)bsearch(key, the_entry->field.values,           \
 190                 the_entry->field.size, sizeof(type), compar));          \
 191 }                                                                       \
 192                                                                         \
 193 void name##_ENTRY_REMOVE(struct entry_ *the_entry, type *del_elm)       \
 194 {                                                                       \
 195                                                                         \
 196         memmove(del_elm, del_elm + 1,                                   \
 197                 (&the_entry->field.values[--the_entry->field.size] - del_elm) *\
 198                 sizeof(type));                                          \
 199 }
 200
 201 /*
 202  * Macro definitions below wrap the functions, generaed with
 203  * HASHTABLE_GENERATE macro. You should use them and avoid using generated
 204  * functions directly.
 205  */
 206 #define HASHTABLE_CALCULATE_HASH(name, table, data)                     \
 207         (name##_CALCULATE_HASH((table), data))
 208
 209 #define HASHTABLE_ENTRY_STORE(name, entry, data)                        \
 210         name##_ENTRY_STORE((entry), data)
 211
 212 #define HASHTABLE_ENTRY_FIND(name, entry, key)                          \
 213         (name##_ENTRY_FIND((entry), (key)))
 214
 215 #define HASHTABLE_ENTRY_FIND_SPECIAL(name, entry, key, cmp)             \
 216         (name##_ENTRY_FIND_SPECIAL((entry), (key), (cmp)))
 217
 218 #define HASHTABLE_ENTRY_REMOVE(name, entry, del_elm)                    \
 219         name##_ENTRY_REMOVE((entry), (del_elm))
 220
 221 #endif