\doxysubsection{hashtable.\+c}
\label{hashtable_8c_source}\index{hashtable.c@{hashtable.c}}

\begin{DoxyCode}{0}
\DoxyCodeLine{00001 \textcolor{comment}{/*= -\/*-\/ c-\/basic-\/offset: 4; indent-\/tabs-\/mode: nil; -\/*-\/}}
\DoxyCodeLine{00002 \textcolor{comment}{ *}}
\DoxyCodeLine{00003 \textcolor{comment}{ * hashtable.c -\/-\/ a generic hashtable implementation.}}
\DoxyCodeLine{00004 \textcolor{comment}{ *}}
\DoxyCodeLine{00005 \textcolor{comment}{ * Copyright (C) 2016 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{preprocessor}{\#include <assert.h>}}
\DoxyCodeLine{00022 \textcolor{preprocessor}{\#include <stdlib.h>}}
\DoxyCodeLine{00023 \textcolor{preprocessor}{\#include "{}hashtable.h"{}}}
\DoxyCodeLine{00024 }
\DoxyCodeLine{00025 \textcolor{comment}{/* Open addressing works best if it can take advantage of memory caches using}}
\DoxyCodeLine{00026 \textcolor{comment}{   locality for probes of adjacent buckets on collisions. So we pack the keys}}
\DoxyCodeLine{00027 \textcolor{comment}{   tightly together in their own key table and avoid referencing the element}}
\DoxyCodeLine{00028 \textcolor{comment}{   table and elements as much as possible. Key value zero is reserved as a}}
\DoxyCodeLine{00029 \textcolor{comment}{   marker for an empty bucket to avoid checking for NULL in the element table.}}
\DoxyCodeLine{00030 \textcolor{comment}{   If we do get a hash value of zero, we -\/1 to wrap it around to 0xffff. */}}
\DoxyCodeLine{00031 }
\DoxyCodeLine{00032 \textcolor{comment}{/* Use max 0.7 load factor to avoid bad open addressing performance. */}}
\DoxyCodeLine{00033 \textcolor{preprocessor}{\#define HASHTABLE\_LOADFACTOR\_NUM 7}}
\DoxyCodeLine{00034 \textcolor{preprocessor}{\#define HASHTABLE\_LOADFACTOR\_DEN 10}}
\DoxyCodeLine{00035 }
\DoxyCodeLine{00036 hashtable\_t *\_hashtable\_new(\textcolor{keywordtype}{int} size)}
\DoxyCodeLine{00037 \{}
\DoxyCodeLine{00038     hashtable\_t *t;}
\DoxyCodeLine{00039     \textcolor{keywordtype}{unsigned} size2, bits2;}
\DoxyCodeLine{00040 }
\DoxyCodeLine{00041     \textcolor{comment}{/* Adjust requested size to account for max load factor. */}}
\DoxyCodeLine{00042     size = 1 + size * HASHTABLE\_LOADFACTOR\_DEN / HASHTABLE\_LOADFACTOR\_NUM;}
\DoxyCodeLine{00043     \textcolor{comment}{/* Use next power of 2 larger than the requested size and get mask bits. */}}
\DoxyCodeLine{00044     \textcolor{keywordflow}{for} (size2 = 2, bits2 = 1; (int)size2 < size; size2 <<= 1, bits2++) ;}
\DoxyCodeLine{00045     \textcolor{keywordflow}{if} (!(t = calloc(1, \textcolor{keyword}{sizeof}(hashtable\_t)+ size2 * \textcolor{keyword}{sizeof}(\textcolor{keywordtype}{unsigned}))))}
\DoxyCodeLine{00046         \textcolor{keywordflow}{return} NULL;}
\DoxyCodeLine{00047     \textcolor{keywordflow}{if} (!(t-\/>etable = calloc(size2, \textcolor{keyword}{sizeof}(\textcolor{keywordtype}{void} *)))) \{}
\DoxyCodeLine{00048         \_hashtable\_free(t);}
\DoxyCodeLine{00049         \textcolor{keywordflow}{return} NULL;}
\DoxyCodeLine{00050     \}}
\DoxyCodeLine{00051     t-\/>size = (int)size2;}
\DoxyCodeLine{00052     t-\/>count = 0;}
\DoxyCodeLine{00053     t-\/>tmask = size2 -\/ 1;}
\DoxyCodeLine{00054 \textcolor{preprocessor}{\#ifndef HASHTABLE\_NBLOOM}}
\DoxyCodeLine{00055     \textcolor{keywordflow}{if} (!(t-\/>kbloom = calloc((size2 + 7) / 8, \textcolor{keyword}{sizeof}(\textcolor{keywordtype}{unsigned} \textcolor{keywordtype}{char})))) \{}
\DoxyCodeLine{00056         \_hashtable\_free(t);}
\DoxyCodeLine{00057         \textcolor{keywordflow}{return} NULL;}
\DoxyCodeLine{00058     \}}
\DoxyCodeLine{00059     t-\/>bshift = (unsigned)\textcolor{keyword}{sizeof}(\textcolor{keywordtype}{unsigned}) * 8 -\/ bits2;}
\DoxyCodeLine{00060     assert(t-\/>tmask == (\textcolor{keywordtype}{unsigned})-\/1 >> t-\/>bshift);}
\DoxyCodeLine{00061 \textcolor{preprocessor}{\#endif}}
\DoxyCodeLine{00062 \textcolor{preprocessor}{\#ifndef HASHTABLE\_NSTATS}}
\DoxyCodeLine{00063     t-\/>find\_count = t-\/>match\_count = t-\/>hashcmp\_count = t-\/>entrycmp\_count = 0;}
\DoxyCodeLine{00064 \textcolor{preprocessor}{\#endif}}
\DoxyCodeLine{00065     \textcolor{keywordflow}{return} t;}
\DoxyCodeLine{00066 \}}
\DoxyCodeLine{00067 }
\DoxyCodeLine{00068 \textcolor{keywordtype}{void} \_hashtable\_free(hashtable\_t *t)}
\DoxyCodeLine{00069 \{}
\DoxyCodeLine{00070     \textcolor{keywordflow}{if} (t) \{}
\DoxyCodeLine{00071         free(t-\/>etable);}
\DoxyCodeLine{00072 \textcolor{preprocessor}{\#ifndef HASHTABLE\_NBLOOM}}
\DoxyCodeLine{00073         free(t-\/>kbloom);}
\DoxyCodeLine{00074 \textcolor{preprocessor}{\#endif}}
\DoxyCodeLine{00075         free(t);}
\DoxyCodeLine{00076     \}}
\DoxyCodeLine{00077 \}}

\end{DoxyCode}
