librsync
2.3.1
src
hashtable.c
1
/*= -*- c-basic-offset: 4; indent-tabs-mode: nil; -*-
2
*
3
* hashtable.c -- a generic hashtable implementation.
4
*
5
* Copyright (C) 2016 by Donovan Baarda <abo@minkirri.apana.org.au>
6
*
7
* This program is free software; you can redistribute it and/or modify
8
* it under the terms of the GNU Lesser General Public License as published by
9
* the Free Software Foundation; either version 2.1 of the License, or
10
* (at your option) any later version.
11
*
12
* This program is distributed in the hope that it will be useful,
13
* but WITHOUT ANY WARRANTY; without even the implied warranty of
14
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15
* GNU Lesser General Public License for more details.
16
*
17
* You should have received a copy of the GNU Lesser General Public License
18
* along with this program; if not, write to the Free Software
19
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20
*/
21
#include <assert.h>
22
#include <stdlib.h>
23
#include "
hashtable.h
"
24
25
/* Open addressing works best if it can take advantage of memory caches using
26
locality for probes of adjacent buckets on collisions. So we pack the keys
27
tightly together in their own key table and avoid referencing the element
28
table and elements as much as possible. Key value zero is reserved as a
29
marker for an empty bucket to avoid checking for NULL in the element table.
30
If we do get a hash value of zero, we -1 to wrap it around to 0xffff. */
31
32
/* Use max 0.7 load factor to avoid bad open addressing performance. */
33
#define HASHTABLE_LOADFACTOR_NUM 7
34
#define HASHTABLE_LOADFACTOR_DEN 10
35
36
hashtable_t
*_hashtable_new(
int
size)
37
{
38
hashtable_t
*t;
39
int
size2, bits2;
40
41
/* Adjust requested size to account for max load factor. */
42
size = 1 + size * HASHTABLE_LOADFACTOR_DEN / HASHTABLE_LOADFACTOR_NUM;
43
/* Use next power of 2 larger than the requested size and get mask bits. */
44
for
(size2 = 2, bits2 = 1; size2 < size; size2 <<= 1, bits2++) ;
45
if
(!(t = calloc(1,
sizeof
(
hashtable_t
)+ size2 *
sizeof
(
unsigned
))))
46
return
NULL;
47
if
(!(t->
etable
= calloc(size2,
sizeof
(
void
*)))) {
48
_hashtable_free(t);
49
return
NULL;
50
}
51
t->
size
= size2;
52
t->
count
= 0;
53
t->
tmask
= size2 - 1;
54
#ifndef HASHTABLE_NBLOOM
55
if
(!(t->
kbloom
= calloc(size2 / 8,
sizeof
(
unsigned
char
)))) {
56
_hashtable_free(t);
57
return
NULL;
58
}
59
t->
bshift
=
sizeof
(unsigned) * 8 - bits2;
60
assert(t->
tmask
== (
unsigned
)-1 >> t->
bshift
);
61
#endif
62
#ifndef HASHTABLE_NSTATS
63
t->
find_count
= t->
match_count
= t->
hashcmp_count
= t->
entrycmp_count
= 0;
64
#endif
65
return
t;
66
}
67
68
void
_hashtable_free(
hashtable_t
*t)
69
{
70
if
(t) {
71
free(t->
etable
);
72
#ifndef HASHTABLE_NBLOOM
73
free(t->
kbloom
);
74
#endif
75
free(t);
76
}
77
}
hashtable::bshift
unsigned bshift
Shift to get the bloomfilter index.
Definition:
hashtable.h:135
hashtable::etable
void ** etable
Table of pointers to entries.
Definition:
hashtable.h:147
hashtable::find_count
long find_count
The count of finds tried.
Definition:
hashtable.h:139
hashtable::kbloom
unsigned char * kbloom
Bloom filter of hash keys with k=1.
Definition:
hashtable.h:145
hashtable::count
int count
Number of entries in hashtable.
Definition:
hashtable.h:132
hashtable::tmask
unsigned tmask
Mask to get the hashtable index.
Definition:
hashtable.h:133
hashtable::hashcmp_count
long hashcmp_count
The count of hash compares done.
Definition:
hashtable.h:141
hashtable.h
hashtable::match_count
long match_count
The count of matches found.
Definition:
hashtable.h:140
hashtable::size
int size
Size of allocated hashtable.
Definition:
hashtable.h:131
hashtable
The hashtable type.
Definition:
hashtable.h:130
hashtable::entrycmp_count
long entrycmp_count
The count of entry compares done.
Definition:
hashtable.h:142
Generated on Tue Aug 4 2020 00:00:00 for librsync by
1.8.18