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