1/*
2 * This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
5 *
6 * Copyright 1997 - July 2008 CWI, August 2008 - 2019 MonetDB B.V.
7 */
8
9#include "monetdb_config.h"
10#include "sql_mem.h"
11#include "sql_hash.h"
12
13static unsigned int
14log_base2(unsigned int n)
15{
16 unsigned int l ;
17
18 for (l = 0; n; l++)
19 n >>= 1 ;
20 return l ;
21}
22
23
24sql_hash *
25hash_new(sql_allocator *sa, int size, fkeyvalue key)
26{
27 int i;
28 sql_hash *ht = SA_ZNEW(sa, sql_hash);
29
30 if (ht == NULL)
31 return NULL;
32 ht->sa = sa;
33 ht->size = (1<<log_base2(size-1));
34 ht->key = key;
35 ht->buckets = SA_NEW_ARRAY(sa, sql_hash_e*, ht->size);
36 for(i = 0; i < ht->size; i++)
37 ht->buckets[i] = NULL;
38 return ht;
39}
40
41sql_hash_e*
42hash_add(sql_hash *h, int key, void *value)
43{
44 sql_hash_e *e = SA_ZNEW(h->sa, sql_hash_e);
45
46 if (e == NULL)
47 return NULL;
48 e->chain = h->buckets[key&(h->size-1)];
49 h->buckets[key&(h->size-1)] = e;
50 e->key = key;
51 e->value = value;
52 return e;
53}
54
55void
56hash_del(sql_hash *h, int key, void *value)
57{
58 sql_hash_e *e = h->buckets[key&(h->size-1)], *p = NULL;
59
60 while (e && (e->key != key || e->value != value)) {
61 p = e;
62 e = e->chain;
63 }
64 if (e) {
65 if (p)
66 p->chain = e->chain;
67 else
68 h->buckets[key&(h->size-1)] = e->chain;
69 }
70}
71
72unsigned int
73hash_key(const char *k)
74{
75 unsigned int h = 0;
76
77 while (*k) {
78 h += *k;
79 h += (h << 10);
80 h ^= (h >> 6);
81 k++;
82 }
83 h += (h << 3);
84 h ^= (h >> 11);
85 h += (h << 15);
86 return h;
87}
88