1 /*- 2 * Copyright (c) 2013 Larisa Grigore<larisagrigore@gmail.com> 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24 * SUCH DAMAGE. 25 */ 26 27 #include <stdlib.h> 28 #include <stdio.h> 29 #include <errno.h> 30 31 #include "sysvipc_hash.h" 32 33 struct hashtable * 34 _hash_init(int nr_elems) { 35 long hashsize; 36 struct hashtable *hashtable; 37 int i; 38 39 if (nr_elems <= 0) 40 return NULL; 41 for (hashsize = 2; hashsize < nr_elems; hashsize <<= 1) 42 continue; 43 44 hashtable = malloc(sizeof(struct hashtable)); 45 if (!hashtable) { 46 return NULL; 47 } 48 49 hashtable->entries = malloc(hashsize * sizeof(struct entries_list)); 50 if (!hashtable->entries) { 51 free(hashtable); 52 hashtable = NULL; 53 goto out; 54 } 55 56 hashtable->nr_elems = hashsize; 57 58 for (i = 0; i < hashsize; i++) 59 LIST_INIT(&hashtable->entries[i]); 60 61 out: 62 return hashtable; 63 } 64 65 int 66 _hash_destroy(struct hashtable *hashtable) { 67 struct entries_list *tmp; 68 u_long hashmask = hashtable->nr_elems -1; 69 70 for (tmp = &hashtable->entries[0]; tmp <= &hashtable->entries[hashmask]; tmp++) { 71 if (!LIST_EMPTY(tmp)) 72 return -1; 73 } 74 free(hashtable->entries); 75 free(hashtable); 76 hashtable = NULL; 77 return 0; 78 } 79 80 void 81 _hash_insert(struct hashtable *hashtable, 82 u_long key, 83 void *value) { 84 85 u_long hashmask = hashtable->nr_elems -1; 86 struct entries_list *list = 87 &hashtable->entries[key & hashmask]; 88 struct hashentry *new_entry = malloc(sizeof(struct hashentry)); 89 new_entry->value = value; 90 new_entry->key = key; 91 LIST_INSERT_HEAD(list, new_entry, entry_link); 92 } 93 94 void * 95 _hash_lookup(struct hashtable *hashtable, u_long key) { 96 97 u_long hashmask = hashtable->nr_elems -1; 98 struct entries_list *list = 99 &hashtable->entries[key & hashmask]; 100 struct hashentry *tmp; 101 102 LIST_FOREACH(tmp, list, entry_link) { 103 if (tmp->key == key) { 104 return tmp->value; 105 } 106 } 107 108 return NULL; 109 } 110 111 void * 112 _hash_remove(struct hashtable *hashtable, 113 u_long key) { 114 115 void *value; 116 u_long hashmask = hashtable->nr_elems -1; 117 struct entries_list *list = 118 &hashtable->entries[key & hashmask]; 119 struct hashentry *tmp; 120 121 LIST_FOREACH(tmp, list, entry_link) { 122 if (tmp->key == key) 123 goto done; 124 } 125 126 return NULL; 127 128 done: 129 LIST_REMOVE(tmp, entry_link); 130 value = tmp->value; 131 free(tmp); 132 return value; 133 } 134 135 int 136 get_hash_size(int nr_elems) { 137 long hashsize = 0; 138 139 for (hashsize = 2; hashsize < nr_elems; hashsize <<= 1) 140 continue; 141 142 return hashsize; 143 } 144