htable2.h 8.91 KB
Newer Older
Pekka Pessi's avatar
Pekka Pessi committed
1 2 3 4 5 6 7
/*
 * This file is part of the Sofia-SIP package
 *
 * Copyright (C) 2005 Nokia Corporation.
 *
 * Contact: Pekka Pessi <pekka.pessi@nokia.com>
 *
8
 * This library is free software; you can redistribute it and/or
Pekka Pessi's avatar
Pekka Pessi committed
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either version 2.1 of
 * the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
 * 02110-1301 USA
 *
 */

Pekka Pessi's avatar
Pekka Pessi committed
25 26
#ifndef HTABLE2_H
/** Defined when <sofia-sip/htable2.h> has been included. */
27
#define HTABLE2_H
Pekka Pessi's avatar
Pekka Pessi committed
28

Pekka Pessi's avatar
Pekka Pessi committed
29
/**@file sofia-sip/htable2.h
Pekka Pessi's avatar
Pekka Pessi committed
30 31 32
 *
 * Hash tables templates, take 2.
 *
33 34 35
 * Note: this version stores the given element types as entries (instead of
 * always storing a pointer to element). It can be used without
 * <sofia-sip/su_alloc.h>.
36
 *
37 38 39 40 41 42
 * This file contain a hash table template for C. The hash tables are
 * resizeable, and they usually contain pointers to entries. The declaration
 * for template datatypes is instantiated with macro HTABLE2_DECLARE2(). The
 * prototypes for hashing functions are instantiated with macro
 * HTABLE2_PROTOS2(). The implementation is instantiated with macro
 * HTABLE2_BODIES2().
Pekka Pessi's avatar
Pekka Pessi committed
43 44 45
 *
 * The hash table template is most efficient when the hash value is
 * precalculated and stored in each entry.  The hash "function" given to the
46
 * HTABLE2_BODIES2() would then be something like macro
Pekka Pessi's avatar
Pekka Pessi committed
47
 * @code
48
 * #define ENTRY_HASH(e) ((e).e_hash_value)
Pekka Pessi's avatar
Pekka Pessi committed
49 50
 * @endcode
 *
51 52 53
 * When a entry with new identical key is added to the table, it can be
 * either @e inserted (before any other entry with same key value) or @e
 * appended.
54
 *
Pekka Pessi's avatar
Pekka Pessi committed
55
 * Example code can be found from <htable_test.c>.
56
 *
Pekka Pessi's avatar
Pekka Pessi committed
57 58 59 60 61 62 63 64 65 66 67
 * @author Pekka Pessi <Pekka.Pessi@nokia.com>.
 *
 * @date Created: Tue Sep 25 17:42:40 2001 ppessi
 */

typedef unsigned long hash_value_t;

/** Minimum size of hash table */
#define HTABLE2_MIN_SIZE 31

/** Declare hash table structure type.
68
 *
69 70 71
 * The macro HTABLE2_DECLARE2() expands to a declaration for hash table
 * structure. The its typedef will be @a type, the field names start with @a
 * pr. The entry type is @a entrytype.
Pekka Pessi's avatar
Pekka Pessi committed
72
 *
73
 * @param type      hash table typedef
Pekka Pessi's avatar
Pekka Pessi committed
74 75 76
 * @param sname     name of struct
 * @param pr        hash table field prefix
 * @param entrytype entry type
77
 * @param sizetype  type of size variables
78 79
 *
 * @NEW_1_12_8
Pekka Pessi's avatar
Pekka Pessi committed
80
 */
81
#define HTABLE2_DECLARE2(type, sname, pr, entrytype, sizetype)	\
82
typedef struct sname { \
83 84
  sizetype pr##size; \
  sizetype pr##used; \
85 86 87
  entrytype *pr##table; \
} type

Pekka Pessi's avatar
Pekka Pessi committed
88
#define HTABLE2_DECLARE(sname, prefix, pr, entrytype)	\
89
  HTABLE2_DECLARE2(prefix##t, sname, pr, entrytype, unsigned)
Pekka Pessi's avatar
Pekka Pessi committed
90 91 92

#ifndef HTABLE2_SCOPE
/** Default scope for hash table functions. */
93
#define HTABLE2_SCOPE su_inline
Pekka Pessi's avatar
Pekka Pessi committed
94 95 96 97
#endif

/** Prototypes for hash table
 *
98
 * The macro HTABLE2_PROTOS2() expands to the prototypes of hash table
Pekka Pessi's avatar
Pekka Pessi committed
99 100
 * functions.  The function and type names start with @a prefix, the field
 * names start with @a pr.  The entry type is @a entrytype.
101
 *
Pekka Pessi's avatar
Pekka Pessi committed
102 103
 * @param type      hash table typedef
 * @param prefix    function prefix
104
 * @param pr        hash table field prefix (not used)
Pekka Pessi's avatar
Pekka Pessi committed
105
 * @param entrytype entry type
106
 * @param sizetype  type of size variables
107 108
 *
 * @NEW_1_12_8
Pekka Pessi's avatar
Pekka Pessi committed
109
 */
110 111
#define HTABLE2_PROTOS2(type, prefix, pr, entrytype, sizetype)	    \
HTABLE2_SCOPE int prefix##_resize(void *a, type *, sizetype); \
Pekka Pessi's avatar
Pekka Pessi committed
112
HTABLE2_SCOPE int prefix##_is_full(type const *); \
113 114 115 116 117 118 119
HTABLE2_SCOPE entrytype *prefix##_hash(type const *, hash_value_t); \
HTABLE2_SCOPE entrytype *prefix##_next(type const *, entrytype *); \
HTABLE2_SCOPE entrytype *prefix##_append(type *, entrytype); \
HTABLE2_SCOPE entrytype *prefix##_insert(type *, entrytype); \
HTABLE2_SCOPE int prefix##_remove(type *, entrytype const)

#define HTABLE2_PROTOS(type, prefix, pr, entrytype) \
120
  HTABLE2_PROTOS2(type, prefix, pr, entrytype, unsigned)
Pekka Pessi's avatar
Pekka Pessi committed
121 122 123

/** Hash table implementation.
 *
124
 * The macro HTABLE2_BODIES2() expands the hash table functions.  The function
Pekka Pessi's avatar
Pekka Pessi committed
125 126 127 128 129
 * and type names start with @a prefix, the field names start with @a pr.
 * The entry type is @a entrytype.  The function (or macro) name returning
 * hash value of each entry is given as @a hfun.
 *
 * @param type      hash table type
130 131
 * @param prefix    function prefix for hash table
 * @param pr        field prefix for hash table
Pekka Pessi's avatar
Pekka Pessi committed
132
 * @param entrytype type of entry element
133
 * @param sizetype  size_t type
Pekka Pessi's avatar
Pekka Pessi committed
134 135 136 137 138
 * @param hfun      function or macro returning hash value of entry
 * @param is_used   function or macro returning true if entry is occupied
 * @param reclaim   function or macro zeroing entry
 * @param is_equal  equality test
 * @param halloc    function allocating or freeing memory
139 140
 *
 * @NEW_1_12_8
Pekka Pessi's avatar
Pekka Pessi committed
141
 */
142
#define HTABLE2_BODIES2(type, prefix, pr, entrytype, sizetype,		\
143
		        hfun, is_used, reclaim, is_equal, halloc)	\
Pekka Pessi's avatar
Pekka Pessi committed
144 145 146 147
/** Reallocate new hash table */ \
HTABLE2_SCOPE \
int prefix##_resize(void *realloc_arg, \
                    type pr[1], \
148
		    sizetype new_size) \
Pekka Pessi's avatar
Pekka Pessi committed
149 150 151
{ \
  entrytype *new_hash; \
  entrytype *old_hash = pr->pr##table; \
152 153 154
  sizetype old_size; \
  sizetype i, j, i0; \
  sizetype again = 0, used = 0, collisions = 0; \
Pekka Pessi's avatar
Pekka Pessi committed
155 156 157 158 159 160 161
\
  (void)realloc_arg; \
\
  if (new_size == 0) \
    new_size = 2 * pr->pr##size + 1; \
  if (new_size < HTABLE2_MIN_SIZE) \
    new_size = HTABLE2_MIN_SIZE; \
162 163
  if (new_size < 5 * pr->pr##used / 4) \
    new_size = 5 * pr->pr##used / 4; \
Pekka Pessi's avatar
Pekka Pessi committed
164 165 166 167
\
  if (!(new_hash = halloc(realloc_arg, NULL, sizeof(*new_hash) * new_size))) \
    return -1; \
\
168 169 170
  for (i = 0; i < new_size; i++) { \
    (reclaim(&new_hash[i])); \
  } \
Pekka Pessi's avatar
Pekka Pessi committed
171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194
  old_size = pr->pr##size; \
\
  do for (j = 0; j < old_size; j++) { \
    if (!is_used(old_hash[j])) \
      continue; \
\
    if (again < 2 && hfun(old_hash[j]) % old_size > j) { \
      /* Wrapped, leave entry for second pass */ \
      again = 1; continue; \
    } \
\
    i0 = hfun(old_hash[j]) % new_size; \
\
    for (i = i0; is_used(new_hash[i]); \
         i = (i + 1) % new_size, assert(i != i0)) \
      collisions++; \
\
    new_hash[i] = old_hash[j]; reclaim(&old_hash[j]); \
    used++; \
  } \
  while (again++ == 1); \
\
  pr->pr##table = new_hash, pr->pr##size = new_size; \
\
Pekka Pessi's avatar
Pekka Pessi committed
195
  if (old_hash) old_hash = halloc(realloc_arg, old_hash, 0);	\
Pekka Pessi's avatar
Pekka Pessi committed
196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
\
  assert(pr->pr##used == used);\
\
  return 0; \
} \
\
HTABLE2_SCOPE \
int prefix##_is_full(type const *pr) \
{ \
  return pr->pr##table == NULL || 3 * pr->pr##used > 2 * pr->pr##size; \
} \
\
HTABLE2_SCOPE \
entrytype *prefix##_hash(type const *pr, hash_value_t hv) \
{ \
  return pr->pr##table + hv % pr->pr##size; \
} \
\
HTABLE2_SCOPE \
entrytype *prefix##_next(type const *pr, entrytype *ee) \
{ \
  if (++ee < pr->pr##table + pr->pr##size && ee >= pr->pr##table) \
    return ee; \
  else \
    return pr->pr##table; \
}  \
\
HTABLE2_SCOPE \
224
entrytype *prefix##_append(type *pr, entrytype e) \
Pekka Pessi's avatar
Pekka Pessi committed
225 226
{ \
  entrytype *ee; \
227 228 229 230
\
  assert(pr->pr##used < pr->pr##size); \
  if (pr->pr##used == pr->pr##size) \
    return (entrytype *)0; \
Pekka Pessi's avatar
Pekka Pessi committed
231 232 233 234 235 236 237
\
  pr->pr##used++; \
  for (ee = prefix##_hash(pr, hfun(e)); \
       is_used(*ee); \
       ee = prefix##_next(pr, ee)) \
   ; \
  *ee = e; \
238 239
\
  return ee; \
Pekka Pessi's avatar
Pekka Pessi committed
240 241 242
} \
\
HTABLE2_SCOPE \
243
entrytype *prefix##_insert(type *pr, entrytype e) \
Pekka Pessi's avatar
Pekka Pessi committed
244 245 246
{ \
  entrytype e0; \
  entrytype *ee; \
247 248 249 250
\
  assert(pr->pr##used < pr->pr##size); \
  if (pr->pr##used == pr->pr##size) \
    return (entrytype *)0; \
Pekka Pessi's avatar
Pekka Pessi committed
251 252 253 254 255 256 257 258
\
  pr->pr##used++; \
  /* Insert entry into hash table (before other entries with same hash) */ \
  for (ee = prefix##_hash(pr, hfun(e));  \
       is_used((*ee)); \
       ee = prefix##_next(pr, ee)) \
    *ee = e, e = e0; \
  *ee = e; \
259 260
\
  return ee; \
Pekka Pessi's avatar
Pekka Pessi committed
261 262 263 264 265
} \
\
HTABLE2_SCOPE \
int prefix##_remove(type *pr, entrytype const e) \
{ \
266
  sizetype i, j, k, size = pr->pr##size; \
Pekka Pessi's avatar
Pekka Pessi committed
267 268 269 270 271 272 273
  entrytype *htable = pr->pr##table; \
\
  /* Search for entry */ \
  for (i = hfun(e) % size; is_used(htable[i]); i = (i + 1) % size) \
    if (is_equal(e, htable[i])) \
      break; \
\
274
  if (!is_used(htable[i])) return -1; \
Pekka Pessi's avatar
Pekka Pessi committed
275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296
\
  /* Move table entries towards their primary place  */ \
  for (j = (i + 1) % size; is_used(htable[j]); j = (j + 1) % size) { \
    /* k is primary place for entry */ \
    k = hfun(htable[j]) % size; \
    if (k == j)			/* entry is in its primary place? */ \
      continue; \
    /* primary place is between i and j - do not move this to i */ \
    if (j > i ? (i < k && k < j) : (i < k || k < j)) \
      continue; \
\
    htable[i] = htable[j], i = j; \
  } \
\
  pr->pr##used--; \
\
  reclaim(&htable[i]); \
\
  return 0; \
} \
extern int const prefix##_dummy

297 298 299
#define HTABLE2_BODIES(type, prefix, pr, entrytype, \
		        hfun, is_used, reclaim, is_equal, halloc) \
  HTABLE2_BODIES2(type, prefix, pr, entrytype, unsigned, \
300
		        hfun, is_used, reclaim, is_equal, halloc)
301 302


Pekka Pessi's avatar
Pekka Pessi committed
303
#endif /** !defined(HTABLE2_H) */