1 // store.c
2 // hosts2zones
3 //
4 // Created by Dr. Rolf Jansen on 2014-08-01.
5 // Copyright (c) 2014 projectworld.net. All rights reserved.
6 //
7 // Redistribution and use in source and binary forms, with or without modification,
8 // are permitted provided that the following conditions are met:
9 //
10 // 1. Redistributions of source code must retain the above copyright notice,
11 // this list of conditions and the following disclaimer.
12 //
13 // 2. Redistributions in binary form must reproduce the above copyright notice,
14 // this list of conditions and the following disclaimer in the documentation
15 // and/or other materials provided with the distribution.
16 //
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS
18 // OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
19 // AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER
20 // OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
23 // IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
24 // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25
26
27 #include <stdlib.h>
28 #include <stdio.h>
29 #include <stddef.h>
30 #include <stdbool.h>
31 #include <stdint.h>
32 #include <stdarg.h>
33 #include <string.h>
34 #include <syslog.h>
35 #include <sys/stat.h>
36
37 #include "binutils.h"
38 #include "store.h"
39
40
41 #pragma mark ••• Value Data householding •••
42
releaseValue(Value * value)43 static inline void releaseValue(Value *value)
44 {
45 switch (-value->kind) // dynamic data, has to be released
46 {
47 case Simple:
48 case Data:
49 deallocate(VPR(value->p), false);
50 break;
51
52 case String:
53 deallocate(VPR(value->s), false);
54 break;
55
56 case Dictionary:
57 releaseTable((Node **)value->p);
58 break;
59 }
60 }
61
62
63 #pragma mark ••• AVL Tree •••
64
balanceNode(Node ** node)65 static int balanceNode(Node **node)
66 {
67 int change = 0;
68 Node *o = *node;
69 Node *p, *q;
70
71 if (o->B == -2)
72 {
73 if (p = o->L) // make the static analyzer happy
74 if (p->B == +1)
75 {
76 change = 1; // double left-right rotation
77 q = p->R; // left rotation
78 p->R = q->L;
79 q->L = p;
80 o->L = q->R; // right rotation
81 q->R = o;
82 o->B = +(q->B < 0);
83 p->B = -(q->B > 0);
84 q->B = 0;
85 *node = q;
86 }
87
88 else
89 {
90 change = p->B; // single right rotation
91 o->L = p->R;
92 p->R = o;
93 o->B = -(++p->B);
94 *node = p;
95 }
96 }
97
98 else if (o->B == +2)
99 {
100 if (q = o->R) // make the static analyzer happy
101 if (q->B == -1)
102 {
103 change = 1; // double right-left rotation
104 p = q->L; // right rotation
105 q->L = p->R;
106 p->R = q;
107 o->R = p->L; // left rotation
108 p->L = o;
109 o->B = -(p->B > 0);
110 q->B = +(p->B < 0);
111 p->B = 0;
112 *node = p;
113 }
114
115 else
116 {
117 change = q->B; // single left rotation
118 o->R = q->L;
119 q->L = o;
120 o->B = -(--q->B);
121 *node = q;
122 }
123 }
124
125 return change != 0;
126 }
127
128
pickPrevNode(Node ** node,Node ** exch)129 static int pickPrevNode(Node **node, Node **exch)
130 { // *exch on entry = parent node
131 Node *o = *node; // *exch on exit = picked previous value node
132
133 if (o->R)
134 {
135 *exch = o;
136 int change = -pickPrevNode(&o->R, exch);
137 if (change)
138 if (abs(o->B += change) > 1)
139 return balanceNode(node);
140 else
141 return o->B == 0;
142 else
143 return 0;
144 }
145
146 else if (o->L)
147 {
148 Node *p = o->L;
149 o->L = NULL;
150 (*exch)->R = p;
151 *exch = o;
152 return p->B == 0;
153 }
154
155 else
156 {
157 (*exch)->R = NULL;
158 *exch = o;
159 return 1;
160 }
161 }
162
163
pickNextNode(Node ** node,Node ** exch)164 static int pickNextNode(Node **node, Node **exch)
165 { // *exch on entry = parent node
166 Node *o = *node; // *exch on exit = picked next value node
167
168 if (o->L)
169 {
170 *exch = o;
171 int change = +pickNextNode(&o->L, exch);
172 if (change)
173 if (abs(o->B += change) > 1)
174 return balanceNode(node);
175 else
176 return o->B == 0;
177 else
178 return 0;
179 }
180
181 else if (o->R)
182 {
183 Node *q = o->R;
184 o->R = NULL;
185 (*exch)->L = q;
186 *exch = o;
187 return q->B == 0;
188 }
189
190 else
191 {
192 (*exch)->L = NULL;
193 *exch = o;
194 return 1;
195 }
196 }
197
198
199 // CAUTION: The following recursive functions must not be called with name == NULL.
200 // For performace reasons no extra error cheking is done.
201
findTreeNode(const char * name,Node * node)202 Node *findTreeNode(const char *name, Node *node)
203 {
204 if (node)
205 {
206 int ord = strcmp(name, node->name);
207
208 if (ord == 0)
209 return node;
210
211 else if (ord < 0)
212 return findTreeNode(name, node->L);
213
214 else // (ord > 0)
215 return findTreeNode(name, node->R);
216 }
217
218 else
219 return NULL;
220 }
221
addTreeNode(const char * name,ssize_t naml,Value * value,Node ** node,Node ** passed)222 int addTreeNode(const char *name, ssize_t naml, Value *value, Node **node, Node **passed)
223 {
224 static const Value zeros = {0, {.i = 0}};
225
226 Node *o = *node;
227
228 if (o == NULL) // if the hash/name is not in the tree
229 { // then add it into a new leaf
230 if (o = allocate(sizeof(Node), true))
231 if (o->name = allocate(naml+1, false))
232 {
233 strcpy(o->name, name);
234 o->naml = naml;
235 if (value)
236 o->value = *value;
237 *node = *passed = o; // report back the new node into which the new value has been entered
238 return 1; // add the weight of 1 leaf onto the balance
239 }
240 else
241 deallocate(VPR(o), false);
242
243 *passed = NULL;
244 return 0; // Out of Memory situation, nothing changed
245 }
246
247 else
248 {
249 int change;
250 int ord = strcmp(name, o->name);
251
252 if (ord == 0) // if the name is already in the tree then
253 {
254 releaseValue(&o->value); // release the old value - if kind is empty then releaseValue() does nothing
255 o->value = (value) ? *value // either store the new value or
256 : zeros; // zero-out the value struct
257 *passed = o; // report back the node in which the value was modified
258 return 0;
259 }
260
261 else if (ord < 0)
262 change = -addTreeNode(name, naml, value, &o->L, passed);
263
264 else // (ord > 0)
265 change = +addTreeNode(name, naml, value, &o->R, passed);
266
267 if (change)
268 if (abs(o->B += change) > 1)
269 return 1 - balanceNode(node);
270 else
271 return o->B != 0;
272 else
273 return 0;
274 }
275 }
276
removeTreeNode(const char * name,Node ** node)277 int removeTreeNode(const char *name, Node **node)
278 {
279 Node *o = *node;
280
281 if (o == NULL)
282 return 0; // not found -> recursively do nothing
283
284 else
285 {
286 int change;
287 int ord = strcmp(name, o->name);
288
289 if (ord == 0)
290 {
291 int b = o->B;
292 Node *p = o->L;
293 Node *q = o->R;
294
295 if (!p || !q)
296 {
297 releaseValue(&(*node)->value);
298 deallocate_batch(false, VPR((*node)->name),
299 VPR(*node), NULL);
300 *node = (p > q) ? p : q;
301 return 1; // remove the weight of 1 leaf from the balance
302 }
303
304 else
305 {
306 if (b == -1)
307 {
308 if (!p->R)
309 {
310 change = +1;
311 o = p;
312 o->R = q;
313 }
314 else
315 {
316 change = +pickPrevNode(&p, &o);
317 o->L = p;
318 o->R = q;
319 }
320 }
321
322 else
323 {
324 if (!q->L)
325 {
326 change = -1;
327 o = q;
328 o->L = p;
329 }
330 else
331 {
332 change = -pickNextNode(&q, &o);
333 o->L = p;
334 o->R = q;
335 }
336 }
337
338 o->B = b;
339 releaseValue(&(*node)->value);
340 deallocate_batch(false, VPR((*node)->name),
341 VPR(*node), NULL);
342 *node = o;
343 }
344 }
345
346 else if (ord < 0)
347 change = +removeTreeNode(name, &o->L);
348
349 else // (ord > 0)
350 change = -removeTreeNode(name, &o->R);
351
352 if (change)
353 if (abs(o->B += change) > 1)
354 return balanceNode(node);
355 else
356 return o->B == 0;
357 else
358 return 0;
359 }
360 }
361
releaseTree(Node * node)362 void releaseTree(Node *node)
363 {
364 if (node)
365 {
366 if (node->L)
367 releaseTree(node->L);
368 if (node->R)
369 releaseTree(node->R);
370
371 releaseValue(&node->value);
372 deallocate_batch(false, VPR(node->name),
373 VPR(node), NULL);
374 }
375 }
376
377
378 #pragma mark ••• Hash Table •••
379
380 // Essence of MurmurHash3_x86_32()
381 //
382 // Original at: https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp
383 //
384 // Quote from the Source:
385 // "MurmurHash3 was written by Austin Appleby, and is placed in the public
386 // domain. The author hereby disclaims copyright to this source code."
387 //
388 // Many thanks to Austin!
389
mmh3(const char * name,ssize_t naml)390 static inline uint mmh3(const char *name, ssize_t naml)
391 {
392 int i, n = (int)(naml/4);
393 uint k1, h1 = (uint)naml; // quite tiny (0.2 %) better distribution by seeding the name length
394 uint *quads = (uint *)(name + n*4);
395 uchar *tail = (uchar *)quads;
396
397 for (i = -n; i; i++)
398 {
399 k1 = quads[i];
400 k1 *= 0xCC9E2D51;
401 k1 = (k1<<15)|(k1>>17);
402 k1 *= 0x1B873593;
403
404 h1 ^= k1;
405 h1 = (h1<<13)|(h1>>19);
406 h1 = h1*5 + 0xE6546B64;
407 }
408
409 k1 = 0;
410 switch (naml & 3)
411 {
412 case 3: k1 ^= (uint)(tail[2] << 16);
413 case 2: k1 ^= (uint)(tail[1] << 8);
414 case 1: k1 ^= (uint)(tail[0]);
415 k1 *= 0xCC9E2D51;
416 k1 = (k1<<15)|(k1>>17);
417 k1 *= 0x1B873593;
418 h1 ^= k1;
419 };
420
421 h1 ^= naml;
422 h1 ^= h1 >> 16;
423 h1 *= 0x85EBCA6B;
424 h1 ^= h1 >> 13;
425 h1 *= 0xC2B2AE35;
426 h1 ^= h1 >> 16;
427
428 return h1;
429 }
430
431
432 // Table creation and release
createTable(uint n)433 Node **createTable(uint n)
434 {
435 Node **table = allocate((n+1)*sizeof(Node *), true);
436 if (table)
437 *(uint *)table = n;
438 return table;
439 }
440
releaseTable(Node * table[])441 void releaseTable(Node *table[])
442 {
443 if (table)
444 {
445 uint i, n = *(uint *)table;
446 for (i = 1; i <= n; i++)
447 releaseTree(table[i]);
448 deallocate(VPR(table), false);
449 }
450 }
451
452
453 // Storing and retrieving values by name
findName(Node * table[],const char * name,ssize_t naml)454 Node *findName(Node *table[], const char *name, ssize_t naml)
455 {
456 if (name && *name)
457 {
458 if (naml < 0)
459 naml = strvlen(name);
460 uint n = *(uint *)table;
461 return findTreeNode(name, table[mmh3(name, naml)%n + 1]);
462 }
463 else
464 return NULL;
465 }
466
storeName(Node * table[],const char * name,ssize_t naml,Value * value)467 Node *storeName(Node *table[], const char *name, ssize_t naml, Value *value)
468 {
469 if (name && *name)
470 {
471 if (naml < 0)
472 naml = strvlen(name);
473 uint n = *(uint *)table;
474 Node *passed;
475 addTreeNode(name, naml, value, &table[mmh3(name, naml)%n + 1], &passed);
476 return passed;
477 }
478 else
479 return NULL;
480 }
481
removeName(Node * table[],const char * name,ssize_t naml)482 void removeName(Node *table[], const char *name, ssize_t naml)
483 {
484 if (name && *name)
485 {
486 if (naml < 0)
487 naml = strvlen(name);
488 uint tidx = mmh3(name, naml) % *(uint*)table + 1;
489 Node *node = table[tidx];
490 if (node)
491 if (!node->L && !node->R)
492 {
493 releaseValue(&node->value);
494 deallocate_batch(false, VPR(node->name),
495 VPR(table[tidx]), NULL);
496 }
497 else
498 removeTreeNode(name, &table[tidx]);
499 }
500 }
501