-
Notifications
You must be signed in to change notification settings - Fork 265
/
utp_hash.h
146 lines (128 loc) · 5.19 KB
/
utp_hash.h
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
/*
* Copyright (c) 2010-2013 BitTorrent, Inc.
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
* THE SOFTWARE.
*/
#ifndef __UTP_HASH_H__
#define __UTP_HASH_H__
#include <string.h> // memset
#include <stdlib.h> // malloc
#include "utp_types.h"
#include "utp_templates.h"
// TODO: make utp_link_t a template parameter to HashTable
typedef uint32 utp_link_t;
#ifdef _MSC_VER
// Silence the warning about the C99-compliant zero-length array at the end of the structure
#pragma warning (disable: 4200)
#endif
typedef uint32 (*utp_hash_compute_t)(const void *keyp, size_t keysize);
typedef uint (*utp_hash_equal_t)(const void *key_a, const void *key_b, size_t keysize);
// In memory the HashTable is laid out as follows:
// ---------------------------- low
// | hash table data members |
// ---------------------------- _
// | indices | ^
// | . | | utp_link_t indices into the key-values.
// | . | .
// ---------------------------- - <----- bep
// | keys and values | each key-value pair has size total_size
// | . |
// | . |
// ---------------------------- high
//
// The code depends on the ability of the compiler to pad the length
// of the hash table data members structure to
// a length divisible by 32-bits with no remainder.
//
// Since the number of hash buckets (indices) should be odd, the code
// asserts this and adds one to the hash bucket count to ensure that the
// following key-value pairs array starts on a 32-bit boundary.
//
// The key-value pairs array should start on a 32-bit boundary, otherwise
// processors like the ARM will silently mangle 32-bit data in these structures
// (e.g., turning 0xABCD into 0XCDAB when moving a value from memory to register
// when the memory address is 16 bits offset from a 32-bit boundary),
// also, the value will be stored at an address two bytes lower than the address
// value would ordinarily indicate.
//
// The key-value pair is of type T. The first field in T must
// be the key, i.e., the first K bytes of T contains the key.
// total_size = sizeof(T) and thus sizeof(T) >= sizeof(K)
//
// N is the number of buckets.
//
struct utp_hash_t {
utp_link_t N;
byte K;
byte E;
size_t count;
utp_hash_compute_t hash_compute;
utp_hash_equal_t hash_equal;
utp_link_t allocated;
utp_link_t used;
utp_link_t free;
utp_link_t inits[0];
};
#ifdef _MSC_VER
#pragma warning (default: 4200)
#endif
struct utp_hash_iterator_t {
utp_link_t bucket;
utp_link_t elem;
utp_hash_iterator_t() : bucket(0xffffffff), elem(0xffffffff) {}
};
uint utp_hash_mem(const void *keyp, size_t keysize);
uint utp_hash_comp(const void *key_a, const void *key_b, size_t keysize);
utp_hash_t *utp_hash_create(int N, int key_size, int total_size, int initial, utp_hash_compute_t hashfun = utp_hash_mem, utp_hash_equal_t eqfun = NULL);
void *utp_hash_lookup(utp_hash_t *hash, const void *key);
void *utp_hash_add(utp_hash_t **hashp, const void *key);
void *utp_hash_del(utp_hash_t *hash, const void *key);
void *utp_hash_iterate(utp_hash_t *hash, utp_hash_iterator_t *iter);
void utp_hash_free_mem(utp_hash_t *hash);
/*
This HashTable requires that T have at least sizeof(K)+sizeof(utp_link_t) bytes.
Usually done like this:
struct K {
int whatever;
};
struct T {
K wtf;
utp_link_t link; // also wtf
};
*/
template<typename K, typename T> class utpHashTable {
utp_hash_t *hash;
public:
static uint compare(const void *k1, const void *k2, size_t ks) {
return *((K*)k1) == *((K*)k2);
}
static uint32 compute_hash(const void *k, size_t ks) {
return ((K*)k)->compute_hash();
}
void Init() { hash = NULL; }
bool Allocated() { return (hash != NULL); }
void Free() { utp_hash_free_mem(hash); hash = NULL; }
void Create(int N, int initial) { hash = utp_hash_create(N, sizeof(K), sizeof(T), initial, &compute_hash, &compare); }
T *Lookup(const K &key) { return (T*)utp_hash_lookup(hash, &key); }
T *Add(const K &key) { return (T*)utp_hash_add(&hash, &key); }
T *Delete(const K &key) { return (T*)utp_hash_del(hash, &key); }
T *Iterate(utp_hash_iterator_t &iterator) { return (T*)utp_hash_iterate(hash, &iterator); }
size_t GetCount() { return hash->count; }
};
#endif //__UTP_HASH_H__