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 { 36 long hashsize; 37 struct hashtable *hashtable; 38 int i; 39 40 if (nr_elems <= 0) 41 return NULL; 42 for (hashsize = 2; hashsize < nr_elems; hashsize <<= 1) 43 continue; 44 45 hashtable = malloc(sizeof(struct hashtable)); 46 if (!hashtable) { 47 return NULL; 48 } 49 50 hashtable->entries = malloc(hashsize * sizeof(struct entries_list)); 51 if (!hashtable->entries) { 52 free(hashtable); 53 hashtable = NULL; 54 goto out; 55 } 56 57 hashtable->nr_elems = hashsize; 58 59 for (i = 0; i < hashsize; i++) 60 LIST_INIT(&hashtable->entries[i]); 61 62 out: 63 return hashtable; 64 } 65 66 int 67 _hash_destroy(struct hashtable *hashtable) 68 { 69 struct entries_list *tmp; 70 u_long hashmask = hashtable->nr_elems -1; 71 72 for (tmp = &hashtable->entries[0]; tmp <= &hashtable->entries[hashmask]; tmp++) { 73 if (!LIST_EMPTY(tmp)) 74 return -1; 75 } 76 free(hashtable->entries); 77 free(hashtable); 78 hashtable = NULL; 79 return 0; 80 } 81 82 void 83 _hash_insert(struct hashtable *hashtable, u_long key, void *value) 84 { 85 86 u_long hashmask = hashtable->nr_elems -1; 87 struct entries_list *list = 88 &hashtable->entries[key & hashmask]; 89 struct hashentry *new_entry = malloc(sizeof(struct hashentry)); 90 new_entry->value = value; 91 new_entry->key = key; 92 LIST_INSERT_HEAD(list, new_entry, entry_link); 93 } 94 95 void * 96 _hash_lookup(struct hashtable *hashtable, u_long key) 97 { 98 99 u_long hashmask = hashtable->nr_elems -1; 100 struct entries_list *list = 101 &hashtable->entries[key & hashmask]; 102 struct hashentry *tmp; 103 104 LIST_FOREACH(tmp, list, entry_link) { 105 if (tmp->key == key) { 106 return tmp->value; 107 } 108 } 109 110 return NULL; 111 } 112 113 void * 114 _hash_remove(struct hashtable *hashtable, u_long key) 115 { 116 117 void *value; 118 u_long hashmask = hashtable->nr_elems -1; 119 struct entries_list *list = 120 &hashtable->entries[key & hashmask]; 121 struct hashentry *tmp; 122 123 LIST_FOREACH(tmp, list, entry_link) { 124 if (tmp->key == key) 125 goto done; 126 } 127 128 return NULL; 129 130 done: 131 LIST_REMOVE(tmp, entry_link); 132 value = tmp->value; 133 free(tmp); 134 return value; 135 } 136 137 int 138 get_hash_size(int nr_elems) 139 { 140 long hashsize = 0; 141 142 for (hashsize = 2; hashsize < nr_elems; hashsize <<= 1) 143 continue; 144 145 return hashsize; 146 } 147