<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>SphinxBase: src/libsphinxbase/util/hash_table.c Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript">
$(document).ready(initResizable);
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<!-- Generated by Doxygen 1.7.3 -->
<div id="top">
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td style="padding-left: 0.5em;">
<div id="projectname">SphinxBase <span id="projectnumber">0.6</span></div>
</td>
</tr>
</tbody>
</table>
</div>
<div id="navrow1" class="tabs">
<ul class="tablist">
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="pages.html"><span>Related Pages</span></a></li>
<li><a href="annotated.html"><span>Data Structures</span></a></li>
<li class="current"><a href="files.html"><span>Files</span></a></li>
</ul>
</div>
<div id="navrow2" class="tabs2">
<ul class="tablist">
<li><a href="files.html"><span>File List</span></a></li>
<li><a href="globals.html"><span>Globals</span></a></li>
</ul>
</div>
</div>
<div id="side-nav" class="ui-resizable side-nav-resizable">
<div id="nav-tree">
<div id="nav-tree-contents">
</div>
</div>
<div id="splitbar" style="-moz-user-select:none;"
class="ui-resizable-handle">
</div>
</div>
<script type="text/javascript">
initNavTree('hash__table_8c.html','');
</script>
<div id="doc-content">
<div class="header">
<div class="headertitle">
<h1>src/libsphinxbase/util/hash_table.c</h1> </div>
</div>
<div class="contents">
<div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */</span>
<a name="l00002"></a>00002 <span class="comment">/* ====================================================================</span>
<a name="l00003"></a>00003 <span class="comment"> * Copyright (c) 1999-2004 Carnegie Mellon University. All rights</span>
<a name="l00004"></a>00004 <span class="comment"> * reserved.</span>
<a name="l00005"></a>00005 <span class="comment"> *</span>
<a name="l00006"></a>00006 <span class="comment"> * Redistribution and use in source and binary forms, with or without</span>
<a name="l00007"></a>00007 <span class="comment"> * modification, are permitted provided that the following conditions</span>
<a name="l00008"></a>00008 <span class="comment"> * are met:</span>
<a name="l00009"></a>00009 <span class="comment"> *</span>
<a name="l00010"></a>00010 <span class="comment"> * 1. Redistributions of source code must retain the above copyright</span>
<a name="l00011"></a>00011 <span class="comment"> * notice, this list of conditions and the following disclaimer. </span>
<a name="l00012"></a>00012 <span class="comment"> *</span>
<a name="l00013"></a>00013 <span class="comment"> * 2. Redistributions in binary form must reproduce the above copyright</span>
<a name="l00014"></a>00014 <span class="comment"> * notice, this list of conditions and the following disclaimer in</span>
<a name="l00015"></a>00015 <span class="comment"> * the documentation and/or other materials provided with the</span>
<a name="l00016"></a>00016 <span class="comment"> * distribution.</span>
<a name="l00017"></a>00017 <span class="comment"> *</span>
<a name="l00018"></a>00018 <span class="comment"> * This work was supported in part by funding from the Defense Advanced </span>
<a name="l00019"></a>00019 <span class="comment"> * Research Projects Agency and the National Science Foundation of the </span>
<a name="l00020"></a>00020 <span class="comment"> * United States of America, and the CMU Sphinx Speech Consortium.</span>
<a name="l00021"></a>00021 <span class="comment"> *</span>
<a name="l00022"></a>00022 <span class="comment"> * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND </span>
<a name="l00023"></a>00023 <span class="comment"> * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, </span>
<a name="l00024"></a>00024 <span class="comment"> * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR</span>
<a name="l00025"></a>00025 <span class="comment"> * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY</span>
<a name="l00026"></a>00026 <span class="comment"> * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,</span>
<a name="l00027"></a>00027 <span class="comment"> * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT </span>
<a name="l00028"></a>00028 <span class="comment"> * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, </span>
<a name="l00029"></a>00029 <span class="comment"> * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY </span>
<a name="l00030"></a>00030 <span class="comment"> * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT </span>
<a name="l00031"></a>00031 <span class="comment"> * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE </span>
<a name="l00032"></a>00032 <span class="comment"> * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.</span>
<a name="l00033"></a>00033 <span class="comment"> *</span>
<a name="l00034"></a>00034 <span class="comment"> * ====================================================================</span>
<a name="l00035"></a>00035 <span class="comment"> *</span>
<a name="l00036"></a>00036 <span class="comment"> */</span>
<a name="l00037"></a>00037 <span class="comment">/*</span>
<a name="l00038"></a>00038 <span class="comment"> * hash.c -- Hash table module.</span>
<a name="l00039"></a>00039 <span class="comment"> *</span>
<a name="l00040"></a>00040 <span class="comment"> * **********************************************</span>
<a name="l00041"></a>00041 <span class="comment"> * CMU ARPA Speech Project</span>
<a name="l00042"></a>00042 <span class="comment"> *</span>
<a name="l00043"></a>00043 <span class="comment"> * Copyright (c) 1999 Carnegie Mellon University.</span>
<a name="l00044"></a>00044 <span class="comment"> * ALL RIGHTS RESERVED.</span>
<a name="l00045"></a>00045 <span class="comment"> * **********************************************</span>
<a name="l00046"></a>00046 <span class="comment"> * </span>
<a name="l00047"></a>00047 <span class="comment"> * HISTORY</span>
<a name="l00048"></a>00048 <span class="comment"> * $Log: hash.c,v $</span>
<a name="l00049"></a>00049 <span class="comment"> * Revision 1.5 2005/06/22 03:04:01 arthchan2003</span>
<a name="l00050"></a>00050 <span class="comment"> * 1, Implemented hash_delete and hash_display, 2, Fixed doxygen documentation, 3, Added keyword.</span>
<a name="l00051"></a>00051 <span class="comment"> *</span>
<a name="l00052"></a>00052 <span class="comment"> * Revision 1.9 2005/05/25 06:17:53 archan</span>
<a name="l00053"></a>00053 <span class="comment"> * Delete the test code in cmd_ln.c and fixed platform specific code of hash.c</span>
<a name="l00054"></a>00054 <span class="comment"> *</span>
<a name="l00055"></a>00055 <span class="comment"> * Revision 1.8 2005/05/24 01:10:54 archan</span>
<a name="l00056"></a>00056 <span class="comment"> * Fix a bug when the value only appear in the hash but there is no chain. Also make sure that prev was initialized to NULL. All success cases were tested, but not tested with the deletion is tested.</span>
<a name="l00057"></a>00057 <span class="comment"> *</span>
<a name="l00058"></a>00058 <span class="comment"> * Revision 1.6 2005/05/24 00:00:45 archan</span>
<a name="l00059"></a>00059 <span class="comment"> * Added basic functionalities to hash_t: 1, display and 2, delete a key from a hash. \n</span>
<a name="l00060"></a>00060 <span class="comment"> *</span>
<a name="l00061"></a>00061 <span class="comment"> * Revision 1.5 2005/05/11 07:01:38 archan</span>
<a name="l00062"></a>00062 <span class="comment"> * Added comments on the usage of the current implementation of hash tables.</span>
<a name="l00063"></a>00063 <span class="comment"> *</span>
<a name="l00064"></a>00064 <span class="comment"> * Revision 1.4 2005/05/03 04:09:11 archan</span>
<a name="l00065"></a>00065 <span class="comment"> * Implemented the heart of word copy search. For every ci-phone, every word end, a tree will be allocated to preserve its pathscore. This is different from 3.5 or below, only the best score for a particular ci-phone, regardless of the word-ends will be preserved at every frame. The graph propagation will not collect unused word tree at this point. srch_WST_propagate_wd_lv2 is also as the most stupid in the century. But well, after all, everything needs a start. I will then really get the results from the search and see how it looks.</span>
<a name="l00066"></a>00066 <span class="comment"> *</span>
<a name="l00067"></a>00067 <span class="comment"> * Revision 1.3 2005/03/30 01:22:48 archan</span>
<a name="l00068"></a>00068 <span class="comment"> * Fixed mistakes in last updates. Add</span>
<a name="l00069"></a>00069 <span class="comment"> *</span>
<a name="l00070"></a>00070 <span class="comment"> * </span>
<a name="l00071"></a>00071 <span class="comment"> * 05-May-1999 M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon</span>
<a name="l00072"></a>00072 <span class="comment"> * Removed hash_key2hash(). Added hash_enter_bkey() and hash_lookup_bkey(),</span>
<a name="l00073"></a>00073 <span class="comment"> * and len attribute to hash_entry_t.</span>
<a name="l00074"></a>00074 <span class="comment"> * </span>
<a name="l00075"></a>00075 <span class="comment"> * 30-Apr-1999 M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon</span>
<a name="l00076"></a>00076 <span class="comment"> * Added hash_key2hash().</span>
<a name="l00077"></a>00077 <span class="comment"> * </span>
<a name="l00078"></a>00078 <span class="comment"> * 18-Jun-97 M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon</span>
<a name="l00079"></a>00079 <span class="comment"> * Included case sensitive/insensitive option. Removed local, static</span>
<a name="l00080"></a>00080 <span class="comment"> * maintenance of all hash tables.</span>
<a name="l00081"></a>00081 <span class="comment"> * </span>
<a name="l00082"></a>00082 <span class="comment"> * 31-Jul-95 M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon</span>
<a name="l00083"></a>00083 <span class="comment"> * Created.</span>
<a name="l00084"></a>00084 <span class="comment"> */</span>
<a name="l00085"></a>00085
<a name="l00086"></a>00086
<a name="l00087"></a>00087 <span class="preprocessor">#include <stdio.h></span>
<a name="l00088"></a>00088 <span class="preprocessor">#include <stdlib.h></span>
<a name="l00089"></a>00089 <span class="preprocessor">#include <string.h></span>
<a name="l00090"></a>00090 <span class="preprocessor">#include <assert.h></span>
<a name="l00091"></a>00091
<a name="l00092"></a>00092 <span class="preprocessor">#ifdef _MSC_VER</span>
<a name="l00093"></a>00093 <span class="preprocessor"></span><span class="preprocessor">#pragma warning (disable: 4018)</span>
<a name="l00094"></a>00094 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
<a name="l00095"></a>00095 <span class="preprocessor"></span>
<a name="l00096"></a>00096 <span class="preprocessor">#include "sphinxbase/hash_table.h"</span>
<a name="l00097"></a>00097 <span class="preprocessor">#include "sphinxbase/err.h"</span>
<a name="l00098"></a>00098 <span class="preprocessor">#include "sphinxbase/ckd_alloc.h"</span>
<a name="l00099"></a>00099 <span class="preprocessor">#include "sphinxbase/case.h"</span>
<a name="l00100"></a>00100
<a name="l00101"></a>00101
<a name="l00102"></a>00102 <span class="preprocessor">#if 0</span>
<a name="l00103"></a>00103 <span class="preprocessor"></span><span class="keyword">static</span> <span class="keywordtype">void</span>
<a name="l00104"></a>00104 prime_sieve(int32 max)
<a name="l00105"></a>00105 {
<a name="l00106"></a>00106 <span class="keywordtype">char</span> *notprime;
<a name="l00107"></a>00107 int32 p, pp;
<a name="l00108"></a>00108
<a name="l00109"></a>00109 notprime = (<span class="keywordtype">char</span> *) <a class="code" href="ckd__alloc_8h.html#aa00ef21903bc4f8a972488417adc8d2e" title="Macros to simplify the use of above functions.">ckd_calloc</a>(max + 1, 1);
<a name="l00110"></a>00110 p = 2;
<a name="l00111"></a>00111 <span class="keywordflow">for</span> (;;) {
<a name="l00112"></a>00112 printf(<span class="stringliteral">"%d\n"</span>, p);
<a name="l00113"></a>00113 <span class="keywordflow">for</span> (pp = p + p; pp <= max; pp += p)
<a name="l00114"></a>00114 notprime[pp] = 1;
<a name="l00115"></a>00115 <span class="keywordflow">for</span> (++p; (p <= max) && notprime[p]; p++);
<a name="l00116"></a>00116 <span class="keywordflow">if</span> (p > max)
<a name="l00117"></a>00117 <span class="keywordflow">break</span>;
<a name="l00118"></a>00118 }
<a name="l00119"></a>00119 }
<a name="l00120"></a>00120 <span class="preprocessor">#endif</span>
<a name="l00121"></a>00121 <span class="preprocessor"></span>
<a name="l00122"></a>00122
<a name="l00123"></a>00123 <span class="comment">/*</span>
<a name="l00124"></a>00124 <span class="comment"> * HACK!! Initial hash table size is restricted by this set of primes. (Of course,</span>
<a name="l00125"></a>00125 <span class="comment"> * collision resolution by chaining will accommodate more entries indefinitely, but</span>
<a name="l00126"></a>00126 <span class="comment"> * efficiency will drop.)</span>
<a name="l00127"></a>00127 <span class="comment"> */</span>
<a name="l00128"></a>00128 <span class="keyword">const</span> int32 prime[] = {
<a name="l00129"></a>00129 101, 211, 307, 401, 503, 601, 701, 809, 907,
<a name="l00130"></a>00130 1009, 1201, 1601, 2003, 2411, 3001, 4001, 5003, 6007, 7001, 8009,
<a name="l00131"></a>00131 9001,
<a name="l00132"></a>00132 10007, 12007, 16001, 20011, 24001, 30011, 40009, 50021, 60013,
<a name="l00133"></a>00133 70001, 80021, 90001,
<a name="l00134"></a>00134 100003, 120011, 160001, 200003, 240007, 300007, 400009, 500009,
<a name="l00135"></a>00135 600011, 700001, 800011, 900001,
<a name="l00136"></a>00136 -1
<a name="l00137"></a>00137 };
<a name="l00138"></a>00138
<a name="l00139"></a>00139
<a name="l00143"></a>00143 <span class="keyword">static</span> int32
<a name="l00144"></a>00144 prime_size(int32 size)
<a name="l00145"></a>00145 {
<a name="l00146"></a>00146 int32 i;
<a name="l00147"></a>00147
<a name="l00148"></a>00148 <span class="keywordflow">for</span> (i = 0; (prime[i] > 0) && (prime[i] < size); i++);
<a name="l00149"></a>00149 <span class="keywordflow">if</span> (prime[i] <= 0) {
<a name="l00150"></a>00150 <a class="code" href="err_8h.html#a6a794bec721b555ac1f2167f9e12f662" title="Print warning information to standard error stream.">E_WARN</a>(<span class="stringliteral">"Very large hash table requested (%d entries)\n"</span>, size);
<a name="l00151"></a>00151 --i;
<a name="l00152"></a>00152 }
<a name="l00153"></a>00153 <span class="keywordflow">return</span> (prime[i]);
<a name="l00154"></a>00154 }
<a name="l00155"></a>00155
<a name="l00156"></a>00156
<a name="l00157"></a>00157 <a class="code" href="structhash__table__t.html">hash_table_t</a> *
<a name="l00158"></a><a class="code" href="hash__table_8h.html#a56d93e8c03e066b77377ac6eab50cfae">00158</a> <a class="code" href="hash__table_8h.html#a56d93e8c03e066b77377ac6eab50cfae" title="Allocate a new hash table for a given expected size.">hash_table_new</a>(int32 size, int32 casearg)
<a name="l00159"></a>00159 {
<a name="l00160"></a>00160 <a class="code" href="structhash__table__t.html">hash_table_t</a> *h;
<a name="l00161"></a>00161
<a name="l00162"></a>00162 h = (<a class="code" href="structhash__table__t.html">hash_table_t</a> *) <a class="code" href="ckd__alloc_8h.html#aa00ef21903bc4f8a972488417adc8d2e" title="Macros to simplify the use of above functions.">ckd_calloc</a>(1, <span class="keyword">sizeof</span>(<a class="code" href="structhash__table__t.html">hash_table_t</a>));
<a name="l00163"></a>00163 h-><a class="code" href="structhash__table__t.html#a34cc067a2c4f517ce8b8921965d0f8dd" title="Primary hash table, excluding entries that collide.">size</a> = prime_size(size + (size >> 1));
<a name="l00164"></a>00164 h-><a class="code" href="structhash__table__t.html#a09ea72a33026b9a77f76811062a4d692" title="Number of valid entries in the table.">nocase</a> = (casearg == HASH_CASE_NO);
<a name="l00165"></a>00165 h->table = (<a class="code" href="structhash__entry__s.html" title="A note by ARCHAN at 20050510: Technically what we use is so-called &quot;hash table with buckets&quot...">hash_entry_t</a> *) <a class="code" href="ckd__alloc_8h.html#aa00ef21903bc4f8a972488417adc8d2e" title="Macros to simplify the use of above functions.">ckd_calloc</a>(h-><a class="code" href="structhash__table__t.html#a34cc067a2c4f517ce8b8921965d0f8dd" title="Primary hash table, excluding entries that collide.">size</a>, <span class="keyword">sizeof</span>(<a class="code" href="structhash__entry__s.html" title="A note by ARCHAN at 20050510: Technically what we use is so-called &quot;hash table with buckets&quot...">hash_entry_t</a>));
<a name="l00166"></a>00166 <span class="comment">/* The above calloc clears h->table[*].key and .next to NULL, i.e. an empty table */</span>
<a name="l00167"></a>00167
<a name="l00168"></a>00168 <span class="keywordflow">return</span> h;
<a name="l00169"></a>00169 }
<a name="l00170"></a>00170
<a name="l00171"></a>00171
<a name="l00172"></a>00172 <span class="comment">/*</span>
<a name="l00173"></a>00173 <span class="comment"> * Compute hash value for given key string.</span>
<a name="l00174"></a>00174 <span class="comment"> * Somewhat tuned for English text word strings.</span>
<a name="l00175"></a>00175 <span class="comment"> */</span>
<a name="l00176"></a>00176 <span class="keyword">static</span> uint32
<a name="l00177"></a>00177 key2hash(<a class="code" href="structhash__table__t.html">hash_table_t</a> * h, <span class="keyword">const</span> <span class="keywordtype">char</span> *key)
<a name="l00178"></a>00178 {
<a name="l00179"></a>00179
<a name="l00180"></a>00180 <span class="keyword">register</span> <span class="keyword">const</span> <span class="keywordtype">char</span> *cp;
<a name="l00181"></a>00181
<a name="l00191"></a>00191 <span class="comment">/*register char c; */</span>
<a name="l00192"></a>00192 <span class="keyword">register</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span> c;
<a name="l00193"></a>00193 <span class="keyword">register</span> int32 s;
<a name="l00194"></a>00194 <span class="keyword">register</span> uint32 hash;
<a name="l00195"></a>00195
<a name="l00196"></a>00196 hash = 0;
<a name="l00197"></a>00197 s = 0;
<a name="l00198"></a>00198
<a name="l00199"></a>00199 <span class="keywordflow">if</span> (h-><a class="code" href="structhash__table__t.html#a09ea72a33026b9a77f76811062a4d692" title="Number of valid entries in the table.">nocase</a>) {
<a name="l00200"></a>00200 <span class="keywordflow">for</span> (cp = key; *cp; cp++) {
<a name="l00201"></a>00201 c = *cp;
<a name="l00202"></a>00202 c = <a class="code" href="case_8h.html#a3299c549655d5af1fcbc384ee7fd68e3" title="Return upper case form for c.">UPPER_CASE</a>(c);
<a name="l00203"></a>00203 hash += c << s;
<a name="l00204"></a>00204 s += 5;
<a name="l00205"></a>00205 <span class="keywordflow">if</span> (s >= 25)
<a name="l00206"></a>00206 s -= 24;
<a name="l00207"></a>00207 }
<a name="l00208"></a>00208 }
<a name="l00209"></a>00209 <span class="keywordflow">else</span> {
<a name="l00210"></a>00210 <span class="keywordflow">for</span> (cp = key; *cp; cp++) {
<a name="l00211"></a>00211 hash += (*cp) << s;
<a name="l00212"></a>00212 s += 5;
<a name="l00213"></a>00213 <span class="keywordflow">if</span> (s >= 25)
<a name="l00214"></a>00214 s -= 24;
<a name="l00215"></a>00215 }
<a name="l00216"></a>00216 }
<a name="l00217"></a>00217
<a name="l00218"></a>00218 <span class="keywordflow">return</span> (hash % h-><a class="code" href="structhash__table__t.html#a34cc067a2c4f517ce8b8921965d0f8dd" title="Primary hash table, excluding entries that collide.">size</a>);
<a name="l00219"></a>00219 }
<a name="l00220"></a>00220
<a name="l00221"></a>00221
<a name="l00222"></a>00222 <span class="keyword">static</span> <span class="keywordtype">char</span> *
<a name="l00223"></a>00223 makekey(uint8 * data, int32 len, <span class="keywordtype">char</span> *key)
<a name="l00224"></a>00224 {
<a name="l00225"></a>00225 int32 i, j;
<a name="l00226"></a>00226
<a name="l00227"></a>00227 <span class="keywordflow">if</span> (!key)
<a name="l00228"></a>00228 key = (<span class="keywordtype">char</span> *) <a class="code" href="ckd__alloc_8h.html#aa00ef21903bc4f8a972488417adc8d2e" title="Macros to simplify the use of above functions.">ckd_calloc</a>(len * 2 + 1, <span class="keyword">sizeof</span>(<span class="keywordtype">char</span>));
<a name="l00229"></a>00229
<a name="l00230"></a>00230 <span class="keywordflow">for</span> (i = 0, j = 0; i < len; i++, j += 2) {
<a name="l00231"></a>00231 key[j] = <span class="charliteral">'A'</span> + (data[i] & 0x000f);
<a name="l00232"></a>00232 key[j + 1] = <span class="charliteral">'J'</span> + ((data[i] >> 4) & 0x000f);
<a name="l00233"></a>00233 }
<a name="l00234"></a>00234 key[j] = <span class="charliteral">'\0'</span>;
<a name="l00235"></a>00235
<a name="l00236"></a>00236 <span class="keywordflow">return</span> key;
<a name="l00237"></a>00237 }
<a name="l00238"></a>00238
<a name="l00239"></a>00239
<a name="l00240"></a>00240 <span class="keyword">static</span> int32
<a name="l00241"></a>00241 keycmp_nocase(<a class="code" href="structhash__entry__s.html" title="A note by ARCHAN at 20050510: Technically what we use is so-called &quot;hash table with buckets&quot...">hash_entry_t</a> * entry, <span class="keyword">const</span> <span class="keywordtype">char</span> *key)
<a name="l00242"></a>00242 {
<a name="l00243"></a>00243 <span class="keywordtype">char</span> c1, c2;
<a name="l00244"></a>00244 int32 i;
<a name="l00245"></a>00245 <span class="keyword">const</span> <span class="keywordtype">char</span> *str;
<a name="l00246"></a>00246
<a name="l00247"></a>00247 str = entry->key;
<a name="l00248"></a>00248 <span class="keywordflow">for</span> (i = 0; i < entry-><a class="code" href="structhash__entry__s.html#af1ec5f16059ced6d9a8ae4d36ca7e2b3" title="Key string, NULL if this is an empty slot.">len</a>; i++) {
<a name="l00249"></a>00249 c1 = *(str++);
<a name="l00250"></a>00250 c1 = <a class="code" href="case_8h.html#a3299c549655d5af1fcbc384ee7fd68e3" title="Return upper case form for c.">UPPER_CASE</a>(c1);
<a name="l00251"></a>00251 c2 = *(key++);
<a name="l00252"></a>00252 c2 = <a class="code" href="case_8h.html#a3299c549655d5af1fcbc384ee7fd68e3" title="Return upper case form for c.">UPPER_CASE</a>(c2);
<a name="l00253"></a>00253 <span class="keywordflow">if</span> (c1 != c2)
<a name="l00254"></a>00254 <span class="keywordflow">return</span> (c1 - c2);
<a name="l00255"></a>00255 }
<a name="l00256"></a>00256
<a name="l00257"></a>00257 <span class="keywordflow">return</span> 0;
<a name="l00258"></a>00258 }
<a name="l00259"></a>00259
<a name="l00260"></a>00260
<a name="l00261"></a>00261 <span class="keyword">static</span> int32
<a name="l00262"></a>00262 keycmp_case(<a class="code" href="structhash__entry__s.html" title="A note by ARCHAN at 20050510: Technically what we use is so-called &quot;hash table with buckets&quot...">hash_entry_t</a> * entry, <span class="keyword">const</span> <span class="keywordtype">char</span> *key)
<a name="l00263"></a>00263 {
<a name="l00264"></a>00264 <span class="keywordtype">char</span> c1, c2;
<a name="l00265"></a>00265 int32 i;
<a name="l00266"></a>00266 <span class="keyword">const</span> <span class="keywordtype">char</span> *str;
<a name="l00267"></a>00267
<a name="l00268"></a>00268 str = entry->key;
<a name="l00269"></a>00269 <span class="keywordflow">for</span> (i = 0; i < entry-><a class="code" href="structhash__entry__s.html#af1ec5f16059ced6d9a8ae4d36ca7e2b3" title="Key string, NULL if this is an empty slot.">len</a>; i++) {
<a name="l00270"></a>00270 c1 = *(str++);
<a name="l00271"></a>00271 c2 = *(key++);
<a name="l00272"></a>00272 <span class="keywordflow">if</span> (c1 != c2)
<a name="l00273"></a>00273 <span class="keywordflow">return</span> (c1 - c2);
<a name="l00274"></a>00274 }
<a name="l00275"></a>00275
<a name="l00276"></a>00276 <span class="keywordflow">return</span> 0;
<a name="l00277"></a>00277 }
<a name="l00278"></a>00278
<a name="l00279"></a>00279
<a name="l00280"></a>00280 <span class="comment">/*</span>
<a name="l00281"></a>00281 <span class="comment"> * Lookup entry with hash-value hash in table h for given key</span>
<a name="l00282"></a>00282 <span class="comment"> * Return value: hash_entry_t for key</span>
<a name="l00283"></a>00283 <span class="comment"> */</span>
<a name="l00284"></a>00284 <span class="keyword">static</span> <a class="code" href="structhash__entry__s.html" title="A note by ARCHAN at 20050510: Technically what we use is so-called &quot;hash table with buckets&quot...">hash_entry_t</a> *
<a name="l00285"></a>00285 lookup(<a class="code" href="structhash__table__t.html">hash_table_t</a> * h, uint32 hash, <span class="keyword">const</span> <span class="keywordtype">char</span> *key, <span class="keywordtype">size_t</span> len)
<a name="l00286"></a>00286 {
<a name="l00287"></a>00287 <a class="code" href="structhash__entry__s.html" title="A note by ARCHAN at 20050510: Technically what we use is so-called &quot;hash table with buckets&quot...">hash_entry_t</a> *entry;
<a name="l00288"></a>00288
<a name="l00289"></a>00289 entry = &(h->table[hash]);
<a name="l00290"></a>00290 <span class="keywordflow">if</span> (entry->key == NULL)
<a name="l00291"></a>00291 <span class="keywordflow">return</span> NULL;
<a name="l00292"></a>00292
<a name="l00293"></a>00293 <span class="keywordflow">if</span> (h-><a class="code" href="structhash__table__t.html#a09ea72a33026b9a77f76811062a4d692" title="Number of valid entries in the table.">nocase</a>) {
<a name="l00294"></a>00294 <span class="keywordflow">while</span> (entry && ((entry-><a class="code" href="structhash__entry__s.html#af1ec5f16059ced6d9a8ae4d36ca7e2b3" title="Key string, NULL if this is an empty slot.">len</a> != len)
<a name="l00295"></a>00295 || (keycmp_nocase(entry, key) != 0)))
<a name="l00296"></a>00296 entry = entry-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a>;
<a name="l00297"></a>00297 }
<a name="l00298"></a>00298 <span class="keywordflow">else</span> {
<a name="l00299"></a>00299 <span class="keywordflow">while</span> (entry && ((entry-><a class="code" href="structhash__entry__s.html#af1ec5f16059ced6d9a8ae4d36ca7e2b3" title="Key string, NULL if this is an empty slot.">len</a> != len)
<a name="l00300"></a>00300 || (keycmp_case(entry, key) != 0)))
<a name="l00301"></a>00301 entry = entry-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a>;
<a name="l00302"></a>00302 }
<a name="l00303"></a>00303
<a name="l00304"></a>00304 <span class="keywordflow">return</span> entry;
<a name="l00305"></a>00305 }
<a name="l00306"></a>00306
<a name="l00307"></a>00307
<a name="l00308"></a>00308 int32
<a name="l00309"></a><a class="code" href="hash__table_8h.html#a9a1e5ed410eb96f514b00fdce770fbd7">00309</a> <a class="code" href="hash__table_8h.html#a9a1e5ed410eb96f514b00fdce770fbd7" title="Look up a key in a hash table and optionally return the associated value.">hash_table_lookup</a>(<a class="code" href="structhash__table__t.html">hash_table_t</a> * h, <span class="keyword">const</span> <span class="keywordtype">char</span> *key, <span class="keywordtype">void</span> ** val)
<a name="l00310"></a>00310 {
<a name="l00311"></a>00311 <a class="code" href="structhash__entry__s.html" title="A note by ARCHAN at 20050510: Technically what we use is so-called &quot;hash table with buckets&quot...">hash_entry_t</a> *entry;
<a name="l00312"></a>00312 uint32 hash;
<a name="l00313"></a>00313 int32 len;
<a name="l00314"></a>00314
<a name="l00315"></a>00315 hash = key2hash(h, key);
<a name="l00316"></a>00316 len = strlen(key);
<a name="l00317"></a>00317
<a name="l00318"></a>00318 entry = lookup(h, hash, key, len);
<a name="l00319"></a>00319 <span class="keywordflow">if</span> (entry) {
<a name="l00320"></a>00320 <span class="keywordflow">if</span> (val)
<a name="l00321"></a>00321 *val = entry-><a class="code" href="structhash__entry__s.html#a0d57012963084fed93886681108aa636" title="Key-length; the key string does not have to be a C-style NULL terminated string; it can have arbitrar...">val</a>;
<a name="l00322"></a>00322 <span class="keywordflow">return</span> 0;
<a name="l00323"></a>00323 }
<a name="l00324"></a>00324 <span class="keywordflow">else</span>
<a name="l00325"></a>00325 <span class="keywordflow">return</span> -1;
<a name="l00326"></a>00326 }
<a name="l00327"></a>00327
<a name="l00328"></a>00328 int32
<a name="l00329"></a><a class="code" href="hash__table_8h.html#acaf27e8e7e336faf6653649937c42ed8">00329</a> <a class="code" href="hash__table_8h.html#acaf27e8e7e336faf6653649937c42ed8" title="Look up a 32-bit integer value in a hash table.">hash_table_lookup_int32</a>(<a class="code" href="structhash__table__t.html">hash_table_t</a> * h, <span class="keyword">const</span> <span class="keywordtype">char</span> *key, int32 *val)
<a name="l00330"></a>00330 {
<a name="l00331"></a>00331 <span class="keywordtype">void</span> *vval;
<a name="l00332"></a>00332 int32 rv;
<a name="l00333"></a>00333
<a name="l00334"></a>00334 rv = <a class="code" href="hash__table_8h.html#a9a1e5ed410eb96f514b00fdce770fbd7" title="Look up a key in a hash table and optionally return the associated value.">hash_table_lookup</a>(h, key, &vval);
<a name="l00335"></a>00335 <span class="keywordflow">if</span> (rv != 0)
<a name="l00336"></a>00336 <span class="keywordflow">return</span> rv;
<a name="l00337"></a>00337 <span class="keywordflow">if</span> (val)
<a name="l00338"></a>00338 *val = (int32)(<span class="keywordtype">long</span>)vval;
<a name="l00339"></a>00339 <span class="keywordflow">return</span> 0;
<a name="l00340"></a>00340 }
<a name="l00341"></a>00341
<a name="l00342"></a>00342
<a name="l00343"></a>00343 int32
<a name="l00344"></a><a class="code" href="hash__table_8h.html#a91f5b3924c0e3a50f94c86bb5fd078e8">00344</a> <a class="code" href="hash__table_8h.html#a91f5b3924c0e3a50f94c86bb5fd078e8" title="Like hash_lookup, but with an explicitly specified key length, instead of a NULL-terminated, C-style key string.">hash_table_lookup_bkey</a>(<a class="code" href="structhash__table__t.html">hash_table_t</a> * h, <span class="keyword">const</span> <span class="keywordtype">char</span> *key, <span class="keywordtype">size_t</span> len, <span class="keywordtype">void</span> ** val)
<a name="l00345"></a>00345 {
<a name="l00346"></a>00346 <a class="code" href="structhash__entry__s.html" title="A note by ARCHAN at 20050510: Technically what we use is so-called &quot;hash table with buckets&quot...">hash_entry_t</a> *entry;
<a name="l00347"></a>00347 uint32 hash;
<a name="l00348"></a>00348 <span class="keywordtype">char</span> *str;
<a name="l00349"></a>00349
<a name="l00350"></a>00350 str = makekey((uint8 *) key, len, NULL);
<a name="l00351"></a>00351 hash = key2hash(h, str);
<a name="l00352"></a>00352 <a class="code" href="ckd__alloc_8h.html#a31c6b405558620ac37599737b5722fbf" title="Test and free a 1-D array.">ckd_free</a>(str);
<a name="l00353"></a>00353
<a name="l00354"></a>00354 entry = lookup(h, hash, key, len);
<a name="l00355"></a>00355 <span class="keywordflow">if</span> (entry) {
<a name="l00356"></a>00356 <span class="keywordflow">if</span> (val)
<a name="l00357"></a>00357 *val = entry-><a class="code" href="structhash__entry__s.html#a0d57012963084fed93886681108aa636" title="Key-length; the key string does not have to be a C-style NULL terminated string; it can have arbitrar...">val</a>;
<a name="l00358"></a>00358 <span class="keywordflow">return</span> 0;
<a name="l00359"></a>00359 }
<a name="l00360"></a>00360 <span class="keywordflow">else</span>
<a name="l00361"></a>00361 <span class="keywordflow">return</span> -1;
<a name="l00362"></a>00362 }
<a name="l00363"></a>00363
<a name="l00364"></a>00364 int32
<a name="l00365"></a><a class="code" href="hash__table_8h.html#acc530eda0b105745cf3a47cc3c1148e4">00365</a> <a class="code" href="hash__table_8h.html#acc530eda0b105745cf3a47cc3c1148e4" title="Look up a 32-bit integer value in a hash table.">hash_table_lookup_bkey_int32</a>(<a class="code" href="structhash__table__t.html">hash_table_t</a> * h, <span class="keyword">const</span> <span class="keywordtype">char</span> *key, <span class="keywordtype">size_t</span> len, int32 *val)
<a name="l00366"></a>00366 {
<a name="l00367"></a>00367 <span class="keywordtype">void</span> *vval;
<a name="l00368"></a>00368 int32 rv;
<a name="l00369"></a>00369
<a name="l00370"></a>00370 rv = <a class="code" href="hash__table_8h.html#a91f5b3924c0e3a50f94c86bb5fd078e8" title="Like hash_lookup, but with an explicitly specified key length, instead of a NULL-terminated, C-style key string.">hash_table_lookup_bkey</a>(h, key, len, &vval);
<a name="l00371"></a>00371 <span class="keywordflow">if</span> (rv != 0)
<a name="l00372"></a>00372 <span class="keywordflow">return</span> rv;
<a name="l00373"></a>00373 <span class="keywordflow">if</span> (val)
<a name="l00374"></a>00374 *val = (int32)(<span class="keywordtype">long</span>)vval;
<a name="l00375"></a>00375 <span class="keywordflow">return</span> 0;
<a name="l00376"></a>00376 }
<a name="l00377"></a>00377
<a name="l00378"></a>00378
<a name="l00379"></a>00379 <span class="keyword">static</span> <span class="keywordtype">void</span> *
<a name="l00380"></a>00380 enter(<a class="code" href="structhash__table__t.html">hash_table_t</a> * h, uint32 hash, <span class="keyword">const</span> <span class="keywordtype">char</span> *key, <span class="keywordtype">size_t</span> len, <span class="keywordtype">void</span> *val, int32 replace)
<a name="l00381"></a>00381 {
<a name="l00382"></a>00382 <a class="code" href="structhash__entry__s.html" title="A note by ARCHAN at 20050510: Technically what we use is so-called &quot;hash table with buckets&quot...">hash_entry_t</a> *cur, *<span class="keyword">new</span>;
<a name="l00383"></a>00383
<a name="l00384"></a>00384 <span class="keywordflow">if</span> ((cur = lookup(h, hash, key, len)) != NULL) {
<a name="l00385"></a>00385 <span class="keywordtype">void</span> *oldval;
<a name="l00386"></a>00386 <span class="comment">/* Key already exists. */</span>
<a name="l00387"></a>00387 oldval = cur-><a class="code" href="structhash__entry__s.html#a0d57012963084fed93886681108aa636" title="Key-length; the key string does not have to be a C-style NULL terminated string; it can have arbitrar...">val</a>;
<a name="l00388"></a>00388 <span class="keywordflow">if</span> (replace) {
<a name="l00389"></a>00389 <span class="comment">/* Replace the pointer if replacement is requested,</span>
<a name="l00390"></a>00390 <span class="comment"> * because this might be a different instance of the same</span>
<a name="l00391"></a>00391 <span class="comment"> * string (this verges on magic, sorry) */</span>
<a name="l00392"></a>00392 cur->key = key;
<a name="l00393"></a>00393 cur-><a class="code" href="structhash__entry__s.html#a0d57012963084fed93886681108aa636" title="Key-length; the key string does not have to be a C-style NULL terminated string; it can have arbitrar...">val</a> = val;
<a name="l00394"></a>00394 }
<a name="l00395"></a>00395 <span class="keywordflow">return</span> oldval;
<a name="l00396"></a>00396 }
<a name="l00397"></a>00397
<a name="l00398"></a>00398 cur = &(h->table[hash]);
<a name="l00399"></a>00399 <span class="keywordflow">if</span> (cur->key == NULL) {
<a name="l00400"></a>00400 <span class="comment">/* Empty slot at hashed location; add this entry */</span>
<a name="l00401"></a>00401 cur->key = key;
<a name="l00402"></a>00402 cur-><a class="code" href="structhash__entry__s.html#af1ec5f16059ced6d9a8ae4d36ca7e2b3" title="Key string, NULL if this is an empty slot.">len</a> = len;
<a name="l00403"></a>00403 cur-><a class="code" href="structhash__entry__s.html#a0d57012963084fed93886681108aa636" title="Key-length; the key string does not have to be a C-style NULL terminated string; it can have arbitrar...">val</a> = val;
<a name="l00404"></a>00404
<a name="l00405"></a>00405 <span class="comment">/* Added by ARCHAN at 20050515. This allows deletion could work. */</span>
<a name="l00406"></a>00406 cur-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a> = NULL;
<a name="l00407"></a>00407
<a name="l00408"></a>00408 }
<a name="l00409"></a>00409 <span class="keywordflow">else</span> {
<a name="l00410"></a>00410 <span class="comment">/* Key collision; create new entry and link to hashed location */</span>
<a name="l00411"></a>00411 <span class="keyword">new</span> = (<a class="code" href="structhash__entry__s.html" title="A note by ARCHAN at 20050510: Technically what we use is so-called &quot;hash table with buckets&quot...">hash_entry_t</a> *) <a class="code" href="ckd__alloc_8h.html#aa00ef21903bc4f8a972488417adc8d2e" title="Macros to simplify the use of above functions.">ckd_calloc</a>(1, <span class="keyword">sizeof</span>(<a class="code" href="structhash__entry__s.html" title="A note by ARCHAN at 20050510: Technically what we use is so-called &quot;hash table with buckets&quot...">hash_entry_t</a>));
<a name="l00412"></a>00412 <span class="keyword">new</span>->key = key;
<a name="l00413"></a>00413 <span class="keyword">new</span>->len = len;
<a name="l00414"></a>00414 <span class="keyword">new</span>->val = val;
<a name="l00415"></a>00415 <span class="keyword">new</span>->next = cur-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a>;
<a name="l00416"></a>00416 cur-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a> = <span class="keyword">new</span>;
<a name="l00417"></a>00417 }
<a name="l00418"></a>00418 ++h-><a class="code" href="structhash__table__t.html#a8c691525a04e01751972d608948c8ac0" title="Primary hash table size, (is a prime#); NOTE: This is the number of primary entries ALLOCATED...">inuse</a>;
<a name="l00419"></a>00419
<a name="l00420"></a>00420 <span class="keywordflow">return</span> val;
<a name="l00421"></a>00421 }
<a name="l00422"></a>00422
<a name="l00423"></a>00423 <span class="comment">/* 20050523 Added by ARCHAN to delete a key from a hash table */</span>
<a name="l00424"></a>00424 <span class="keyword">static</span> <span class="keywordtype">void</span> *
<a name="l00425"></a>00425 <span class="keyword">delete</span>(<a class="code" href="structhash__table__t.html">hash_table_t</a> * h, uint32 hash, <span class="keyword">const</span> <span class="keywordtype">char</span> *key, <span class="keywordtype">size_t</span> len)
<a name="l00426"></a>00426 {
<a name="l00427"></a>00427 <a class="code" href="structhash__entry__s.html" title="A note by ARCHAN at 20050510: Technically what we use is so-called &quot;hash table with buckets&quot...">hash_entry_t</a> *entry, *prev;
<a name="l00428"></a>00428 <span class="keywordtype">void</span> *val;
<a name="l00429"></a>00429
<a name="l00430"></a>00430 prev = NULL;
<a name="l00431"></a>00431 entry = &(h->table[hash]);
<a name="l00432"></a>00432 <span class="keywordflow">if</span> (entry->key == NULL)
<a name="l00433"></a>00433 <span class="keywordflow">return</span> NULL;
<a name="l00434"></a>00434
<a name="l00435"></a>00435 <span class="keywordflow">if</span> (h->nocase) {
<a name="l00436"></a>00436 <span class="keywordflow">while</span> (entry && ((entry-><a class="code" href="structhash__entry__s.html#af1ec5f16059ced6d9a8ae4d36ca7e2b3" title="Key string, NULL if this is an empty slot.">len</a> != len)
<a name="l00437"></a>00437 || (keycmp_nocase(entry, key) != 0))) {
<a name="l00438"></a>00438 prev = entry;
<a name="l00439"></a>00439 entry = entry-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a>;
<a name="l00440"></a>00440 }
<a name="l00441"></a>00441 }
<a name="l00442"></a>00442 <span class="keywordflow">else</span> {
<a name="l00443"></a>00443 <span class="keywordflow">while</span> (entry && ((entry-><a class="code" href="structhash__entry__s.html#af1ec5f16059ced6d9a8ae4d36ca7e2b3" title="Key string, NULL if this is an empty slot.">len</a> != len)
<a name="l00444"></a>00444 || (keycmp_case(entry, key) != 0))) {
<a name="l00445"></a>00445 prev = entry;
<a name="l00446"></a>00446 entry = entry-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a>;
<a name="l00447"></a>00447 }
<a name="l00448"></a>00448 }
<a name="l00449"></a>00449
<a name="l00450"></a>00450 <span class="keywordflow">if</span> (entry == NULL)
<a name="l00451"></a>00451 <span class="keywordflow">return</span> NULL;
<a name="l00452"></a>00452
<a name="l00453"></a>00453 <span class="comment">/* At this point, entry will be the one required to be deleted, prev</span>
<a name="l00454"></a>00454 <span class="comment"> will contain the previous entry</span>
<a name="l00455"></a>00455 <span class="comment"> */</span>
<a name="l00456"></a>00456 val = entry-><a class="code" href="structhash__entry__s.html#a0d57012963084fed93886681108aa636" title="Key-length; the key string does not have to be a C-style NULL terminated string; it can have arbitrar...">val</a>;
<a name="l00457"></a>00457
<a name="l00458"></a>00458 <span class="keywordflow">if</span> (prev == NULL) {
<a name="l00459"></a>00459 <span class="comment">/* That is to say the entry in the hash table (not the chain) matched the key. */</span>
<a name="l00460"></a>00460 <span class="comment">/* We will then copy the things from the next entry to the hash table */</span>
<a name="l00461"></a>00461 prev = entry;
<a name="l00462"></a>00462 <span class="keywordflow">if</span> (entry-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a>) { <span class="comment">/* There is a next entry, great, copy it. */</span>
<a name="l00463"></a>00463 entry = entry-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a>;
<a name="l00464"></a>00464 prev->key = entry->key;
<a name="l00465"></a>00465 prev-><a class="code" href="structhash__entry__s.html#af1ec5f16059ced6d9a8ae4d36ca7e2b3" title="Key string, NULL if this is an empty slot.">len</a> = entry-><a class="code" href="structhash__entry__s.html#af1ec5f16059ced6d9a8ae4d36ca7e2b3" title="Key string, NULL if this is an empty slot.">len</a>;
<a name="l00466"></a>00466 prev-><a class="code" href="structhash__entry__s.html#a0d57012963084fed93886681108aa636" title="Key-length; the key string does not have to be a C-style NULL terminated string; it can have arbitrar...">val</a> = entry-><a class="code" href="structhash__entry__s.html#a0d57012963084fed93886681108aa636" title="Key-length; the key string does not have to be a C-style NULL terminated string; it can have arbitrar...">val</a>;
<a name="l00467"></a>00467 prev-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a> = entry-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a>;
<a name="l00468"></a>00468 <a class="code" href="ckd__alloc_8h.html#a31c6b405558620ac37599737b5722fbf" title="Test and free a 1-D array.">ckd_free</a>(entry);
<a name="l00469"></a>00469 }
<a name="l00470"></a>00470 <span class="keywordflow">else</span> { <span class="comment">/* There is not a next entry, just set the key to null */</span>
<a name="l00471"></a>00471 prev->key = NULL;
<a name="l00472"></a>00472 prev-><a class="code" href="structhash__entry__s.html#af1ec5f16059ced6d9a8ae4d36ca7e2b3" title="Key string, NULL if this is an empty slot.">len</a> = 0;
<a name="l00473"></a>00473 prev-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a> = NULL;
<a name="l00474"></a>00474 }
<a name="l00475"></a>00475
<a name="l00476"></a>00476 }
<a name="l00477"></a>00477 <span class="keywordflow">else</span> { <span class="comment">/* This case is simple */</span>
<a name="l00478"></a>00478 prev-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a> = entry-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a>;
<a name="l00479"></a>00479 <a class="code" href="ckd__alloc_8h.html#a31c6b405558620ac37599737b5722fbf" title="Test and free a 1-D array.">ckd_free</a>(entry);
<a name="l00480"></a>00480 }
<a name="l00481"></a>00481
<a name="l00482"></a>00482 <span class="comment">/* Do wiring and free the entry */</span>
<a name="l00483"></a>00483
<a name="l00484"></a>00484 --h->inuse;
<a name="l00485"></a>00485
<a name="l00486"></a>00486 <span class="keywordflow">return</span> val;
<a name="l00487"></a>00487 }
<a name="l00488"></a>00488
<a name="l00489"></a>00489 <span class="keywordtype">void</span>
<a name="l00490"></a><a class="code" href="hash__table_8h.html#acab374d21e25009d397642e3465308c7">00490</a> <a class="code" href="hash__table_8h.html#acab374d21e25009d397642e3465308c7" title="Delete all entries from a hash_table.">hash_table_empty</a>(<a class="code" href="structhash__table__t.html">hash_table_t</a> *h)
<a name="l00491"></a>00491 {
<a name="l00492"></a>00492 <a class="code" href="structhash__entry__s.html" title="A note by ARCHAN at 20050510: Technically what we use is so-called &quot;hash table with buckets&quot...">hash_entry_t</a> *e, *e2;
<a name="l00493"></a>00493 int32 i;
<a name="l00494"></a>00494
<a name="l00495"></a>00495 <span class="keywordflow">for</span> (i = 0; i < h-><a class="code" href="structhash__table__t.html#a34cc067a2c4f517ce8b8921965d0f8dd" title="Primary hash table, excluding entries that collide.">size</a>; i++) {
<a name="l00496"></a>00496 <span class="comment">/* Free collision lists. */</span>
<a name="l00497"></a>00497 <span class="keywordflow">for</span> (e = h->table[i].<a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a>; e; e = e2) {
<a name="l00498"></a>00498 e2 = e-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a>;
<a name="l00499"></a>00499 <a class="code" href="ckd__alloc_8h.html#a31c6b405558620ac37599737b5722fbf" title="Test and free a 1-D array.">ckd_free</a>((<span class="keywordtype">void</span> *) e);
<a name="l00500"></a>00500 }
<a name="l00501"></a>00501 memset(&h->table[i], 0, <span class="keyword">sizeof</span>(h->table[i]));
<a name="l00502"></a>00502 }
<a name="l00503"></a>00503 h-><a class="code" href="structhash__table__t.html#a8c691525a04e01751972d608948c8ac0" title="Primary hash table size, (is a prime#); NOTE: This is the number of primary entries ALLOCATED...">inuse</a> = 0;
<a name="l00504"></a>00504 }
<a name="l00505"></a>00505
<a name="l00506"></a>00506
<a name="l00507"></a>00507 <span class="keywordtype">void</span> *
<a name="l00508"></a><a class="code" href="hash__table_8h.html#aebfe63c3869c271b125a8413ee384412">00508</a> <a class="code" href="hash__table_8h.html#aebfe63c3869c271b125a8413ee384412" title="Try to add a new entry with given key and associated value to hash table h.">hash_table_enter</a>(<a class="code" href="structhash__table__t.html">hash_table_t</a> * h, <span class="keyword">const</span> <span class="keywordtype">char</span> *key, <span class="keywordtype">void</span> *val)
<a name="l00509"></a>00509 {
<a name="l00510"></a>00510 uint32 hash;
<a name="l00511"></a>00511 <span class="keywordtype">size_t</span> len;
<a name="l00512"></a>00512
<a name="l00513"></a>00513 hash = key2hash(h, key);
<a name="l00514"></a>00514 len = strlen(key);
<a name="l00515"></a>00515 <span class="keywordflow">return</span> (enter(h, hash, key, len, val, 0));
<a name="l00516"></a>00516 }
<a name="l00517"></a>00517
<a name="l00518"></a>00518 <span class="keywordtype">void</span> *
<a name="l00519"></a><a class="code" href="hash__table_8h.html#ae61b28ea189a98ef8f2a3c5521482968">00519</a> <a class="code" href="hash__table_8h.html#ae61b28ea189a98ef8f2a3c5521482968" title="Add a new entry with given key and value to hash table h.">hash_table_replace</a>(<a class="code" href="structhash__table__t.html">hash_table_t</a> * h, <span class="keyword">const</span> <span class="keywordtype">char</span> *key, <span class="keywordtype">void</span> *val)
<a name="l00520"></a>00520 {
<a name="l00521"></a>00521 uint32 hash;
<a name="l00522"></a>00522 <span class="keywordtype">size_t</span> len;
<a name="l00523"></a>00523
<a name="l00524"></a>00524 hash = key2hash(h, key);
<a name="l00525"></a>00525 len = strlen(key);
<a name="l00526"></a>00526 <span class="keywordflow">return</span> (enter(h, hash, key, len, val, 1));
<a name="l00527"></a>00527 }
<a name="l00528"></a>00528
<a name="l00529"></a>00529 <span class="keywordtype">void</span> *
<a name="l00530"></a><a class="code" href="hash__table_8h.html#af1d87b1b825c302473f2d7c5a3b88475">00530</a> <a class="code" href="hash__table_8h.html#af1d87b1b825c302473f2d7c5a3b88475" title="Delete an entry with given key and associated value to hash table h.">hash_table_delete</a>(<a class="code" href="structhash__table__t.html">hash_table_t</a> * h, <span class="keyword">const</span> <span class="keywordtype">char</span> *key)
<a name="l00531"></a>00531 {
<a name="l00532"></a>00532 uint32 hash;
<a name="l00533"></a>00533 <span class="keywordtype">size_t</span> len;
<a name="l00534"></a>00534
<a name="l00535"></a>00535 hash = key2hash(h, key);
<a name="l00536"></a>00536 len = strlen(key);
<a name="l00537"></a>00537
<a name="l00538"></a>00538 <span class="keywordflow">return</span> (<span class="keyword">delete</span>(h, hash, key, len));
<a name="l00539"></a>00539 }
<a name="l00540"></a>00540
<a name="l00541"></a>00541 <span class="keywordtype">void</span> *
<a name="l00542"></a><a class="code" href="hash__table_8h.html#a6f5752fadefe2662adb2c141f1511062">00542</a> <a class="code" href="hash__table_8h.html#a6f5752fadefe2662adb2c141f1511062" title="Like hash_table_enter, but with an explicitly specified key length, instead of a NULL-terminated, C-style key string.">hash_table_enter_bkey</a>(<a class="code" href="structhash__table__t.html">hash_table_t</a> * h, <span class="keyword">const</span> <span class="keywordtype">char</span> *key, <span class="keywordtype">size_t</span> len, <span class="keywordtype">void</span> *val)
<a name="l00543"></a>00543 {
<a name="l00544"></a>00544 uint32 hash;
<a name="l00545"></a>00545 <span class="keywordtype">char</span> *str;
<a name="l00546"></a>00546
<a name="l00547"></a>00547 str = makekey((uint8 *) key, len, NULL);
<a name="l00548"></a>00548 hash = key2hash(h, str);
<a name="l00549"></a>00549 <a class="code" href="ckd__alloc_8h.html#a31c6b405558620ac37599737b5722fbf" title="Test and free a 1-D array.">ckd_free</a>(str);
<a name="l00550"></a>00550
<a name="l00551"></a>00551 <span class="keywordflow">return</span> (enter(h, hash, key, len, val, 0));
<a name="l00552"></a>00552 }
<a name="l00553"></a>00553
<a name="l00554"></a>00554 <span class="keywordtype">void</span> *
<a name="l00555"></a><a class="code" href="hash__table_8h.html#a273237d63833e5625c830f421d9463de">00555</a> <a class="code" href="hash__table_8h.html#a273237d63833e5625c830f421d9463de" title="Like hash_table_replace, but with an explicitly specified key length, instead of a NULL-terminated...">hash_table_replace_bkey</a>(<a class="code" href="structhash__table__t.html">hash_table_t</a> * h, <span class="keyword">const</span> <span class="keywordtype">char</span> *key, <span class="keywordtype">size_t</span> len, <span class="keywordtype">void</span> *val)
<a name="l00556"></a>00556 {
<a name="l00557"></a>00557 uint32 hash;
<a name="l00558"></a>00558 <span class="keywordtype">char</span> *str;
<a name="l00559"></a>00559
<a name="l00560"></a>00560 str = makekey((uint8 *) key, len, NULL);
<a name="l00561"></a>00561 hash = key2hash(h, str);
<a name="l00562"></a>00562 <a class="code" href="ckd__alloc_8h.html#a31c6b405558620ac37599737b5722fbf" title="Test and free a 1-D array.">ckd_free</a>(str);
<a name="l00563"></a>00563
<a name="l00564"></a>00564 <span class="keywordflow">return</span> (enter(h, hash, key, len, val, 1));
<a name="l00565"></a>00565 }
<a name="l00566"></a>00566
<a name="l00567"></a>00567 <span class="keywordtype">void</span> *
<a name="l00568"></a><a class="code" href="hash__table_8h.html#aa2ab1f5eb2f1b4689645d1e1c19dc887">00568</a> <a class="code" href="hash__table_8h.html#aa2ab1f5eb2f1b4689645d1e1c19dc887" title="Like hash_table_delete, but with an explicitly specified key length, instead of a NULL-terminated...">hash_table_delete_bkey</a>(<a class="code" href="structhash__table__t.html">hash_table_t</a> * h, <span class="keyword">const</span> <span class="keywordtype">char</span> *key, <span class="keywordtype">size_t</span> len)
<a name="l00569"></a>00569 {
<a name="l00570"></a>00570 uint32 hash;
<a name="l00571"></a>00571 <span class="keywordtype">char</span> *str;
<a name="l00572"></a>00572
<a name="l00573"></a>00573 str = makekey((uint8 *) key, len, NULL);
<a name="l00574"></a>00574 hash = key2hash(h, str);
<a name="l00575"></a>00575
<a name="l00576"></a>00576 <span class="keywordflow">return</span> (<span class="keyword">delete</span>(h, hash, key, len));
<a name="l00577"></a>00577 }
<a name="l00578"></a>00578
<a name="l00579"></a>00579 <span class="keywordtype">void</span>
<a name="l00580"></a><a class="code" href="hash__table_8h.html#a2721f6b601c80ceeeae570589fd12e38">00580</a> <a class="code" href="hash__table_8h.html#a2721f6b601c80ceeeae570589fd12e38" title="Display a hash-with-chaining representation on the screen.">hash_table_display</a>(<a class="code" href="structhash__table__t.html">hash_table_t</a> * h, int32 showdisplay)
<a name="l00581"></a>00581 {
<a name="l00582"></a>00582 <a class="code" href="structhash__entry__s.html" title="A note by ARCHAN at 20050510: Technically what we use is so-called &quot;hash table with buckets&quot...">hash_entry_t</a> *e;
<a name="l00583"></a>00583 <span class="keywordtype">int</span> i, j;
<a name="l00584"></a>00584 j = 0;
<a name="l00585"></a>00585
<a name="l00586"></a>00586 <a class="code" href="err_8h.html#ae5a17ac5be8c738d3d977b1bea2d4538" title="Print logging information without header, to standard error stream.">E_INFOCONT</a>(<span class="stringliteral">"Hash with chaining representation of the hash table\n"</span>);
<a name="l00587"></a>00587
<a name="l00588"></a>00588 <span class="keywordflow">for</span> (i = 0; i < h-><a class="code" href="structhash__table__t.html#a34cc067a2c4f517ce8b8921965d0f8dd" title="Primary hash table, excluding entries that collide.">size</a>; i++) {
<a name="l00589"></a>00589 e = &(h->table[i]);
<a name="l00590"></a>00590 <span class="keywordflow">if</span> (e->key != NULL) {
<a name="l00591"></a>00591 <a class="code" href="err_8h.html#ae5a17ac5be8c738d3d977b1bea2d4538" title="Print logging information without header, to standard error stream.">E_INFOCONT</a>(<span class="stringliteral">"|key:"</span>);
<a name="l00592"></a>00592 <span class="keywordflow">if</span> (showdisplay)
<a name="l00593"></a>00593 <a class="code" href="err_8h.html#ae5a17ac5be8c738d3d977b1bea2d4538" title="Print logging information without header, to standard error stream.">E_INFOCONT</a>(<span class="stringliteral">"%s"</span>, e->key);
<a name="l00594"></a>00594 <span class="keywordflow">else</span>
<a name="l00595"></a>00595 <a class="code" href="err_8h.html#ae5a17ac5be8c738d3d977b1bea2d4538" title="Print logging information without header, to standard error stream.">E_INFOCONT</a>(<span class="stringliteral">"%p"</span>, e->key);
<a name="l00596"></a>00596
<a name="l00597"></a>00597 <a class="code" href="err_8h.html#ae5a17ac5be8c738d3d977b1bea2d4538" title="Print logging information without header, to standard error stream.">E_INFOCONT</a>(<span class="stringliteral">"|len:%d|val=%ld|->"</span>, e-><a class="code" href="structhash__entry__s.html#af1ec5f16059ced6d9a8ae4d36ca7e2b3" title="Key string, NULL if this is an empty slot.">len</a>, (<span class="keywordtype">long</span>)e-><a class="code" href="structhash__entry__s.html#a0d57012963084fed93886681108aa636" title="Key-length; the key string does not have to be a C-style NULL terminated string; it can have arbitrar...">val</a>);
<a name="l00598"></a>00598 <span class="keywordflow">if</span> (e-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a> == NULL) {
<a name="l00599"></a>00599 <a class="code" href="err_8h.html#ae5a17ac5be8c738d3d977b1bea2d4538" title="Print logging information without header, to standard error stream.">E_INFOCONT</a>(<span class="stringliteral">"NULL\n"</span>);
<a name="l00600"></a>00600 }
<a name="l00601"></a>00601 j++;
<a name="l00602"></a>00602
<a name="l00603"></a>00603 <span class="keywordflow">for</span> (e = e-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a>; e; e = e-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a>) {
<a name="l00604"></a>00604 <a class="code" href="err_8h.html#ae5a17ac5be8c738d3d977b1bea2d4538" title="Print logging information without header, to standard error stream.">E_INFOCONT</a>(<span class="stringliteral">"|key:"</span>);
<a name="l00605"></a>00605 <span class="keywordflow">if</span> (showdisplay)
<a name="l00606"></a>00606 <a class="code" href="err_8h.html#ae5a17ac5be8c738d3d977b1bea2d4538" title="Print logging information without header, to standard error stream.">E_INFOCONT</a>(<span class="stringliteral">"%s"</span>, e->key);
<a name="l00607"></a>00607
<a name="l00608"></a>00608 <a class="code" href="err_8h.html#ae5a17ac5be8c738d3d977b1bea2d4538" title="Print logging information without header, to standard error stream.">E_INFOCONT</a>(<span class="stringliteral">"|len:%d|val=%ld|->"</span>, e-><a class="code" href="structhash__entry__s.html#af1ec5f16059ced6d9a8ae4d36ca7e2b3" title="Key string, NULL if this is an empty slot.">len</a>, (<span class="keywordtype">long</span>)e-><a class="code" href="structhash__entry__s.html#a0d57012963084fed93886681108aa636" title="Key-length; the key string does not have to be a C-style NULL terminated string; it can have arbitrar...">val</a>);
<a name="l00609"></a>00609 <span class="keywordflow">if</span> (e-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a> == NULL) {
<a name="l00610"></a>00610 <a class="code" href="err_8h.html#ae5a17ac5be8c738d3d977b1bea2d4538" title="Print logging information without header, to standard error stream.">E_INFOCONT</a>(<span class="stringliteral">"NULL\n"</span>);
<a name="l00611"></a>00611 }
<a name="l00612"></a>00612 j++;
<a name="l00613"></a>00613 }
<a name="l00614"></a>00614 }
<a name="l00615"></a>00615 }
<a name="l00616"></a>00616
<a name="l00617"></a>00617 <a class="code" href="err_8h.html#ae5a17ac5be8c738d3d977b1bea2d4538" title="Print logging information without header, to standard error stream.">E_INFOCONT</a>(<span class="stringliteral">"The total number of keys =%d\n"</span>, j);
<a name="l00618"></a>00618 }
<a name="l00619"></a>00619
<a name="l00620"></a>00620
<a name="l00621"></a>00621 <a class="code" href="structgnode__s.html" title="A node in a generic list.">glist_t</a>
<a name="l00622"></a><a class="code" href="hash__table_8h.html#a61f59389f05d8871003da4692a9c2acc">00622</a> <a class="code" href="hash__table_8h.html#a61f59389f05d8871003da4692a9c2acc" title="Build a glist of valid hash_entry_t pointers from the given hash table.">hash_table_tolist</a>(<a class="code" href="structhash__table__t.html">hash_table_t</a> * h, int32 * count)
<a name="l00623"></a>00623 {
<a name="l00624"></a>00624 <a class="code" href="structgnode__s.html" title="A node in a generic list.">glist_t</a> g;
<a name="l00625"></a>00625 <a class="code" href="structhash__entry__s.html" title="A note by ARCHAN at 20050510: Technically what we use is so-called &quot;hash table with buckets&quot...">hash_entry_t</a> *e;
<a name="l00626"></a>00626 int32 i, j;
<a name="l00627"></a>00627
<a name="l00628"></a>00628 g = NULL;
<a name="l00629"></a>00629
<a name="l00630"></a>00630 j = 0;
<a name="l00631"></a>00631 <span class="keywordflow">for</span> (i = 0; i < h-><a class="code" href="structhash__table__t.html#a34cc067a2c4f517ce8b8921965d0f8dd" title="Primary hash table, excluding entries that collide.">size</a>; i++) {
<a name="l00632"></a>00632 e = &(h->table[i]);
<a name="l00633"></a>00633
<a name="l00634"></a>00634 <span class="keywordflow">if</span> (e->key != NULL) {
<a name="l00635"></a>00635 g = <a class="code" href="glist_8h.html#a77a9c20b7df5a289477af405ab778377" title="Create and prepend a new list node, with the given user-defined data, at the HEAD of the given generi...">glist_add_ptr</a>(g, (<span class="keywordtype">void</span> *) e);
<a name="l00636"></a>00636 j++;
<a name="l00637"></a>00637
<a name="l00638"></a>00638 <span class="keywordflow">for</span> (e = e->next; e; e = e->next) {
<a name="l00639"></a>00639 g = <a class="code" href="glist_8h.html#a77a9c20b7df5a289477af405ab778377" title="Create and prepend a new list node, with the given user-defined data, at the HEAD of the given generi...">glist_add_ptr</a>(g, (<span class="keywordtype">void</span> *) e);
<a name="l00640"></a>00640 j++;
<a name="l00641"></a>00641 }
<a name="l00642"></a>00642 }
<a name="l00643"></a>00643 }
<a name="l00644"></a>00644
<a name="l00645"></a>00645 <span class="keywordflow">if</span> (count)
<a name="l00646"></a>00646 *count = j;
<a name="l00647"></a>00647
<a name="l00648"></a>00648 <span class="keywordflow">return</span> g;
<a name="l00649"></a>00649 }
<a name="l00650"></a>00650
<a name="l00651"></a>00651 <a class="code" href="structhash__iter__s.html">hash_iter_t</a> *
<a name="l00652"></a><a class="code" href="hash__table_8h.html#aae6e6373d3c371d57861a9a875edb207">00652</a> <a class="code" href="hash__table_8h.html#aae6e6373d3c371d57861a9a875edb207" title="Start iterating over key-value pairs in a hash table.">hash_table_iter</a>(<a class="code" href="structhash__table__t.html">hash_table_t</a> *h)
<a name="l00653"></a>00653 {
<a name="l00654"></a>00654 <a class="code" href="structhash__iter__s.html">hash_iter_t</a> *itor;
<a name="l00655"></a>00655
<a name="l00656"></a>00656 itor = <a class="code" href="ckd__alloc_8h.html#aa00ef21903bc4f8a972488417adc8d2e" title="Macros to simplify the use of above functions.">ckd_calloc</a>(1, <span class="keyword">sizeof</span>(*itor));
<a name="l00657"></a>00657 itor-><a class="code" href="structhash__iter__s.html#a02844d3426aaa62e41086c98a052ed7d" title="Hash table we are iterating over.">ht</a> = h;
<a name="l00658"></a>00658 <span class="keywordflow">return</span> <a class="code" href="hash__table_8h.html#ad023321efab26a30bd6d855fbdbe08a3" title="Get the next key-value pair in iteration.">hash_table_iter_next</a>(itor);
<a name="l00659"></a>00659 }
<a name="l00660"></a>00660
<a name="l00661"></a>00661 <a class="code" href="structhash__iter__s.html">hash_iter_t</a> *
<a name="l00662"></a><a class="code" href="hash__table_8h.html#ad023321efab26a30bd6d855fbdbe08a3">00662</a> <a class="code" href="hash__table_8h.html#ad023321efab26a30bd6d855fbdbe08a3" title="Get the next key-value pair in iteration.">hash_table_iter_next</a>(<a class="code" href="structhash__iter__s.html">hash_iter_t</a> *itor)
<a name="l00663"></a>00663 {
<a name="l00664"></a>00664 <span class="comment">/* If there is an entry, walk down its list. */</span>
<a name="l00665"></a>00665 <span class="keywordflow">if</span> (itor-><a class="code" href="structhash__iter__s.html#a8aa7d6656a165e2e74c42ae4c48ed78f" title="Current entry in that table.">ent</a>)
<a name="l00666"></a>00666 itor-><a class="code" href="structhash__iter__s.html#a8aa7d6656a165e2e74c42ae4c48ed78f" title="Current entry in that table.">ent</a> = itor-><a class="code" href="structhash__iter__s.html#a8aa7d6656a165e2e74c42ae4c48ed78f" title="Current entry in that table.">ent</a>-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a>;
<a name="l00667"></a>00667 <span class="comment">/* If we got to the end of the chain, or we had no entry, scan</span>
<a name="l00668"></a>00668 <span class="comment"> * forward in the table to find the next non-empty bucket. */</span>
<a name="l00669"></a>00669 <span class="keywordflow">if</span> (itor-><a class="code" href="structhash__iter__s.html#a8aa7d6656a165e2e74c42ae4c48ed78f" title="Current entry in that table.">ent</a> == NULL) {
<a name="l00670"></a>00670 <span class="keywordflow">while</span> (itor-><a class="code" href="structhash__iter__s.html#a9cb2842206d721ef3ef9b15c133ba3c9" title="Index of next bucket to search.">idx</a> < itor-><a class="code" href="structhash__iter__s.html#a02844d3426aaa62e41086c98a052ed7d" title="Hash table we are iterating over.">ht</a>-><a class="code" href="structhash__table__t.html#a34cc067a2c4f517ce8b8921965d0f8dd" title="Primary hash table, excluding entries that collide.">size</a>
<a name="l00671"></a>00671 && itor-><a class="code" href="structhash__iter__s.html#a02844d3426aaa62e41086c98a052ed7d" title="Hash table we are iterating over.">ht</a>->table[itor-><a class="code" href="structhash__iter__s.html#a9cb2842206d721ef3ef9b15c133ba3c9" title="Index of next bucket to search.">idx</a>].key == NULL)
<a name="l00672"></a>00672 ++itor-><a class="code" href="structhash__iter__s.html#a9cb2842206d721ef3ef9b15c133ba3c9" title="Index of next bucket to search.">idx</a>;
<a name="l00673"></a>00673 <span class="comment">/* If we did not find one then delete the iterator and</span>
<a name="l00674"></a>00674 <span class="comment"> * return NULL. */</span>
<a name="l00675"></a>00675 <span class="keywordflow">if</span> (itor-><a class="code" href="structhash__iter__s.html#a9cb2842206d721ef3ef9b15c133ba3c9" title="Index of next bucket to search.">idx</a> == itor-><a class="code" href="structhash__iter__s.html#a02844d3426aaa62e41086c98a052ed7d" title="Hash table we are iterating over.">ht</a>-><a class="code" href="structhash__table__t.html#a34cc067a2c4f517ce8b8921965d0f8dd" title="Primary hash table, excluding entries that collide.">size</a>) {
<a name="l00676"></a>00676 <a class="code" href="hash__table_8h.html#a7aa43b228d7dc24f5221d281debeb025" title="Delete an unfinished iterator.">hash_table_iter_free</a>(itor);
<a name="l00677"></a>00677 <span class="keywordflow">return</span> NULL;
<a name="l00678"></a>00678 }
<a name="l00679"></a>00679 <span class="comment">/* Otherwise use this next entry. */</span>
<a name="l00680"></a>00680 itor-><a class="code" href="structhash__iter__s.html#a8aa7d6656a165e2e74c42ae4c48ed78f" title="Current entry in that table.">ent</a> = itor-><a class="code" href="structhash__iter__s.html#a02844d3426aaa62e41086c98a052ed7d" title="Hash table we are iterating over.">ht</a>->table + itor-><a class="code" href="structhash__iter__s.html#a9cb2842206d721ef3ef9b15c133ba3c9" title="Index of next bucket to search.">idx</a>;
<a name="l00681"></a>00681 <span class="comment">/* Increase idx for the next time around. */</span>
<a name="l00682"></a>00682 ++itor-><a class="code" href="structhash__iter__s.html#a9cb2842206d721ef3ef9b15c133ba3c9" title="Index of next bucket to search.">idx</a>;
<a name="l00683"></a>00683 }
<a name="l00684"></a>00684 <span class="keywordflow">return</span> itor;
<a name="l00685"></a>00685 }
<a name="l00686"></a>00686
<a name="l00687"></a>00687 <span class="keywordtype">void</span>
<a name="l00688"></a><a class="code" href="hash__table_8h.html#a7aa43b228d7dc24f5221d281debeb025">00688</a> <a class="code" href="hash__table_8h.html#a7aa43b228d7dc24f5221d281debeb025" title="Delete an unfinished iterator.">hash_table_iter_free</a>(<a class="code" href="structhash__iter__s.html">hash_iter_t</a> *itor)
<a name="l00689"></a>00689 {
<a name="l00690"></a>00690 <a class="code" href="ckd__alloc_8h.html#a31c6b405558620ac37599737b5722fbf" title="Test and free a 1-D array.">ckd_free</a>(itor);
<a name="l00691"></a>00691 }
<a name="l00692"></a>00692
<a name="l00693"></a>00693 <span class="keywordtype">void</span>
<a name="l00694"></a><a class="code" href="hash__table_8h.html#a0a588c22946f8cc16328973035ed19e3">00694</a> <a class="code" href="hash__table_8h.html#a0a588c22946f8cc16328973035ed19e3" title="Free the specified hash table; the caller is responsible for freeing the key strings pointed to by th...">hash_table_free</a>(<a class="code" href="structhash__table__t.html">hash_table_t</a> * h)
<a name="l00695"></a>00695 {
<a name="l00696"></a>00696 <a class="code" href="structhash__entry__s.html" title="A note by ARCHAN at 20050510: Technically what we use is so-called &quot;hash table with buckets&quot...">hash_entry_t</a> *e, *e2;
<a name="l00697"></a>00697 int32 i;
<a name="l00698"></a>00698
<a name="l00699"></a>00699 <span class="keywordflow">if</span> (h == NULL)
<a name="l00700"></a>00700 <span class="keywordflow">return</span>;
<a name="l00701"></a>00701
<a name="l00702"></a>00702 <span class="comment">/* Free additional entries created for key collision cases */</span>
<a name="l00703"></a>00703 <span class="keywordflow">for</span> (i = 0; i < h-><a class="code" href="structhash__table__t.html#a34cc067a2c4f517ce8b8921965d0f8dd" title="Primary hash table, excluding entries that collide.">size</a>; i++) {
<a name="l00704"></a>00704 <span class="keywordflow">for</span> (e = h->table[i].<a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a>; e; e = e2) {
<a name="l00705"></a>00705 e2 = e-><a class="code" href="structhash__entry__s.html#aa855ac854b9c36cf23f60d9ac8093e7f" title="Value associated with above key.">next</a>;
<a name="l00706"></a>00706 <a class="code" href="ckd__alloc_8h.html#a31c6b405558620ac37599737b5722fbf" title="Test and free a 1-D array.">ckd_free</a>((<span class="keywordtype">void</span> *) e);
<a name="l00707"></a>00707 }
<a name="l00708"></a>00708 }
<a name="l00709"></a>00709
<a name="l00710"></a>00710 <a class="code" href="ckd__alloc_8h.html#a31c6b405558620ac37599737b5722fbf" title="Test and free a 1-D array.">ckd_free</a>((<span class="keywordtype">void</span> *) h->table);
<a name="l00711"></a>00711 <a class="code" href="ckd__alloc_8h.html#a31c6b405558620ac37599737b5722fbf" title="Test and free a 1-D array.">ckd_free</a>((<span class="keywordtype">void</span> *) h);
<a name="l00712"></a>00712 }
</pre></div></div>
</div>
<div id="nav-path" class="navpath">
<ul>
<li class="navelem"><b>hash_table.c</b> </li>
<li class="footer">Generated on Tue Apr 19 2011 for SphinxBase by 
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.7.3 </li>
</ul>
</div>
</body>
</html>
distrib
>
Fedora
>
14
>
x86_64
>
media
>
updates
>
by-pkgid
>
0b420d0fce195cf4115dc6a3be5c2da2
>
files
>
242
