<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"> <title>libghthash: ght_hash_table.h Source File</title> <link href="doxygen.css" rel="stylesheet" type="text/css"> </head><body> <!-- Generated by Doxygen 1.4.2 --> <div class="qindex"><a class="qindex" href="index.html">Main Page</a> | <a class="qindex" href="annotated.html">Class List</a> | <a class="qindex" href="dirs.html">Directories</a> | <a class="qindex" href="files.html">File List</a> | <a class="qindex" href="functions.html">Class Members</a> | <a class="qindex" href="globals.html">File Members</a></div> <div class="nav"> <a class="el" href="dir_000000.html">src</a></div> <h1>ght_hash_table.h</h1><a href="ght__hash__table_8h.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment">00001 <span class="comment">/*-*-c-*- ************************************************************</span> 00002 <span class="comment"> * Copyright (C) 2001-2005, Simon Kagstrom</span> 00003 <span class="comment"> *</span> 00004 <span class="comment"> * Filename: ght_hash_table.h.in</span> 00005 <span class="comment"> * Description: The definitions used in the hash table.</span> 00006 <span class="comment"> *</span> 00007 <span class="comment"> * This program is free software; you can redistribute it and/or</span> 00008 <span class="comment"> * modify it under the terms of the GNU Library General Public License</span> 00009 <span class="comment"> * as published by the Free Software Foundation; either version 2</span> 00010 <span class="comment"> * of the License, or (at your option) any later version.</span> 00011 <span class="comment"> *</span> 00012 <span class="comment"> * This program is distributed in the hope that it will be useful,</span> 00013 <span class="comment"> * but WITHOUT ANY WARRANTY; without even the implied warranty of</span> 00014 <span class="comment"> * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the</span> 00015 <span class="comment"> * GNU General Public License for more details.</span> 00016 <span class="comment"> *</span> 00017 <span class="comment"> * You should have received a copy of the GNU Library General Public</span> 00018 <span class="comment"> * License along with this program; if not, write to the Free Software</span> 00019 <span class="comment"> * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA</span> 00020 <span class="comment"> * 02111-1307, USA.</span> 00021 <span class="comment"> *</span> 00022 <span class="comment"> * $Id: ght_hash_table.h.in 5628 2005-11-27 07:57:45Z ska $</span> 00023 <span class="comment"> *</span> 00024 <span class="comment"> ********************************************************************/</span> 00025 00059 <span class="preprocessor">#ifndef GHT_HASH_TABLE_H</span> 00060 <span class="preprocessor"></span><span class="preprocessor">#define GHT_HASH_TABLE_H</span> 00061 <span class="preprocessor"></span> 00062 <span class="preprocessor">#include <stdlib.h></span> <span class="comment">/* size_t */</span> 00063 00064 <span class="preprocessor">#ifdef __cplusplus</span> 00065 <span class="preprocessor"></span><span class="keyword">extern</span> <span class="stringliteral">"C"</span> { 00066 <span class="preprocessor">#endif</span> 00067 <span class="preprocessor"></span> 00068 <span class="preprocessor">#define GHT_HEURISTICS_NONE 0</span> 00069 <span class="preprocessor"></span><span class="preprocessor">#define GHT_HEURISTICS_TRANSPOSE 1</span> 00070 <span class="preprocessor"></span><span class="preprocessor">#define GHT_HEURISTICS_MOVE_TO_FRONT 2</span> 00071 <span class="preprocessor"></span><span class="preprocessor">#define GHT_AUTOMATIC_REHASH 4</span> 00072 <span class="preprocessor"></span> 00073 <span class="preprocessor">#ifndef TRUE</span> 00074 <span class="preprocessor"></span><span class="preprocessor">#define TRUE 1</span> 00075 <span class="preprocessor"></span><span class="preprocessor">#endif</span> 00076 <span class="preprocessor"></span> 00077 <span class="preprocessor">#ifndef FALSE</span> 00078 <span class="preprocessor"></span><span class="preprocessor">#define FALSE 0</span> 00079 <span class="preprocessor"></span><span class="preprocessor">#endif</span> 00080 <span class="preprocessor"></span> <a name="l00082"></a><a class="code" href="ght__hash__table_8h.html#a6">00082</a> <span class="keyword">typedef</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="ght__hash__table_8h.html#a6">ght_uint32_t</a>; 00083 <a name="l00088"></a><a class="code" href="structs__hash__key.html">00088</a> <span class="keyword">typedef</span> <span class="keyword">struct </span><a class="code" href="structs__hash__key.html">s_hash_key</a> 00089 { <a name="l00090"></a><a class="code" href="structs__hash__key.html#o0">00090</a> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="structs__hash__key.html#o0">i_size</a>; <a name="l00091"></a><a class="code" href="structs__hash__key.html#o1">00091</a> <span class="keywordtype">void</span> *<a class="code" href="structs__hash__key.html#o1">p_key</a>; 00092 } <a class="code" href="structs__hash__key.html">ght_hash_key_t</a>; 00093 00094 <span class="comment">/*</span> 00095 <span class="comment"> * The structure for hash entries.</span> 00096 <span class="comment"> *</span> 00097 <span class="comment"> * LOCK: Should be possible to do somewhat atomically</span> 00098 <span class="comment"> */</span> 00099 <span class="keyword">typedef</span> <span class="keyword">struct </span>s_hash_entry 00100 { 00101 <span class="keywordtype">void</span> *p_data; 00102 00103 <span class="keyword">struct </span>s_hash_entry *p_next; 00104 <span class="keyword">struct </span>s_hash_entry *p_prev; 00105 <a class="code" href="structs__hash__key.html">ght_hash_key_t</a> key; 00106 } ght_hash_entry_t; 00107 00108 <span class="comment">/*</span> 00109 <span class="comment"> * The structure used in iterations. You should not care about the</span> 00110 <span class="comment"> * contents of this, it will be filled and updated by ght_first() and</span> 00111 <span class="comment"> * ght_next().</span> 00112 <span class="comment"> */</span> 00113 <span class="keyword">typedef</span> <span class="keyword">struct</span> 00114 <span class="keyword"></span>{ 00115 <span class="keywordtype">int</span> i_curr_bucket; <span class="comment">/* The current bucket */</span> 00116 ght_hash_entry_t *p_entry; <span class="comment">/* The current entry */</span> 00117 ght_hash_entry_t *p_next; <span class="comment">/* The next entry */</span> 00118 } ght_iterator_t; 00119 <a name="l00133"></a><a class="code" href="ght__hash__table_8h.html#a9">00133</a> <span class="keyword">typedef</span> <a class="code" href="ght__hash__table_8h.html#a6">ght_uint32_t</a> (*<a class="code" href="ght__hash__table_8h.html#a9">ght_fn_hash_t</a>)(<a class="code" href="structs__hash__key.html">ght_hash_key_t</a> *p_key); 00134 <a name="l00145"></a><a class="code" href="ght__hash__table_8h.html#a10">00145</a> <span class="keyword">typedef</span> <span class="keywordtype">void</span> *(*ght_fn_alloc_t)(size_t size); 00146 <a name="l00153"></a><a class="code" href="ght__hash__table_8h.html#a11">00153</a> <span class="keyword">typedef</span> void (*<a class="code" href="ght__hash__table_8h.html#a11">ght_fn_free_t</a>)(<span class="keywordtype">void</span> *ptr); 00154 00158 <span class="keyword">typedef</span> void (*ght_fn_bucket_free_callback_t)(<span class="keywordtype">void</span> *data, <span class="keywordtype">void</span> *key); 00159 <a name="l00163"></a><a class="code" href="structght__hash__table__t.html">00163</a> <span class="keyword">typedef</span> <span class="keyword">struct</span> 00164 <span class="keyword"></span>{ <a name="l00165"></a><a class="code" href="structght__hash__table__t.html#o0">00165</a> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i_items; <a name="l00166"></a><a class="code" href="structght__hash__table__t.html#o1">00166</a> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i_size; <a name="l00167"></a><a class="code" href="structght__hash__table__t.html#o2">00167</a> <a class="code" href="ght__hash__table_8h.html#a9">ght_fn_hash_t</a> fn_hash; <a name="l00168"></a><a class="code" href="structght__hash__table__t.html#o3">00168</a> ght_fn_alloc_t fn_alloc; <a name="l00169"></a><a class="code" href="structght__hash__table__t.html#o4">00169</a> <a class="code" href="ght__hash__table_8h.html#a11">ght_fn_free_t</a> fn_free; <a name="l00170"></a><a class="code" href="structght__hash__table__t.html#o5">00170</a> ght_fn_bucket_free_callback_t fn_bucket_free; <a name="l00171"></a><a class="code" href="structght__hash__table__t.html#o6">00171</a> <span class="keywordtype">int</span> i_heuristics; <a name="l00172"></a><a class="code" href="structght__hash__table__t.html#o7">00172</a> <span class="keywordtype">int</span> i_automatic_rehash; 00174 <span class="comment">/* private: */</span> 00175 ght_hash_entry_t **pp_entries; 00176 <span class="keywordtype">int</span> *p_nr; <span class="comment">/* The number of entries in each bucket */</span> 00177 <span class="keywordtype">int</span> i_size_mask; <span class="comment">/* The number of bits used in the size */</span> 00178 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bucket_limit; 00179 } <a class="code" href="structght__hash__table__t.html">ght_hash_table_t</a>; 00180 00200 <a class="code" href="structght__hash__table__t.html">ght_hash_table_t</a> *<a class="code" href="ght__hash__table_8h.html#a13">ght_create</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i_size); 00201 00223 <span class="keywordtype">void</span> <a class="code" href="ght__hash__table_8h.html#a14">ght_set_alloc</a>(<a class="code" href="structght__hash__table__t.html">ght_hash_table_t</a> *p_ht, ght_fn_alloc_t fn_alloc, <a class="code" href="ght__hash__table_8h.html#a11">ght_fn_free_t</a> fn_free); 00224 00235 <span class="keywordtype">void</span> <a class="code" href="ght__hash__table_8h.html#a15">ght_set_hash</a>(<a class="code" href="structght__hash__table__t.html">ght_hash_table_t</a> *p_ht, <a class="code" href="ght__hash__table_8h.html#a9">ght_fn_hash_t</a> fn_hash); 00236 00252 <span class="keywordtype">void</span> <a class="code" href="ght__hash__table_8h.html#a16">ght_set_heuristics</a>(<a class="code" href="structght__hash__table__t.html">ght_hash_table_t</a> *p_ht, <span class="keywordtype">int</span> i_heuristics); 00253 00268 <span class="keywordtype">void</span> <a class="code" href="ght__hash__table_8h.html#a17">ght_set_rehash</a>(<a class="code" href="structght__hash__table__t.html">ght_hash_table_t</a> *p_ht, <span class="keywordtype">int</span> b_rehash); 00269 00290 <span class="keywordtype">void</span> <a class="code" href="ght__hash__table_8h.html#a18">ght_set_bounded_buckets</a>(<a class="code" href="structght__hash__table__t.html">ght_hash_table_t</a> *p_ht, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> limit, ght_fn_bucket_free_callback_t fn); 00291 00292 00300 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="ght__hash__table_8h.html#a19">ght_size</a>(<a class="code" href="structght__hash__table__t.html">ght_hash_table_t</a> *p_ht); 00301 00309 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="ght__hash__table_8h.html#a20">ght_table_size</a>(<a class="code" href="structght__hash__table__t.html">ght_hash_table_t</a> *p_ht); 00310 00311 00346 <span class="keywordtype">int</span> <a class="code" href="ght__hash__table_8h.html#a21">ght_insert</a>(<a class="code" href="structght__hash__table__t.html">ght_hash_table_t</a> *p_ht, 00347 <span class="keywordtype">void</span> *p_entry_data, 00348 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i_key_size, <span class="keywordtype">void</span> *p_key_data); 00349 00362 <span class="keywordtype">void</span> *<a class="code" href="ght__hash__table_8h.html#a22">ght_replace</a>(<a class="code" href="structght__hash__table__t.html">ght_hash_table_t</a> *p_ht, 00363 <span class="keywordtype">void</span> *p_entry_data, 00364 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i_key_size, <span class="keywordtype">void</span> *p_key_data); 00365 00366 00377 <span class="keywordtype">void</span> *<a class="code" href="ght__hash__table_8h.html#a23">ght_get</a>(<a class="code" href="structght__hash__table__t.html">ght_hash_table_t</a> *p_ht, 00378 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i_key_size, <span class="keywordtype">void</span> *p_key_data); 00379 00390 <span class="keywordtype">void</span> *<a class="code" href="ght__hash__table_8h.html#a24">ght_remove</a>(<a class="code" href="structght__hash__table__t.html">ght_hash_table_t</a> *p_ht, 00391 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i_key_size, <span class="keywordtype">void</span> *p_key_data); 00392 00434 <span class="keywordtype">void</span> *<a class="code" href="ght__hash__table_8h.html#a25">ght_first</a>(<a class="code" href="structght__hash__table__t.html">ght_hash_table_t</a> *p_ht, ght_iterator_t *p_iterator, <span class="keywordtype">void</span> **pp_key); 00435 00455 <span class="keywordtype">void</span> *<a class="code" href="ght__hash__table_8h.html#a26">ght_next</a>(<a class="code" href="structght__hash__table__t.html">ght_hash_table_t</a> *p_ht, ght_iterator_t *p_iterator, <span class="keywordtype">void</span> **pp_key); 00456 00473 <span class="keywordtype">void</span> <a class="code" href="ght__hash__table_8h.html#a27">ght_rehash</a>(<a class="code" href="structght__hash__table__t.html">ght_hash_table_t</a> *p_ht, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i_size); 00474 00497 <span class="keywordtype">void</span> <a class="code" href="ght__hash__table_8h.html#a28">ght_finalize</a>(<a class="code" href="structght__hash__table__t.html">ght_hash_table_t</a> *p_ht); 00498 00499 <span class="comment">/* exported hash functions */</span> 00500 00513 ght_uint32_t <a class="code" href="ght__hash__table_8h.html#a29">ght_one_at_a_time_hash</a>(<a class="code" href="structs__hash__key.html">ght_hash_key_t</a> *p_key); 00514 00525 ght_uint32_t <a class="code" href="ght__hash__table_8h.html#a30">ght_rotating_hash</a>(<a class="code" href="structs__hash__key.html">ght_hash_key_t</a> *p_key); 00526 00537 ght_uint32_t <a class="code" href="ght__hash__table_8h.html#a31">ght_crc_hash</a>(<a class="code" href="structs__hash__key.html">ght_hash_key_t</a> *p_key); 00538 00539 <span class="preprocessor">#ifdef USE_PROFILING</span> 00540 <span class="preprocessor"></span> 00544 <span class="keywordtype">void</span> ght_print(<a class="code" href="structght__hash__table__t.html">ght_hash_table_t</a> *p_ht); 00545 <span class="preprocessor">#endif</span> 00546 <span class="preprocessor"></span> 00547 <span class="preprocessor">#ifdef __cplusplus</span> 00548 <span class="preprocessor"></span>} 00549 <span class="preprocessor">#endif</span> 00550 <span class="preprocessor"></span> 00551 <span class="preprocessor">#endif </span><span class="comment">/* GHT_HASH_TABLE_H */</span> </pre></div><hr size="1"><address style="align: right;"><small>Generated on Sun Nov 27 10:49:06 2005 for libghthash by <a href="http://www.doxygen.org/index.html"> <img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.4.2 </small></address> </body> </html>