1/*
2 * Copyright 2016, Data61
3 * Commonwealth Scientific and Industrial Research Organisation (CSIRO)
4 * ABN 41 687 119 230.
5 *
6 * This software may be distributed and modified according to the terms of
7 * the BSD 2-Clause license. Note that NO WARRANTY is provided.
8 * See "LICENSE_BSD2.txt" for details.
9 *
10 * @TAG(D61_BSD)
11 */
12
13#include <data_struct/cvector.h>
14#include <data_struct/chash.h>
15#include <assert.h>
16#include <errno.h>
17#include <stdio.h>
18
19// An algorithm proposed by Donald E. Knuth in The Art Of Computer Programming Volume 3, under the
20// topic of sorting and search chapter 6.4.
21// Src: http://www.partow.net/programming/hashfunctions/
22static unsigned int
23__DEKHash(char* str, unsigned int len)
24{
25   unsigned int hash = len;
26   unsigned int i    = 0;
27
28   for(i = 0; i < len; str++, i++)
29   {
30      hash = ((hash << 5) ^ (hash >> 27)) ^ (*str);
31   }
32   return hash;
33}
34
35static inline uint32_t
36chash_hash(uint32_t key, uint32_t md)
37{
38    char *s = ((char*)(&key));
39    size_t slen = sizeof(key);
40    return __DEKHash(s, slen) % md;
41}
42
43void
44chash_init(chash_t *t, size_t sz)
45{
46    assert(t);
47    t->table = malloc(sizeof(cvector_t) * sz);
48    assert(t->table);
49    t->tableSize = sz;
50    for (int i = 0; i < t->tableSize; i++) {
51        cvector_init(&t->table[i]);
52    }
53}
54
55void
56chash_release(chash_t *t)
57{
58    if (!t) {
59        return;
60    }
61    if (t->table) {
62        for (int i = 0; i < t->tableSize; i++) {
63            int c = cvector_count(&t->table[i]);
64            for (int j = 0; j < c; j++) {
65                chash_entry_t* entry = (chash_entry_t*) cvector_get(&t->table[i], j);
66                if (entry) {
67                    kfree(entry);
68                }
69            }
70            cvector_free(&t->table[i]);
71        }
72        free(t->table);
73    }
74    t->table = NULL;
75    t->tableSize = 0;
76}
77
78static chash_entry_t*
79chash_get_entry(chash_t *t, uint32_t h, uint32_t key, int *index)
80{
81    size_t c = cvector_count(&t->table[h]);
82    for (int i = 0; i < c; i++) {
83        chash_entry_t* entry = (chash_entry_t*) cvector_get(&t->table[h], i);
84        assert(entry);
85        if (entry->key == key) {
86            if (index != NULL) {
87                *index = i;
88            }
89            return entry;
90        }
91    }
92    return NULL;
93}
94
95chash_item_t
96chash_get(chash_t *t, uint32_t key)
97{
98    // This function does _NOT_ give ownership over to caller.
99    uint32_t h = chash_hash(key, t->tableSize);
100    assert (h >= 0 && h < t->tableSize);
101    chash_entry_t* entry = chash_get_entry(t, h, key, NULL);
102    if (entry) {
103        // Found existing entry.
104        return entry->item;
105    }
106    return NULL;
107}
108
109int
110chash_set(chash_t *t, uint32_t key, chash_item_t obj)
111{
112    uint32_t h = chash_hash(key, t->tableSize);
113    assert (h >= 0 && h < t->tableSize);
114
115    chash_entry_t* entry = chash_get_entry(t, h, key, NULL);
116    if (entry) {
117        // Found existing entry. Set existing entry to new obj.
118        entry->item = obj;
119        return 0;
120    }
121
122    // No previous entry found. Create a new entry.
123    entry = kmalloc(sizeof(chash_entry_t));
124    if (!entry) {
125        return -ENOMEM;
126    }
127    entry->key = key;
128    entry->item = obj;
129    cvector_add(&t->table[h], (cvector_item_t)entry);
130    return 0;
131}
132
133void
134chash_remove(chash_t *t, uint32_t key)
135{
136    uint32_t h = chash_hash(key, t->tableSize);
137    assert (h >= 0 && h < t->tableSize);
138    int index;
139    chash_entry_t* entry = chash_get_entry(t, h, key, &index);
140    if (entry) {
141        kfree(entry);
142        cvector_delete(&t->table[h], index);
143    }
144}
145
146int
147chash_find_free(chash_t *t, uint32_t rangeStart, uint32_t rangeEnd)
148{
149    for(int i = rangeStart; i < rangeEnd; i++) {
150        uint32_t h = chash_hash(i, t->tableSize);
151        chash_entry_t* entry = chash_get_entry(t, h, i, NULL);
152        if (!entry) return i;
153    }
154    return -1;
155}
156