\doxysubsection{hashtable.\+h}
\label{hashtable_8h_source}\index{hashtable.h@{hashtable.h}}
\mbox{\hyperlink{hashtable_8h}{Go to the documentation of this file.}}
\begin{DoxyCode}{0}
\DoxyCodeLine{00001 \textcolor{comment}{/*= -\/*-\/ c-\/basic-\/offset: 4; indent-\/tabs-\/mode: nil; -\/*-\/}}
\DoxyCodeLine{00002 \textcolor{comment}{ *}}
\DoxyCodeLine{00003 \textcolor{comment}{ * hashtable.h -\/-\/ a generic open addressing hashtable.}}
\DoxyCodeLine{00004 \textcolor{comment}{ *}}
\DoxyCodeLine{00005 \textcolor{comment}{ * Copyright (C) 2003 by Donovan Baarda <abo@minkirri.apana.org.au>}}
\DoxyCodeLine{00006 \textcolor{comment}{ *}}
\DoxyCodeLine{00007 \textcolor{comment}{ * This program is free software; you can redistribute it and/or modify}}
\DoxyCodeLine{00008 \textcolor{comment}{ * it under the terms of the GNU Lesser General Public License as published by}}
\DoxyCodeLine{00009 \textcolor{comment}{ * the Free Software Foundation; either version 2.1 of the License, or}}
\DoxyCodeLine{00010 \textcolor{comment}{ * (at your option) any later version.}}
\DoxyCodeLine{00011 \textcolor{comment}{ *}}
\DoxyCodeLine{00012 \textcolor{comment}{ * This program is distributed in the hope that it will be useful,}}
\DoxyCodeLine{00013 \textcolor{comment}{ * but WITHOUT ANY WARRANTY; without even the implied warranty of}}
\DoxyCodeLine{00014 \textcolor{comment}{ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the}}
\DoxyCodeLine{00015 \textcolor{comment}{ * GNU Lesser General Public License for more details.}}
\DoxyCodeLine{00016 \textcolor{comment}{ *}}
\DoxyCodeLine{00017 \textcolor{comment}{ * You should have received a copy of the GNU Lesser General Public License}}
\DoxyCodeLine{00018 \textcolor{comment}{ * along with this program; if not, write to the Free Software}}
\DoxyCodeLine{00019 \textcolor{comment}{ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */}}
\DoxyCodeLine{00020 \textcolor{comment}{}}
\DoxyCodeLine{00021 \textcolor{comment}{/** \(\backslash\)file hashtable.h}}
\DoxyCodeLine{00022 \textcolor{comment}{ * A generic open addressing hashtable.}}
\DoxyCodeLine{00023 \textcolor{comment}{ *}}
\DoxyCodeLine{00024 \textcolor{comment}{ * This is a minimal hashtable containing pointers to arbitrary entries with}}
\DoxyCodeLine{00025 \textcolor{comment}{ * configurable hashtable size and support for custom hash() and cmp() methods.}}
\DoxyCodeLine{00026 \textcolor{comment}{ * The cmp() method can either be a simple comparison between two keys, or can}}
\DoxyCodeLine{00027 \textcolor{comment}{ * be against a special match object containing additional mutable state. This}}
\DoxyCodeLine{00028 \textcolor{comment}{ * allows for things like deferred and cached evaluation of costly comparison}}
\DoxyCodeLine{00029 \textcolor{comment}{ * data. The hash() function doesn't need to avoid clustering behaviour.}}
\DoxyCodeLine{00030 \textcolor{comment}{ *}}
\DoxyCodeLine{00031 \textcolor{comment}{ * It uses open addressing with quadratic probing for collisions. The}}
\DoxyCodeLine{00032 \textcolor{comment}{ * MurmurHash3 finalization function is optionally used on the hash() output to}}
\DoxyCodeLine{00033 \textcolor{comment}{ * avoid clustering and can be disabled by setting HASHTABLE\_NMIX32. There is}}
\DoxyCodeLine{00034 \textcolor{comment}{ * no support for removing entries, only adding them. Multiple entries with the}}
\DoxyCodeLine{00035 \textcolor{comment}{ * same key can be added, and you can use a fancy cmp() function to find}}
\DoxyCodeLine{00036 \textcolor{comment}{ * particular entries by more than just their key. There is an iterator for}}
\DoxyCodeLine{00037 \textcolor{comment}{ * iterating through all entries in the hashtable. There are optional}}
\DoxyCodeLine{00038 \textcolor{comment}{ * NAME\_find() find/match/hashcmp/entrycmp stats counters that can be disabled}}
\DoxyCodeLine{00039 \textcolor{comment}{ * by defining HASHTABLE\_NSTATS. There is an optional simple k=1 bloom filter}}
\DoxyCodeLine{00040 \textcolor{comment}{ * for speed that can be disabled by defining HASHTABLE\_NBLOOM.}}
\DoxyCodeLine{00041 \textcolor{comment}{ *}}
\DoxyCodeLine{00042 \textcolor{comment}{ * The types and methods of the hashtable and its contents are specified by}}
\DoxyCodeLine{00043 \textcolor{comment}{ * using \(\backslash\)\#define parameters set to their basenames (the prefixes for the *\_t}}
\DoxyCodeLine{00044 \textcolor{comment}{ * type and *\_func() methods) before doing \(\backslash\)\#include "{}hashtable.h"{}. This}}
\DoxyCodeLine{00045 \textcolor{comment}{ * produces static inline type-\/safe methods that are either application}}
\DoxyCodeLine{00046 \textcolor{comment}{ * optimized for speed or wrappers around void* implementation methods for}}
\DoxyCodeLine{00047 \textcolor{comment}{ * compactness.}}
\DoxyCodeLine{00048 \textcolor{comment}{ *}}
\DoxyCodeLine{00049 \textcolor{comment}{ * \(\backslash\)param ENTRY -\/ the entry type basename.}}
\DoxyCodeLine{00050 \textcolor{comment}{ *}}
\DoxyCodeLine{00051 \textcolor{comment}{ * \(\backslash\)param KEY -\/ optional key type basename (default: ENTRY).}}
\DoxyCodeLine{00052 \textcolor{comment}{ *}}
\DoxyCodeLine{00053 \textcolor{comment}{ * \(\backslash\)param MATCH -\/ optional match type basename (default: KEY).}}
\DoxyCodeLine{00054 \textcolor{comment}{ *}}
\DoxyCodeLine{00055 \textcolor{comment}{ * \(\backslash\)param NAME -\/ optional hashtable type basename (default: ENTRY\_hashtable).}}
\DoxyCodeLine{00056 \textcolor{comment}{ *}}
\DoxyCodeLine{00057 \textcolor{comment}{ * Example: \(\backslash\)code}}
\DoxyCodeLine{00058 \textcolor{comment}{ *   typedef ... mykey\_t;}}
\DoxyCodeLine{00059 \textcolor{comment}{ *   int mykey\_hash(mykey\_t const *e);}}
\DoxyCodeLine{00060 \textcolor{comment}{ *   int mykey\_cmp(mykey\_t *e, mykey\_t const *o);}}
\DoxyCodeLine{00061 \textcolor{comment}{ *}}
\DoxyCodeLine{00062 \textcolor{comment}{ *   typedef struct myentry \{}}
\DoxyCodeLine{00063 \textcolor{comment}{ *     mykey\_t key;  // Inherit from mykey\_t.}}
\DoxyCodeLine{00064 \textcolor{comment}{ *     ...extra entry value data...}}
\DoxyCodeLine{00065 \textcolor{comment}{ *   \} myentry\_t;}}
\DoxyCodeLine{00066 \textcolor{comment}{ *   void myentry\_init(myentry\_t *e, ...);}}
\DoxyCodeLine{00067 \textcolor{comment}{ *}}
\DoxyCodeLine{00068 \textcolor{comment}{ *   \#define ENTRY myentry}}
\DoxyCodeLine{00069 \textcolor{comment}{ *   \#define KEY mykey}}
\DoxyCodeLine{00070 \textcolor{comment}{ *   \#include "{}hashtable.h"{}}}
\DoxyCodeLine{00071 \textcolor{comment}{ *}}
\DoxyCodeLine{00072 \textcolor{comment}{ *   hashtable\_t *t;}}
\DoxyCodeLine{00073 \textcolor{comment}{ *   myentry\_t entries[300];}}
\DoxyCodeLine{00074 \textcolor{comment}{ *   mykey\_t k;}}
\DoxyCodeLine{00075 \textcolor{comment}{ *   myentry\_t *e;}}
\DoxyCodeLine{00076 \textcolor{comment}{ *}}
\DoxyCodeLine{00077 \textcolor{comment}{ *   t = myentry\_hashtable\_new(300);}}
\DoxyCodeLine{00078 \textcolor{comment}{ *   myentry\_init(\&entries[5], ...);}}
\DoxyCodeLine{00079 \textcolor{comment}{ *   myentry\_hashtable\_add(t, \&entries[5]);}}
\DoxyCodeLine{00080 \textcolor{comment}{ *   k = ...;}}
\DoxyCodeLine{00081 \textcolor{comment}{ *   e = myentry\_hashtable\_find(t, \&k);}}
\DoxyCodeLine{00082 \textcolor{comment}{ *}}
\DoxyCodeLine{00083 \textcolor{comment}{ *   int i;}}
\DoxyCodeLine{00084 \textcolor{comment}{ *   for (e = myentry\_hashtable\_iter(t, \&i); e != NULL;}}
\DoxyCodeLine{00085 \textcolor{comment}{ *        e = myentry\_hashtable\_next(t, \&i))}}
\DoxyCodeLine{00086 \textcolor{comment}{ *     ...}}
\DoxyCodeLine{00087 \textcolor{comment}{ *}}
\DoxyCodeLine{00088 \textcolor{comment}{ *   myentry\_hashtable\_free(t);}}
\DoxyCodeLine{00089 \textcolor{comment}{ * \(\backslash\)endcode}}
\DoxyCodeLine{00090 \textcolor{comment}{ *}}
\DoxyCodeLine{00091 \textcolor{comment}{ * The mykey\_hash() and mykey\_cmp() fuctions will typically take pointers to}}
\DoxyCodeLine{00092 \textcolor{comment}{ * mykey/myentry instances the same as the pointers stored in the hashtable.}}
\DoxyCodeLine{00093 \textcolor{comment}{ * However it is also possible for them to take "{}match objects"{} that are a}}
\DoxyCodeLine{00094 \textcolor{comment}{ * "{}subclass"{} of the entry type that contain additional state for complicated}}
\DoxyCodeLine{00095 \textcolor{comment}{ * comparision operations.}}
\DoxyCodeLine{00096 \textcolor{comment}{ *}}
\DoxyCodeLine{00097 \textcolor{comment}{ * Example: \(\backslash\)code}}
\DoxyCodeLine{00098 \textcolor{comment}{ *   typedef struct mymatch \{}}
\DoxyCodeLine{00099 \textcolor{comment}{ *     mykey\_t key;  // Inherit from mykey\_t;}}
\DoxyCodeLine{00100 \textcolor{comment}{ *     ...extra match criteria and state data...}}
\DoxyCodeLine{00101 \textcolor{comment}{ *   \} mymatch\_t;}}
\DoxyCodeLine{00102 \textcolor{comment}{ *   int mymatch\_cmp(mymatch\_t *m, myentry\_t const *e);}}
\DoxyCodeLine{00103 \textcolor{comment}{ *}}
\DoxyCodeLine{00104 \textcolor{comment}{ *   \#define ENTRY myentry}}
\DoxyCodeLine{00105 \textcolor{comment}{ *   \#define KEY mykey}}
\DoxyCodeLine{00106 \textcolor{comment}{ *   \#define MATCH mymatch}}
\DoxyCodeLine{00107 \textcolor{comment}{ *   \#include "{}hashtable.h"{}}}
\DoxyCodeLine{00108 \textcolor{comment}{ *}}
\DoxyCodeLine{00109 \textcolor{comment}{ *   ...}}
\DoxyCodeLine{00110 \textcolor{comment}{ *   mymatch\_t m;}}
\DoxyCodeLine{00111 \textcolor{comment}{ *}}
\DoxyCodeLine{00112 \textcolor{comment}{ *   t = myentry\_hashtable\_new(300);}}
\DoxyCodeLine{00113 \textcolor{comment}{ *   ...}}
\DoxyCodeLine{00114 \textcolor{comment}{ *   m = ...;}}
\DoxyCodeLine{00115 \textcolor{comment}{ *   e = myentry\_hashtable\_find(t, \&m);}}
\DoxyCodeLine{00116 \textcolor{comment}{ * \(\backslash\)endcode}}
\DoxyCodeLine{00117 \textcolor{comment}{ *}}
\DoxyCodeLine{00118 \textcolor{comment}{ * The mymatch\_cmp() function is only called for finding hashtable entries and}}
\DoxyCodeLine{00119 \textcolor{comment}{ * can mutate the mymatch\_t object for doing things like deferred and cached}}
\DoxyCodeLine{00120 \textcolor{comment}{ * evaluation of expensive match data. It can also access the whole myentry\_t}}
\DoxyCodeLine{00121 \textcolor{comment}{ * object to match against more than just the key. */}}
\DoxyCodeLine{00122 \textcolor{preprocessor}{\#ifndef HASHTABLE\_H}}
\DoxyCodeLine{00123 \textcolor{preprocessor}{\#  define HASHTABLE\_H}}
\DoxyCodeLine{00124 }
\DoxyCodeLine{00125 \textcolor{preprocessor}{\#  include <stdbool.h>}}
\DoxyCodeLine{00126 \textcolor{comment}{}}
\DoxyCodeLine{00127 \textcolor{comment}{/** The hashtable type. */}}
\DoxyCodeLine{00128 \textcolor{keyword}{typedef} \textcolor{keyword}{struct }hashtable \{}
\DoxyCodeLine{00129     \textcolor{keywordtype}{int} size;                   \textcolor{comment}{/**< Size of allocated hashtable. */}}
\DoxyCodeLine{00130     \textcolor{keywordtype}{int} count;                  \textcolor{comment}{/**< Number of entries in hashtable. */}}
\DoxyCodeLine{00131     \textcolor{keywordtype}{unsigned} tmask;             \textcolor{comment}{/**< Mask to get the hashtable index. */}}
\DoxyCodeLine{00132 \textcolor{preprocessor}{\#  ifndef HASHTABLE\_NBLOOM}}
\DoxyCodeLine{00133     \textcolor{keywordtype}{unsigned} bshift;            \textcolor{comment}{/**< Shift to get the bloomfilter index. */}}
\DoxyCodeLine{00134 \textcolor{preprocessor}{\#  endif}}
\DoxyCodeLine{00135 \textcolor{preprocessor}{\#  ifndef HASHTABLE\_NSTATS}}
\DoxyCodeLine{00136     \textcolor{comment}{/* The following are for accumulating NAME\_find() stats. */}}
\DoxyCodeLine{00137     \textcolor{keywordtype}{long} find\_count;            \textcolor{comment}{/**< The count of finds tried. */}}
\DoxyCodeLine{00138     \textcolor{keywordtype}{long} match\_count;           \textcolor{comment}{/**< The count of matches found. */}}
\DoxyCodeLine{00139     \textcolor{keywordtype}{long} hashcmp\_count;         \textcolor{comment}{/**< The count of hash compares done. */}}
\DoxyCodeLine{00140     \textcolor{keywordtype}{long} entrycmp\_count;        \textcolor{comment}{/**< The count of entry compares done. */}}
\DoxyCodeLine{00141 \textcolor{preprocessor}{\#  endif}}
\DoxyCodeLine{00142 \textcolor{preprocessor}{\#  ifndef HASHTABLE\_NBLOOM}}
\DoxyCodeLine{00143     \textcolor{keywordtype}{unsigned} \textcolor{keywordtype}{char} *kbloom;      \textcolor{comment}{/**< Bloom filter of hash keys with k=1. */}}
\DoxyCodeLine{00144 \textcolor{preprocessor}{\#  endif}}
\DoxyCodeLine{00145     \textcolor{keywordtype}{void} **etable;              \textcolor{comment}{/**< Table of pointers to entries. */}}
\DoxyCodeLine{00146     \textcolor{keywordtype}{unsigned} ktable[];          \textcolor{comment}{/**< Table of hash keys. */}}
\DoxyCodeLine{00147 \} hashtable\_t;}
\DoxyCodeLine{00148 }
\DoxyCodeLine{00149 \textcolor{comment}{/* void* implementations for the type-\/safe static inline wrappers below. */}}
\DoxyCodeLine{00150 hashtable\_t *\_hashtable\_new(\textcolor{keywordtype}{int} size);}
\DoxyCodeLine{00151 \textcolor{keywordtype}{void} \_hashtable\_free(hashtable\_t *t);}
\DoxyCodeLine{00152 }
\DoxyCodeLine{00153 \textcolor{preprocessor}{\#  ifndef HASHTABLE\_NBLOOM}}
\DoxyCodeLine{00154 \textcolor{keyword}{static} \textcolor{keyword}{inline} \textcolor{keywordtype}{void} hashtable\_setbloom(hashtable\_t *t, \textcolor{keywordtype}{unsigned} \textcolor{keyword}{const} h)}
\DoxyCodeLine{00155 \{}
\DoxyCodeLine{00156     \textcolor{comment}{/* Use upper bits for a "{}different hash"{}. */}}
\DoxyCodeLine{00157     \textcolor{keywordtype}{unsigned} \textcolor{keyword}{const} i = h >> t-\/>bshift;}
\DoxyCodeLine{00158     t-\/>kbloom[i / 8] |= (\textcolor{keywordtype}{unsigned} char)(1 << (i \% 8));}
\DoxyCodeLine{00159 \}}
\DoxyCodeLine{00160 }
\DoxyCodeLine{00161 \textcolor{keyword}{static} \textcolor{keyword}{inline} \textcolor{keywordtype}{bool} hashtable\_getbloom(hashtable\_t *t, \textcolor{keywordtype}{unsigned} \textcolor{keyword}{const} h)}
\DoxyCodeLine{00162 \{}
\DoxyCodeLine{00163     \textcolor{comment}{/* Use upper bits for a "{}different hash"{}. */}}
\DoxyCodeLine{00164     \textcolor{keywordtype}{unsigned} \textcolor{keyword}{const} i = h >> t-\/>bshift;}
\DoxyCodeLine{00165     \textcolor{keywordflow}{return} (t-\/>kbloom[i / 8] >> (i \% 8)) \& 1;}
\DoxyCodeLine{00166 \}}
\DoxyCodeLine{00167 \textcolor{preprocessor}{\#  endif}}
\DoxyCodeLine{00168 \textcolor{comment}{}}
\DoxyCodeLine{00169 \textcolor{comment}{/** MurmurHash3 finalization mix function. */}}
\DoxyCodeLine{00170 \textcolor{keyword}{static} \textcolor{keyword}{inline} \textcolor{keywordtype}{unsigned} mix32(\textcolor{keywordtype}{unsigned} h)}
\DoxyCodeLine{00171 \{}
\DoxyCodeLine{00172     h \string^= h >> 16;}
\DoxyCodeLine{00173     h *= 0x85ebca6b;}
\DoxyCodeLine{00174     h \string^= h >> 13;}
\DoxyCodeLine{00175     h *= 0xc2b2ae35;}
\DoxyCodeLine{00176     h \string^= h >> 16;}
\DoxyCodeLine{00177     \textcolor{keywordflow}{return} h;}
\DoxyCodeLine{00178 \}}
\DoxyCodeLine{00179 \textcolor{comment}{}}
\DoxyCodeLine{00180 \textcolor{comment}{/** Ensure hash's are never zero. */}}
\DoxyCodeLine{00181 \textcolor{keyword}{static} \textcolor{keyword}{inline} \textcolor{keywordtype}{unsigned} nozero(\textcolor{keywordtype}{unsigned} h)}
\DoxyCodeLine{00182 \{}
\DoxyCodeLine{00183     \textcolor{keywordflow}{return} h ? h : (unsigned)-\/1;}
\DoxyCodeLine{00184 \}}
\DoxyCodeLine{00185 }
\DoxyCodeLine{00186 \textcolor{preprocessor}{\#endif                          }\textcolor{comment}{/* !HASHTABLE\_H */}\textcolor{preprocessor}{}}
\DoxyCodeLine{00187 }
\DoxyCodeLine{00188 \textcolor{comment}{/* If ENTRY is defined, define type-\/dependent static inline methods. */}}
\DoxyCodeLine{00189 \textcolor{preprocessor}{\#ifdef ENTRY}}
\DoxyCodeLine{00190 }
\DoxyCodeLine{00191 \textcolor{preprocessor}{\#  include <assert.h>}}
\DoxyCodeLine{00192 \textcolor{preprocessor}{\#  include <stddef.h>}}
\DoxyCodeLine{00193 }
\DoxyCodeLine{00194 \textcolor{preprocessor}{\#  define \_JOIN2(x, y) x\#\#y}}
\DoxyCodeLine{00195 \textcolor{preprocessor}{\#  define \_JOIN(x, y) \_JOIN2(x, y)}}
\DoxyCodeLine{00196 }
\DoxyCodeLine{00197 \textcolor{preprocessor}{\#  ifndef KEY}}
\DoxyCodeLine{00198 \textcolor{preprocessor}{\#    define KEY ENTRY}}
\DoxyCodeLine{00199 \textcolor{preprocessor}{\#  endif}}
\DoxyCodeLine{00200 }
\DoxyCodeLine{00201 \textcolor{preprocessor}{\#  ifndef MATCH}}
\DoxyCodeLine{00202 \textcolor{preprocessor}{\#    define MATCH KEY}}
\DoxyCodeLine{00203 \textcolor{preprocessor}{\#  endif}}
\DoxyCodeLine{00204 }
\DoxyCodeLine{00205 \textcolor{preprocessor}{\#  ifndef NAME}}
\DoxyCodeLine{00206 \textcolor{preprocessor}{\#    define NAME \_JOIN(ENTRY, \_hashtable)}}
\DoxyCodeLine{00207 \textcolor{preprocessor}{\#  endif}}
\DoxyCodeLine{00208 }
\DoxyCodeLine{00209 \textcolor{preprocessor}{\#  define ENTRY\_t \_JOIN(ENTRY, \_t)      }\textcolor{comment}{/**< The entry type. */}\textcolor{preprocessor}{}}
\DoxyCodeLine{00210 \textcolor{preprocessor}{\#  define KEY\_t \_JOIN(KEY, \_t)  }\textcolor{comment}{/**< The key type. */}\textcolor{preprocessor}{}}
\DoxyCodeLine{00211 \textcolor{preprocessor}{\#  define MATCH\_t \_JOIN(MATCH, \_t)      }\textcolor{comment}{/**< The match type. */}\textcolor{preprocessor}{}}
\DoxyCodeLine{00212 \textcolor{preprocessor}{\#  define KEY\_hash \_JOIN(KEY, \_hash)    }\textcolor{comment}{/**< The key hash(k) method. */}\textcolor{preprocessor}{}}
\DoxyCodeLine{00213 \textcolor{preprocessor}{\#  define MATCH\_cmp \_JOIN(MATCH, \_cmp)  }\textcolor{comment}{/**< The match cmp(m, e) method. */}\textcolor{preprocessor}{}}
\DoxyCodeLine{00214 \textcolor{comment}{/* The names for all the hashtable methods. */}}
\DoxyCodeLine{00215 \textcolor{preprocessor}{\#  define NAME\_new \_JOIN(NAME, \_new)}}
\DoxyCodeLine{00216 \textcolor{preprocessor}{\#  define NAME\_free \_JOIN(NAME, \_free)}}
\DoxyCodeLine{00217 \textcolor{preprocessor}{\#  define NAME\_stats\_init \_JOIN(NAME, \_stats\_init)}}
\DoxyCodeLine{00218 \textcolor{preprocessor}{\#  define NAME\_add \_JOIN(NAME, \_add)}}
\DoxyCodeLine{00219 \textcolor{preprocessor}{\#  define NAME\_find \_JOIN(NAME, \_find)}}
\DoxyCodeLine{00220 \textcolor{preprocessor}{\#  define NAME\_iter \_JOIN(NAME, \_iter)}}
\DoxyCodeLine{00221 \textcolor{preprocessor}{\#  define NAME\_next \_JOIN(NAME, \_next)}}
\DoxyCodeLine{00222 }
\DoxyCodeLine{00223 \textcolor{comment}{/* Modified hash() with/without mix32() and reserving zero for empty buckets. */}}
\DoxyCodeLine{00224 \textcolor{preprocessor}{\#  ifdef HASHTABLE\_NMIX32}}
\DoxyCodeLine{00225 \textcolor{preprocessor}{\#    define \_KEY\_HASH(k) nozero(KEY\_hash((KEY\_t *)k))}}
\DoxyCodeLine{00226 \textcolor{preprocessor}{\#  else}}
\DoxyCodeLine{00227 \textcolor{preprocessor}{\#    define \_KEY\_HASH(k) nozero(mix32(KEY\_hash((KEY\_t *)k)))}}
\DoxyCodeLine{00228 \textcolor{preprocessor}{\#  endif}}
\DoxyCodeLine{00229 }
\DoxyCodeLine{00230 \textcolor{comment}{/* Loop macro for probing table t for key hash hk, iterating with index i and}}
\DoxyCodeLine{00231 \textcolor{comment}{   entry hash h, terminating at an empty bucket. */}}
\DoxyCodeLine{00232 \textcolor{preprocessor}{\#  define \_for\_probe(t, hk, i, h) \(\backslash\)}}
\DoxyCodeLine{00233 \textcolor{preprocessor}{    unsigned const *const ktable = t-\/>ktable;\(\backslash\)}}
\DoxyCodeLine{00234 \textcolor{preprocessor}{    unsigned const tmask = t-\/>tmask;\(\backslash\)}}
\DoxyCodeLine{00235 \textcolor{preprocessor}{    unsigned i, s, h;\(\backslash\)}}
\DoxyCodeLine{00236 \textcolor{preprocessor}{    for (i = hk \& tmask, s = 0; (h = ktable[i]); i = (i + ++s) \& tmask)}}
\DoxyCodeLine{00237 }
\DoxyCodeLine{00238 \textcolor{comment}{/* Conditional macro for incrementing stats counters. */}}
\DoxyCodeLine{00239 \textcolor{preprocessor}{\#  ifndef HASHTABLE\_NSTATS}}
\DoxyCodeLine{00240 \textcolor{preprocessor}{\#    define \_stats\_inc(c) (c++)}}
\DoxyCodeLine{00241 \textcolor{preprocessor}{\#  else}}
\DoxyCodeLine{00242 \textcolor{preprocessor}{\#    define \_stats\_inc(c)}}
\DoxyCodeLine{00243 \textcolor{preprocessor}{\#  endif}}
\DoxyCodeLine{00244 \textcolor{comment}{}}
\DoxyCodeLine{00245 \textcolor{comment}{/** Allocate and initialize a hashtable instance.}}
\DoxyCodeLine{00246 \textcolor{comment}{ *}}
\DoxyCodeLine{00247 \textcolor{comment}{ * The provided size is used as an indication of the number of entries you wish}}
\DoxyCodeLine{00248 \textcolor{comment}{ * to add, but the allocated size will probably be larger depending on the}}
\DoxyCodeLine{00249 \textcolor{comment}{ * implementation to enable optimisations or avoid degraded performance. It may}}
\DoxyCodeLine{00250 \textcolor{comment}{ * be possible to fill the table beyond the requested size, but performance can}}
\DoxyCodeLine{00251 \textcolor{comment}{ * start to degrade badly if it is over filled.}}
\DoxyCodeLine{00252 \textcolor{comment}{ *}}
\DoxyCodeLine{00253 \textcolor{comment}{ * \(\backslash\)param size -\/ The desired minimum size of the hash table.}}
\DoxyCodeLine{00254 \textcolor{comment}{ *}}
\DoxyCodeLine{00255 \textcolor{comment}{ * \(\backslash\)return The initialized hashtable instance or NULL if it failed. */}}
\DoxyCodeLine{00256 \textcolor{keyword}{static} \textcolor{keyword}{inline} hashtable\_t *NAME\_new(\textcolor{keywordtype}{int} size)}
\DoxyCodeLine{00257 \{}
\DoxyCodeLine{00258     \textcolor{keywordflow}{return} \_hashtable\_new(size);}
\DoxyCodeLine{00259 \}}
\DoxyCodeLine{00260 \textcolor{comment}{}}
\DoxyCodeLine{00261 \textcolor{comment}{/** Destroy and free a hashtable instance.}}
\DoxyCodeLine{00262 \textcolor{comment}{ *}}
\DoxyCodeLine{00263 \textcolor{comment}{ * This will free the hashtable, but will not free the entries in the}}
\DoxyCodeLine{00264 \textcolor{comment}{ * hashtable. If you want to free the entries too, use a hashtable iterator to}}
\DoxyCodeLine{00265 \textcolor{comment}{ * free the the entries first.}}
\DoxyCodeLine{00266 \textcolor{comment}{ *}}
\DoxyCodeLine{00267 \textcolor{comment}{ * \(\backslash\)param *t -\/ The hashtable to destroy and free. */}}
\DoxyCodeLine{00268 \textcolor{keyword}{static} \textcolor{keyword}{inline} \textcolor{keywordtype}{void} NAME\_free(hashtable\_t *t)}
\DoxyCodeLine{00269 \{}
\DoxyCodeLine{00270     \_hashtable\_free(t);}
\DoxyCodeLine{00271 \}}
\DoxyCodeLine{00272 \textcolor{comment}{}}
\DoxyCodeLine{00273 \textcolor{comment}{/** Initialize hashtable stats counters.}}
\DoxyCodeLine{00274 \textcolor{comment}{ *}}
\DoxyCodeLine{00275 \textcolor{comment}{ * This will reset all the stats counters for the hashtable,}}
\DoxyCodeLine{00276 \textcolor{comment}{ *}}
\DoxyCodeLine{00277 \textcolor{comment}{ * \(\backslash\)param *t -\/ The hashtable to initializ stats for. */}}
\DoxyCodeLine{00278 \textcolor{keyword}{static} \textcolor{keyword}{inline} \textcolor{keywordtype}{void} NAME\_stats\_init(hashtable\_t *t)}
\DoxyCodeLine{00279 \{}
\DoxyCodeLine{00280 \textcolor{preprocessor}{\#  ifndef HASHTABLE\_NSTATS}}
\DoxyCodeLine{00281     t-\/>find\_count = t-\/>match\_count = t-\/>hashcmp\_count = t-\/>entrycmp\_count = 0;}
\DoxyCodeLine{00282 \textcolor{preprocessor}{\#  endif}}
\DoxyCodeLine{00283 \}}
\DoxyCodeLine{00284 \textcolor{comment}{}}
\DoxyCodeLine{00285 \textcolor{comment}{/** Add an entry to a hashtable.}}
\DoxyCodeLine{00286 \textcolor{comment}{ *}}
\DoxyCodeLine{00287 \textcolor{comment}{ * This doesn't use MATCH\_cmp() or do any checks for existing copies or}}
\DoxyCodeLine{00288 \textcolor{comment}{ * instances, so it will add duplicates. If you want to avoid adding}}
\DoxyCodeLine{00289 \textcolor{comment}{ * duplicates, use NAME\_find() to check for existing entries first.}}
\DoxyCodeLine{00290 \textcolor{comment}{ *}}
\DoxyCodeLine{00291 \textcolor{comment}{ * \(\backslash\)param *t -\/ The hashtable to add to.}}
\DoxyCodeLine{00292 \textcolor{comment}{ *}}
\DoxyCodeLine{00293 \textcolor{comment}{ * \(\backslash\)param *e -\/ The entry object to add.}}
\DoxyCodeLine{00294 \textcolor{comment}{ *}}
\DoxyCodeLine{00295 \textcolor{comment}{ * \(\backslash\)return The added entry, or NULL if the table is full. */}}
\DoxyCodeLine{00296 \textcolor{keyword}{static} \textcolor{keyword}{inline} ENTRY\_t *NAME\_add(hashtable\_t *t, ENTRY\_t *e)}
\DoxyCodeLine{00297 \{}
\DoxyCodeLine{00298     \textcolor{keywordtype}{unsigned} he = \_KEY\_HASH(e);}
\DoxyCodeLine{00299 }
\DoxyCodeLine{00300     assert(e != NULL);}
\DoxyCodeLine{00301     \textcolor{keywordflow}{if} (t-\/>count + 1 == t-\/>size)}
\DoxyCodeLine{00302         \textcolor{keywordflow}{return} NULL;}
\DoxyCodeLine{00303 \textcolor{preprocessor}{\#  ifndef HASHTABLE\_NBLOOM}}
\DoxyCodeLine{00304     hashtable\_setbloom(t, he);}
\DoxyCodeLine{00305 \textcolor{preprocessor}{\#  endif}}
\DoxyCodeLine{00306     \_for\_probe(t, he, i, h);}
\DoxyCodeLine{00307     t-\/>count++;}
\DoxyCodeLine{00308     t-\/>ktable[i] = he;}
\DoxyCodeLine{00309     \textcolor{keywordflow}{return} t-\/>etable[i] = e;}
\DoxyCodeLine{00310 \}}
\DoxyCodeLine{00311 \textcolor{comment}{}}
\DoxyCodeLine{00312 \textcolor{comment}{/** Find an entry in a hashtable.}}
\DoxyCodeLine{00313 \textcolor{comment}{ *}}
\DoxyCodeLine{00314 \textcolor{comment}{ * Uses MATCH\_cmp() to find the first matching entry in the table in the same}}
\DoxyCodeLine{00315 \textcolor{comment}{ * hash() bucket.}}
\DoxyCodeLine{00316 \textcolor{comment}{ *}}
\DoxyCodeLine{00317 \textcolor{comment}{ * \(\backslash\)param *t -\/ The hashtable to search.}}
\DoxyCodeLine{00318 \textcolor{comment}{ *}}
\DoxyCodeLine{00319 \textcolor{comment}{ * \(\backslash\)param *m -\/ The key or match object to search for.}}
\DoxyCodeLine{00320 \textcolor{comment}{ *}}
\DoxyCodeLine{00321 \textcolor{comment}{ * \(\backslash\)return The first found entry, or NULL if nothing was found. */}}
\DoxyCodeLine{00322 \textcolor{keyword}{static} \textcolor{keyword}{inline} ENTRY\_t *NAME\_find(hashtable\_t *t, MATCH\_t *m)}
\DoxyCodeLine{00323 \{}
\DoxyCodeLine{00324     assert(m != NULL);}
\DoxyCodeLine{00325     \textcolor{keywordtype}{unsigned} hm = \_KEY\_HASH(m);}
\DoxyCodeLine{00326     ENTRY\_t *e;}
\DoxyCodeLine{00327 }
\DoxyCodeLine{00328     \_stats\_inc(t-\/>find\_count);}
\DoxyCodeLine{00329 \textcolor{preprocessor}{\#  ifndef HASHTABLE\_NBLOOM}}
\DoxyCodeLine{00330     \textcolor{keywordflow}{if} (!hashtable\_getbloom(t, hm))}
\DoxyCodeLine{00331         \textcolor{keywordflow}{return} NULL;}
\DoxyCodeLine{00332 \textcolor{preprocessor}{\#  endif}}
\DoxyCodeLine{00333     \_for\_probe(t, hm, i, he) \{}
\DoxyCodeLine{00334         \_stats\_inc(t-\/>hashcmp\_count);}
\DoxyCodeLine{00335         \textcolor{keywordflow}{if} (hm == he) \{}
\DoxyCodeLine{00336             \_stats\_inc(t-\/>entrycmp\_count);}
\DoxyCodeLine{00337             \textcolor{keywordflow}{if} (!MATCH\_cmp(m, e = t-\/>etable[i])) \{}
\DoxyCodeLine{00338                 \_stats\_inc(t-\/>match\_count);}
\DoxyCodeLine{00339                 \textcolor{keywordflow}{return} e;}
\DoxyCodeLine{00340             \}}
\DoxyCodeLine{00341         \}}
\DoxyCodeLine{00342     \}}
\DoxyCodeLine{00343     \textcolor{comment}{/* Also count the compare for the empty bucket. */}}
\DoxyCodeLine{00344     \_stats\_inc(t-\/>hashcmp\_count);}
\DoxyCodeLine{00345     \textcolor{keywordflow}{return} NULL;}
\DoxyCodeLine{00346 \}}
\DoxyCodeLine{00347 }
\DoxyCodeLine{00348 \textcolor{keyword}{static} \textcolor{keyword}{inline} ENTRY\_t *NAME\_next(hashtable\_t *t, \textcolor{keywordtype}{int} *i);}
\DoxyCodeLine{00349 \textcolor{comment}{}}
\DoxyCodeLine{00350 \textcolor{comment}{/** Initialize a iteration and return the first entry.}}
\DoxyCodeLine{00351 \textcolor{comment}{ *}}
\DoxyCodeLine{00352 \textcolor{comment}{ * This works together with NAME\_next() for iterating through all entries in a}}
\DoxyCodeLine{00353 \textcolor{comment}{ * hashtable.}}
\DoxyCodeLine{00354 \textcolor{comment}{ *}}
\DoxyCodeLine{00355 \textcolor{comment}{ * Example: \(\backslash\)code}}
\DoxyCodeLine{00356 \textcolor{comment}{ *   for (e = NAME\_iter(t, \&i); e != NULL; e = NAME\_next(t, \&i))}}
\DoxyCodeLine{00357 \textcolor{comment}{ *     ...}}
\DoxyCodeLine{00358 \textcolor{comment}{ * \(\backslash\)endcode}}
\DoxyCodeLine{00359 \textcolor{comment}{ *}}
\DoxyCodeLine{00360 \textcolor{comment}{ * \(\backslash\)param *t -\/ the hashtable to iterate over.}}
\DoxyCodeLine{00361 \textcolor{comment}{ *}}
\DoxyCodeLine{00362 \textcolor{comment}{ * \(\backslash\)param *i -\/ the int iterator index to initialize.}}
\DoxyCodeLine{00363 \textcolor{comment}{ *}}
\DoxyCodeLine{00364 \textcolor{comment}{ * \(\backslash\)return The first entry or NULL if the hashtable is empty. */}}
\DoxyCodeLine{00365 \textcolor{keyword}{static} \textcolor{keyword}{inline} ENTRY\_t *NAME\_iter(hashtable\_t *t, \textcolor{keywordtype}{int} *i)}
\DoxyCodeLine{00366 \{}
\DoxyCodeLine{00367     assert(t != NULL);}
\DoxyCodeLine{00368     assert(i != NULL);}
\DoxyCodeLine{00369     *i = 0;}
\DoxyCodeLine{00370     \textcolor{keywordflow}{return} NAME\_next(t, i);}
\DoxyCodeLine{00371 \}}
\DoxyCodeLine{00372 \textcolor{comment}{}}
\DoxyCodeLine{00373 \textcolor{comment}{/** Get the next entry from a hashtable iterator or NULL when finished.}}
\DoxyCodeLine{00374 \textcolor{comment}{ *}}
\DoxyCodeLine{00375 \textcolor{comment}{ * This works together with NAME\_iter() for iterating through all entries in a}}
\DoxyCodeLine{00376 \textcolor{comment}{ * hashtable.}}
\DoxyCodeLine{00377 \textcolor{comment}{ *}}
\DoxyCodeLine{00378 \textcolor{comment}{ * \(\backslash\)param *t -\/ the hashtable to iterate over.}}
\DoxyCodeLine{00379 \textcolor{comment}{ *}}
\DoxyCodeLine{00380 \textcolor{comment}{ * \(\backslash\)param *i -\/ the int iterator index to use.}}
\DoxyCodeLine{00381 \textcolor{comment}{ *}}
\DoxyCodeLine{00382 \textcolor{comment}{ * \(\backslash\)return The next entry or NULL if the iterator is finished. */}}
\DoxyCodeLine{00383 \textcolor{keyword}{static} \textcolor{keyword}{inline} ENTRY\_t *NAME\_next(hashtable\_t *t, \textcolor{keywordtype}{int} *i)}
\DoxyCodeLine{00384 \{}
\DoxyCodeLine{00385     assert(t != NULL);}
\DoxyCodeLine{00386     assert(i != NULL);}
\DoxyCodeLine{00387     ENTRY\_t *e = NULL;}
\DoxyCodeLine{00388 }
\DoxyCodeLine{00389     \textcolor{keywordflow}{while} ((*i < t-\/>size) \&\& !(e = t-\/>etable[(*i)++])) ;}
\DoxyCodeLine{00390     \textcolor{keywordflow}{return} e;}
\DoxyCodeLine{00391 \}}
\DoxyCodeLine{00392 }
\DoxyCodeLine{00393 \textcolor{preprocessor}{\#  undef ENTRY}}
\DoxyCodeLine{00394 \textcolor{preprocessor}{\#  undef KEY}}
\DoxyCodeLine{00395 \textcolor{preprocessor}{\#  undef MATCH}}
\DoxyCodeLine{00396 \textcolor{preprocessor}{\#  undef NAME}}
\DoxyCodeLine{00397 \textcolor{preprocessor}{\#  undef ENTRY\_t}}
\DoxyCodeLine{00398 \textcolor{preprocessor}{\#  undef KEY\_t}}
\DoxyCodeLine{00399 \textcolor{preprocessor}{\#  undef MATCH\_t}}
\DoxyCodeLine{00400 \textcolor{preprocessor}{\#  undef KEY\_hash}}
\DoxyCodeLine{00401 \textcolor{preprocessor}{\#  undef MATCH\_cmp}}
\DoxyCodeLine{00402 \textcolor{preprocessor}{\#  undef NAME\_new}}
\DoxyCodeLine{00403 \textcolor{preprocessor}{\#  undef NAME\_free}}
\DoxyCodeLine{00404 \textcolor{preprocessor}{\#  undef NAME\_stats\_init}}
\DoxyCodeLine{00405 \textcolor{preprocessor}{\#  undef NAME\_add}}
\DoxyCodeLine{00406 \textcolor{preprocessor}{\#  undef NAME\_find}}
\DoxyCodeLine{00407 \textcolor{preprocessor}{\#  undef NAME\_iter}}
\DoxyCodeLine{00408 \textcolor{preprocessor}{\#  undef NAME\_next}}
\DoxyCodeLine{00409 \textcolor{preprocessor}{\#  undef \_KEY\_HASH}}
\DoxyCodeLine{00410 \textcolor{preprocessor}{\#endif                          }\textcolor{comment}{/* ENTRY */}\textcolor{preprocessor}{}}

\end{DoxyCode}
