kinetic-c  v0.12.0
Seagate Kinetic Protocol Client Library for C
yacht.c
Go to the documentation of this file.
1 /*
2 * kinetic-c
3 * Copyright (C) 2015 Seagate Technology.
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License
7 * as published by the Free Software Foundation; either version 2
8 * of the License, or (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18 *
19 */
20 
21 #include "yacht.h"
22 
23 #if 0
24 #include <stdio.h>
25 #define LOG(...) printf(__VA_ARGS__)
26 #else
27 #define LOG(...)
28 #endif
29 
30 #include "yacht_internals.h"
31 
32 static bool insert(int *buckets, void **values,
33  size_t mask, size_t max_fill,
34  int key, void *value, void **old_value);
35 static bool grow(struct yacht *y);
36 
37 #define DEF_SZ2 4
38 #define MAX_PROBES 16
39 
40 /* Init a hash table with approx. 2 ** sz2 buckets. */
41 struct yacht *Yacht_Init(uint8_t sz2) {
42  if (sz2 == 0) { sz2 = DEF_SZ2; }
43  size_t size = 1 << sz2;
44  struct yacht *y = calloc(1, sizeof(*y));
45  int *buckets = calloc(size, sizeof(*buckets));
46  void **values = calloc(size, sizeof(*values));
47  if (y && buckets && values) {
48  y->size = size;
49  y->mask = size - 1;
50  y->buckets = buckets;
51  y->values = values;
52  LOG(" -- init with size %zd\n", size);
53  for (size_t i = 0; i < size; i++) {
54  y->buckets[i] = YACHT_NO_KEY;
55  }
56  return y;
57  } else {
58  if (y) { free(y); }
59  if (buckets) { free(buckets); }
60  if (values) { free(values); }
61  return NULL;
62  }
63 }
64 
65 /* A large prime used to spread around the hashes. */
66 #define LARGE_PRIME (4294967291L /* (2 ** 32) - 5 */)
67 
68 /* Just a constant multiply, since we're hashing file descriptors. */
69 static size_t hash(int key) {
70  return key * LARGE_PRIME;
71 }
72 
73 bool Yacht_Get(struct yacht *y, int key, void **value) {
74  size_t b = hash(key) & y->mask;
75  LOG(" -- getting key %d with bucket %zd\n", key, b);
76 
77  for (size_t o = 0; o < y->size; o++) {
78  size_t i = (b + o) & y->mask; // wrap as necessary
79  int bv = y->buckets[i];
80  if (bv == key) {
81  if (value) { *value = y->values[i]; }
82  return true;
83  } else if (bv == YACHT_NO_KEY || bv == YACHT_DELETED) {
84  return false;
85  }
86  }
87  return false;
88 }
89 
90 /* Check if KEY is in the table. */
91 bool Yacht_Member(struct yacht *y, int key) {
92  LOG(" -- checking membership for %d\n", key);
93  return Yacht_Get(y, key, NULL);
94 }
95 
96 /* Set KEY to VALUE in the table. */
97 bool Yacht_Set(struct yacht *y, int key, void *value, void **old_value) {
98  LOG(" -- setting key %d\n", key);
99 
100  for (;;) {
101  size_t max = y->size / 2;
102  if (max > 16) { max = MAX_PROBES; }
103  if (insert(y->buckets, y->values, y->mask, max, key, value, old_value)) {
104  return true;
105  } else {
106  if (!grow(y)) { return false; }
107  }
108  }
109 }
110 
111 static bool insert(int *buckets, void **values,
112  size_t mask, size_t max_fill,
113  int key, void *value, void **old_value) {
114  size_t b = hash(key) & mask;
115 
116  for (size_t o = 0; o < max_fill; o++) {
117  if (o > 0) { LOG(" -- o %zd (max_fill %zd)\n", o, max_fill); }
118  size_t i = (b + o) & mask; // wrap as necessary
119  int bv = buckets[i];
120  LOG(" -- b %zd: %d\n", i, bv);
121  if (bv == key) {
122  if (old_value) { *old_value = values[i]; }
123  values[i] = value;
124  return true; /* already present */
125  } else if (bv == YACHT_NO_KEY || bv == YACHT_DELETED) {
126  buckets[i] = key;
127  values[i] = value;
128  return true;
129  }
130  }
131  return false; /* too full */
132 }
133 
134 static bool grow(struct yacht *y) {
135  size_t nsize = 2 * y->size;
136  LOG(" -- growing %zd => %zd\n", y->size, nsize);
137  size_t nmask = nsize - 1;
138  int *nbuckets = NULL;
139  void **nvalues = NULL;
140  nbuckets = malloc(nsize * sizeof(*nbuckets));
141  if (nbuckets == NULL) { return false; }
142  for (size_t i = 0; i < nsize; i++) {
143  nbuckets[i] = YACHT_NO_KEY;
144  }
145  nvalues = calloc(nsize, sizeof(*nvalues));
146  if (nvalues == NULL) {
147  free(nbuckets);
148  return false;
149  }
150 
151  for (size_t i = 0; i < y->size; i++) {
152  int key = y->buckets[i];
153  if (key != YACHT_NO_KEY && key != YACHT_DELETED) {
154  if (!insert(nbuckets, nvalues, nmask, nsize, key, y->values[i], NULL)) {
155  goto cleanup;
156  }
157  }
158  }
159  y->size = nsize;
160  free(y->buckets);
161  free(y->values);
162  y->buckets = nbuckets;
163  y->values = nvalues;
164  y->mask = nmask;
165  return true;
166 cleanup:
167  if (nbuckets) { free(nbuckets); }
168  if (nvalues) { free(nvalues); }
169 
170  return false;
171 }
172 
173 /* Remove KEY from the table. */
174 bool Yacht_Remove(struct yacht *y, int key, void **old_value) {
175  size_t b = hash(key) & y->mask;
176  LOG(" -- removing %d with bucket %zd\n", key, b);
177 
178  for (size_t o = 0; o < y->size; o++) {
179  size_t i = (b + o) & y->mask; // wrap as necessary
180  int bv = y->buckets[i];
181  LOG(" -- b %zd: %d\n", i, bv);
182  if (bv == key) {
183  if (y->buckets[(i + 1) & y->mask] == YACHT_NO_KEY) {
184  y->buckets[i] = YACHT_NO_KEY;
185  } else {
186  y->buckets[i] = YACHT_DELETED;
187  }
188  if (old_value) {
189  *old_value = y->values[i];
190  y->values[i] = NULL;
191  }
192  return true;
193  } else if (bv == YACHT_NO_KEY) {
194  return false; /* not present */
195  }
196  }
197 
198  return false;
199 }
200 
201 /* Free the table. */
202 void Yacht_Free(struct yacht *y, Yacht_Free_cb *cb, void *udata) {
203  if (y) {
204  for (size_t i = 0; i < y->size; i++) {
205  int key = y->buckets[i];
206  if (cb && key != YACHT_NO_KEY && key != YACHT_DELETED) {
207  cb(y->values[i], udata);
208  }
209  }
210  free(y->buckets);
211  free(y->values);
212  free(y);
213  }
214 }
#define DEF_SZ2
Definition: yacht.c:37
struct yacht * Yacht_Init(uint8_t sz2)
Init a hash table with approx.
Definition: yacht.c:41
size_t mask
Mask for hash table bucket array.
bool Yacht_Member(struct yacht *y, int key)
Check if KEY is in the table.
Definition: yacht.c:91
int * buckets
Hash table buckets (keys).
static size_t hash(int key)
Definition: yacht.c:69
bool Yacht_Set(struct yacht *y, int key, void *value, void **old_value)
Set KEY to VALUE in the table.
Definition: yacht.c:97
#define LARGE_PRIME
Definition: yacht.c:66
static bool grow(struct yacht *y)
Definition: yacht.c:134
void ** values
Values associated with keys, if any.
#define LOG(...)
Definition: yacht.c:27
bool Yacht_Get(struct yacht *y, int key, void **value)
Get KEY from the table, setting *value if found.
Definition: yacht.c:73
static bool insert(int *buckets, void **values, size_t mask, size_t max_fill, int key, void *value, void **old_value)
Definition: yacht.c:111
#define MAX_PROBES
Definition: yacht.c:38
void( Yacht_Free_cb)(void *value, void *udata)
Callback to free values associated with keys.
Definition: yacht.h:55
bool Yacht_Remove(struct yacht *y, int key, void **old_value)
Remove KEY from the table.
Definition: yacht.c:174
size_t size
Size of bucket array.
#define YACHT_DELETED
Special placeholder for a deleted key in a hash bucket.
Definition: yacht.h:31
void Yacht_Free(struct yacht *y, Yacht_Free_cb *cb, void *udata)
Free the table.
Definition: yacht.c:202
#define YACHT_NO_KEY
Special value for no key in a hash bucket.
Definition: yacht.h:28