-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathhashtable_8c_source.html
179 lines (179 loc) · 20.7 KB
/
hashtable_8c_source.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
<!-- HTML header for doxygen 1.8.10-->
<!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"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.9.4"/>
<title>librsync: hashtable.c Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<!-- ad -->
<script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
<!-- librsync -->
<ins class="adsbygoogle"
style="display:block"
data-ad-client="ca-pub-3547096055927362"
data-ad-slot="8322976738"
data-ad-format="auto"></ins>
<script>
(adsbygoogle = window.adsbygoogle || []).push({});
</script>
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td id="projectalign" style="padding-left: 0.5em;">
<div id="projectname">librsync
 <span id="projectnumber">2.3.4</span>
</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.9.4 -->
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(function() {
initMenu('',false,false,'search.php','Search');
});
/* @license-end */
</script>
<div id="main-nav"></div>
<div id="nav-path" class="navpath">
<ul>
<li class="navelem"><a class="el" href="dir_68267d1309a1af8e8297ef4c3efbcdba.html">src</a></li> </ul>
</div>
</div><!-- top -->
<div class="header">
<div class="headertitle"><div class="title">hashtable.c</div></div>
</div><!--header-->
<div class="contents">
<div class="fragment"><div class="line"><a id="l00001" name="l00001"></a><span class="lineno"> 1</span><span class="comment">/*= -*- c-basic-offset: 4; indent-tabs-mode: nil; -*-</span></div>
<div class="line"><a id="l00002" name="l00002"></a><span class="lineno"> 2</span><span class="comment"> *</span></div>
<div class="line"><a id="l00003" name="l00003"></a><span class="lineno"> 3</span><span class="comment"> * hashtable.c -- a generic hashtable implementation.</span></div>
<div class="line"><a id="l00004" name="l00004"></a><span class="lineno"> 4</span><span class="comment"> *</span></div>
<div class="line"><a id="l00005" name="l00005"></a><span class="lineno"> 5</span><span class="comment"> * Copyright (C) 2016 by Donovan Baarda <[email protected]></span></div>
<div class="line"><a id="l00006" name="l00006"></a><span class="lineno"> 6</span><span class="comment"> *</span></div>
<div class="line"><a id="l00007" name="l00007"></a><span class="lineno"> 7</span><span class="comment"> * This program is free software; you can redistribute it and/or modify</span></div>
<div class="line"><a id="l00008" name="l00008"></a><span class="lineno"> 8</span><span class="comment"> * it under the terms of the GNU Lesser General Public License as published by</span></div>
<div class="line"><a id="l00009" name="l00009"></a><span class="lineno"> 9</span><span class="comment"> * the Free Software Foundation; either version 2.1 of the License, or</span></div>
<div class="line"><a id="l00010" name="l00010"></a><span class="lineno"> 10</span><span class="comment"> * (at your option) any later version.</span></div>
<div class="line"><a id="l00011" name="l00011"></a><span class="lineno"> 11</span><span class="comment"> *</span></div>
<div class="line"><a id="l00012" name="l00012"></a><span class="lineno"> 12</span><span class="comment"> * This program is distributed in the hope that it will be useful,</span></div>
<div class="line"><a id="l00013" name="l00013"></a><span class="lineno"> 13</span><span class="comment"> * but WITHOUT ANY WARRANTY; without even the implied warranty of</span></div>
<div class="line"><a id="l00014" name="l00014"></a><span class="lineno"> 14</span><span class="comment"> * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the</span></div>
<div class="line"><a id="l00015" name="l00015"></a><span class="lineno"> 15</span><span class="comment"> * GNU Lesser General Public License for more details.</span></div>
<div class="line"><a id="l00016" name="l00016"></a><span class="lineno"> 16</span><span class="comment"> *</span></div>
<div class="line"><a id="l00017" name="l00017"></a><span class="lineno"> 17</span><span class="comment"> * You should have received a copy of the GNU Lesser General Public License</span></div>
<div class="line"><a id="l00018" name="l00018"></a><span class="lineno"> 18</span><span class="comment"> * along with this program; if not, write to the Free Software</span></div>
<div class="line"><a id="l00019" name="l00019"></a><span class="lineno"> 19</span><span class="comment"> * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.</span></div>
<div class="line"><a id="l00020" name="l00020"></a><span class="lineno"> 20</span><span class="comment"> */</span></div>
<div class="line"><a id="l00021" name="l00021"></a><span class="lineno"> 21</span><span class="preprocessor">#include <assert.h></span></div>
<div class="line"><a id="l00022" name="l00022"></a><span class="lineno"> 22</span><span class="preprocessor">#include <stdlib.h></span></div>
<div class="line"><a id="l00023" name="l00023"></a><span class="lineno"> 23</span><span class="preprocessor">#include "<a class="code" href="hashtable_8h.html">hashtable.h</a>"</span></div>
<div class="line"><a id="l00024" name="l00024"></a><span class="lineno"> 24</span> </div>
<div class="line"><a id="l00025" name="l00025"></a><span class="lineno"> 25</span><span class="comment">/* Open addressing works best if it can take advantage of memory caches using</span></div>
<div class="line"><a id="l00026" name="l00026"></a><span class="lineno"> 26</span><span class="comment"> locality for probes of adjacent buckets on collisions. So we pack the keys</span></div>
<div class="line"><a id="l00027" name="l00027"></a><span class="lineno"> 27</span><span class="comment"> tightly together in their own key table and avoid referencing the element</span></div>
<div class="line"><a id="l00028" name="l00028"></a><span class="lineno"> 28</span><span class="comment"> table and elements as much as possible. Key value zero is reserved as a</span></div>
<div class="line"><a id="l00029" name="l00029"></a><span class="lineno"> 29</span><span class="comment"> marker for an empty bucket to avoid checking for NULL in the element table.</span></div>
<div class="line"><a id="l00030" name="l00030"></a><span class="lineno"> 30</span><span class="comment"> If we do get a hash value of zero, we -1 to wrap it around to 0xffff. */</span></div>
<div class="line"><a id="l00031" name="l00031"></a><span class="lineno"> 31</span> </div>
<div class="line"><a id="l00032" name="l00032"></a><span class="lineno"> 32</span><span class="comment">/* Use max 0.7 load factor to avoid bad open addressing performance. */</span></div>
<div class="line"><a id="l00033" name="l00033"></a><span class="lineno"> 33</span><span class="preprocessor">#define HASHTABLE_LOADFACTOR_NUM 7</span></div>
<div class="line"><a id="l00034" name="l00034"></a><span class="lineno"> 34</span><span class="preprocessor">#define HASHTABLE_LOADFACTOR_DEN 10</span></div>
<div class="line"><a id="l00035" name="l00035"></a><span class="lineno"> 35</span> </div>
<div class="line"><a id="l00036" name="l00036"></a><span class="lineno"> 36</span><a class="code hl_struct" href="structhashtable.html">hashtable_t</a> *_hashtable_new(<span class="keywordtype">int</span> size)</div>
<div class="line"><a id="l00037" name="l00037"></a><span class="lineno"> 37</span>{</div>
<div class="line"><a id="l00038" name="l00038"></a><span class="lineno"> 38</span> <a class="code hl_struct" href="structhashtable.html">hashtable_t</a> *t;</div>
<div class="line"><a id="l00039" name="l00039"></a><span class="lineno"> 39</span> <span class="keywordtype">unsigned</span> size2, bits2;</div>
<div class="line"><a id="l00040" name="l00040"></a><span class="lineno"> 40</span> </div>
<div class="line"><a id="l00041" name="l00041"></a><span class="lineno"> 41</span> <span class="comment">/* Adjust requested size to account for max load factor. */</span></div>
<div class="line"><a id="l00042" name="l00042"></a><span class="lineno"> 42</span> size = 1 + size * HASHTABLE_LOADFACTOR_DEN / HASHTABLE_LOADFACTOR_NUM;</div>
<div class="line"><a id="l00043" name="l00043"></a><span class="lineno"> 43</span> <span class="comment">/* Use next power of 2 larger than the requested size and get mask bits. */</span></div>
<div class="line"><a id="l00044" name="l00044"></a><span class="lineno"> 44</span> <span class="keywordflow">for</span> (size2 = 2, bits2 = 1; (int)size2 < size; size2 <<= 1, bits2++) ;</div>
<div class="line"><a id="l00045" name="l00045"></a><span class="lineno"> 45</span> <span class="keywordflow">if</span> (!(t = calloc(1, <span class="keyword">sizeof</span>(<a class="code hl_struct" href="structhashtable.html">hashtable_t</a>)+ size2 * <span class="keyword">sizeof</span>(<span class="keywordtype">unsigned</span>))))</div>
<div class="line"><a id="l00046" name="l00046"></a><span class="lineno"> 46</span> <span class="keywordflow">return</span> NULL;</div>
<div class="line"><a id="l00047" name="l00047"></a><span class="lineno"> 47</span> <span class="keywordflow">if</span> (!(t-><a class="code hl_variable" href="structhashtable.html#ac624838d2888397a8374fb2aabd330fe">etable</a> = calloc(size2, <span class="keyword">sizeof</span>(<span class="keywordtype">void</span> *)))) {</div>
<div class="line"><a id="l00048" name="l00048"></a><span class="lineno"> 48</span> _hashtable_free(t);</div>
<div class="line"><a id="l00049" name="l00049"></a><span class="lineno"> 49</span> <span class="keywordflow">return</span> NULL;</div>
<div class="line"><a id="l00050" name="l00050"></a><span class="lineno"> 50</span> }</div>
<div class="line"><a id="l00051" name="l00051"></a><span class="lineno"> 51</span> t-><a class="code hl_variable" href="structhashtable.html#ab62bd10297b090cfce7d728fd650e51d">size</a> = (int)size2;</div>
<div class="line"><a id="l00052" name="l00052"></a><span class="lineno"> 52</span> t-><a class="code hl_variable" href="structhashtable.html#a849d7b9cab945feabe177cd5e61f46a7">count</a> = 0;</div>
<div class="line"><a id="l00053" name="l00053"></a><span class="lineno"> 53</span> t-><a class="code hl_variable" href="structhashtable.html#ab89d13f1e21e46e4790780095e1f14a0">tmask</a> = size2 - 1;</div>
<div class="line"><a id="l00054" name="l00054"></a><span class="lineno"> 54</span><span class="preprocessor">#ifndef HASHTABLE_NBLOOM</span></div>
<div class="line"><a id="l00055" name="l00055"></a><span class="lineno"> 55</span> <span class="keywordflow">if</span> (!(t-><a class="code hl_variable" href="structhashtable.html#aa4b5d6817ee43aae5cc08bff4c0b6b75">kbloom</a> = calloc((size2 + 7) / 8, <span class="keyword">sizeof</span>(<span class="keywordtype">unsigned</span> <span class="keywordtype">char</span>)))) {</div>
<div class="line"><a id="l00056" name="l00056"></a><span class="lineno"> 56</span> _hashtable_free(t);</div>
<div class="line"><a id="l00057" name="l00057"></a><span class="lineno"> 57</span> <span class="keywordflow">return</span> NULL;</div>
<div class="line"><a id="l00058" name="l00058"></a><span class="lineno"> 58</span> }</div>
<div class="line"><a id="l00059" name="l00059"></a><span class="lineno"> 59</span> t-><a class="code hl_variable" href="structhashtable.html#afe6082e065c17d152a5e00150edc9b40">bshift</a> = (unsigned)<span class="keyword">sizeof</span>(<span class="keywordtype">unsigned</span>) * 8 - bits2;</div>
<div class="line"><a id="l00060" name="l00060"></a><span class="lineno"> 60</span> assert(t-><a class="code hl_variable" href="structhashtable.html#ab89d13f1e21e46e4790780095e1f14a0">tmask</a> == (<span class="keywordtype">unsigned</span>)-1 >> t-><a class="code hl_variable" href="structhashtable.html#afe6082e065c17d152a5e00150edc9b40">bshift</a>);</div>
<div class="line"><a id="l00061" name="l00061"></a><span class="lineno"> 61</span><span class="preprocessor">#endif</span></div>
<div class="line"><a id="l00062" name="l00062"></a><span class="lineno"> 62</span><span class="preprocessor">#ifndef HASHTABLE_NSTATS</span></div>
<div class="line"><a id="l00063" name="l00063"></a><span class="lineno"> 63</span> t-><a class="code hl_variable" href="structhashtable.html#a2d26a02a9bc656f5acab82ee1f45c82e">find_count</a> = t-><a class="code hl_variable" href="structhashtable.html#a560df9089435475d6ba5cbd2e0d0076d">match_count</a> = t-><a class="code hl_variable" href="structhashtable.html#ad2995922a4f5fb09e8c0dcc092be91bf">hashcmp_count</a> = t-><a class="code hl_variable" href="structhashtable.html#aa5ee8c97823281612f138de984dd46f3">entrycmp_count</a> = 0;</div>
<div class="line"><a id="l00064" name="l00064"></a><span class="lineno"> 64</span><span class="preprocessor">#endif</span></div>
<div class="line"><a id="l00065" name="l00065"></a><span class="lineno"> 65</span> <span class="keywordflow">return</span> t;</div>
<div class="line"><a id="l00066" name="l00066"></a><span class="lineno"> 66</span>}</div>
<div class="line"><a id="l00067" name="l00067"></a><span class="lineno"> 67</span> </div>
<div class="line"><a id="l00068" name="l00068"></a><span class="lineno"> 68</span><span class="keywordtype">void</span> _hashtable_free(<a class="code hl_struct" href="structhashtable.html">hashtable_t</a> *t)</div>
<div class="line"><a id="l00069" name="l00069"></a><span class="lineno"> 69</span>{</div>
<div class="line"><a id="l00070" name="l00070"></a><span class="lineno"> 70</span> <span class="keywordflow">if</span> (t) {</div>
<div class="line"><a id="l00071" name="l00071"></a><span class="lineno"> 71</span> free(t-><a class="code hl_variable" href="structhashtable.html#ac624838d2888397a8374fb2aabd330fe">etable</a>);</div>
<div class="line"><a id="l00072" name="l00072"></a><span class="lineno"> 72</span><span class="preprocessor">#ifndef HASHTABLE_NBLOOM</span></div>
<div class="line"><a id="l00073" name="l00073"></a><span class="lineno"> 73</span> free(t-><a class="code hl_variable" href="structhashtable.html#aa4b5d6817ee43aae5cc08bff4c0b6b75">kbloom</a>);</div>
<div class="line"><a id="l00074" name="l00074"></a><span class="lineno"> 74</span><span class="preprocessor">#endif</span></div>
<div class="line"><a id="l00075" name="l00075"></a><span class="lineno"> 75</span> free(t);</div>
<div class="line"><a id="l00076" name="l00076"></a><span class="lineno"> 76</span> }</div>
<div class="line"><a id="l00077" name="l00077"></a><span class="lineno"> 77</span>}</div>
<div class="ttc" id="ahashtable_8h_html"><div class="ttname"><a href="hashtable_8h.html">hashtable.h</a></div><div class="ttdoc">A generic open addressing hashtable.</div></div>
<div class="ttc" id="astructhashtable_html"><div class="ttname"><a href="structhashtable.html">hashtable</a></div><div class="ttdoc">The hashtable type.</div><div class="ttdef"><b>Definition:</b> <a href="hashtable_8h_source.html#l00128">hashtable.h:128</a></div></div>
<div class="ttc" id="astructhashtable_html_a2d26a02a9bc656f5acab82ee1f45c82e"><div class="ttname"><a href="structhashtable.html#a2d26a02a9bc656f5acab82ee1f45c82e">hashtable::find_count</a></div><div class="ttdeci">long find_count</div><div class="ttdoc">The count of finds tried.</div><div class="ttdef"><b>Definition:</b> <a href="hashtable_8h_source.html#l00137">hashtable.h:137</a></div></div>
<div class="ttc" id="astructhashtable_html_a560df9089435475d6ba5cbd2e0d0076d"><div class="ttname"><a href="structhashtable.html#a560df9089435475d6ba5cbd2e0d0076d">hashtable::match_count</a></div><div class="ttdeci">long match_count</div><div class="ttdoc">The count of matches found.</div><div class="ttdef"><b>Definition:</b> <a href="hashtable_8h_source.html#l00138">hashtable.h:138</a></div></div>
<div class="ttc" id="astructhashtable_html_a849d7b9cab945feabe177cd5e61f46a7"><div class="ttname"><a href="structhashtable.html#a849d7b9cab945feabe177cd5e61f46a7">hashtable::count</a></div><div class="ttdeci">int count</div><div class="ttdoc">Number of entries in hashtable.</div><div class="ttdef"><b>Definition:</b> <a href="hashtable_8h_source.html#l00130">hashtable.h:130</a></div></div>
<div class="ttc" id="astructhashtable_html_aa4b5d6817ee43aae5cc08bff4c0b6b75"><div class="ttname"><a href="structhashtable.html#aa4b5d6817ee43aae5cc08bff4c0b6b75">hashtable::kbloom</a></div><div class="ttdeci">unsigned char * kbloom</div><div class="ttdoc">Bloom filter of hash keys with k=1.</div><div class="ttdef"><b>Definition:</b> <a href="hashtable_8h_source.html#l00143">hashtable.h:143</a></div></div>
<div class="ttc" id="astructhashtable_html_aa5ee8c97823281612f138de984dd46f3"><div class="ttname"><a href="structhashtable.html#aa5ee8c97823281612f138de984dd46f3">hashtable::entrycmp_count</a></div><div class="ttdeci">long entrycmp_count</div><div class="ttdoc">The count of entry compares done.</div><div class="ttdef"><b>Definition:</b> <a href="hashtable_8h_source.html#l00140">hashtable.h:140</a></div></div>
<div class="ttc" id="astructhashtable_html_ab62bd10297b090cfce7d728fd650e51d"><div class="ttname"><a href="structhashtable.html#ab62bd10297b090cfce7d728fd650e51d">hashtable::size</a></div><div class="ttdeci">int size</div><div class="ttdoc">Size of allocated hashtable.</div><div class="ttdef"><b>Definition:</b> <a href="hashtable_8h_source.html#l00129">hashtable.h:129</a></div></div>
<div class="ttc" id="astructhashtable_html_ab89d13f1e21e46e4790780095e1f14a0"><div class="ttname"><a href="structhashtable.html#ab89d13f1e21e46e4790780095e1f14a0">hashtable::tmask</a></div><div class="ttdeci">unsigned tmask</div><div class="ttdoc">Mask to get the hashtable index.</div><div class="ttdef"><b>Definition:</b> <a href="hashtable_8h_source.html#l00131">hashtable.h:131</a></div></div>
<div class="ttc" id="astructhashtable_html_ac624838d2888397a8374fb2aabd330fe"><div class="ttname"><a href="structhashtable.html#ac624838d2888397a8374fb2aabd330fe">hashtable::etable</a></div><div class="ttdeci">void ** etable</div><div class="ttdoc">Table of pointers to entries.</div><div class="ttdef"><b>Definition:</b> <a href="hashtable_8h_source.html#l00145">hashtable.h:145</a></div></div>
<div class="ttc" id="astructhashtable_html_ad2995922a4f5fb09e8c0dcc092be91bf"><div class="ttname"><a href="structhashtable.html#ad2995922a4f5fb09e8c0dcc092be91bf">hashtable::hashcmp_count</a></div><div class="ttdeci">long hashcmp_count</div><div class="ttdoc">The count of hash compares done.</div><div class="ttdef"><b>Definition:</b> <a href="hashtable_8h_source.html#l00139">hashtable.h:139</a></div></div>
<div class="ttc" id="astructhashtable_html_afe6082e065c17d152a5e00150edc9b40"><div class="ttname"><a href="structhashtable.html#afe6082e065c17d152a5e00150edc9b40">hashtable::bshift</a></div><div class="ttdeci">unsigned bshift</div><div class="ttdoc">Shift to get the bloomfilter index.</div><div class="ttdef"><b>Definition:</b> <a href="hashtable_8h_source.html#l00133">hashtable.h:133</a></div></div>
</div><!-- fragment --></div><!-- contents -->
<!-- HTML footer for doxygen 1.8.10-->
<!-- start footer part -->
<!-- ad -->
<script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
<!-- librsync -->
<ins class="adsbygoogle"
style="display:block"
data-ad-client="ca-pub-3547096055927362"
data-ad-slot="8322976738"
data-ad-format="auto"></ins>
<script>
(adsbygoogle = window.adsbygoogle || []).push({});
</script>
<!-- analytics -->
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-71109100-1', 'auto');
ga('send', 'pageview');
</script>
<hr class="footer"/><address class="footer"><small>
Generated on Sun Feb 19 2023 16:26:49 for librsync by  <a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.9.4
</small></address>
</body>
</html>