1/* simple hash table 2 * --kkourt@cslab.ece.ntua.gr */ 3#include <stdio.h> 4#include <stdlib.h> 5 6#include "hash.h" 7 8hash_t *hash_init(unsigned int size) 9{ 10 hash_t *hash; 11 12 hash = malloc(sizeof(hash_t)); 13 hash->table = calloc(size, sizeof(hash_entry_t *)); 14 if (!hash || !hash->table){ 15 fprintf(stderr, "malloc failed\n"); 16 exit(1); 17 } 18 hash->size = size; 19 20 return hash; 21} 22 23void hash_print(hash_t *hash) 24{ 25 unsigned int i; 26 hash_entry_t *curr; 27 28 printf("hash:%p\n", hash); 29 printf("==============================\n"); 30 for (i = 0; i < hash->size; i++) { 31 printf("Bucket %d:", i); 32 for (curr = hash->table[i]; curr != NULL; curr = curr->next) 33 printf("[%lu] => %lu", curr->key, curr->val); 34 printf("\n"); 35 } 36 printf("==============================\n"); 37} 38 39void hash_destroy(hash_t *hash) 40{ 41 unsigned int i; 42 hash_entry_t *curr; 43 for (i = 0; i < hash->size; i++) { 44 for (curr = hash->table[i]; curr != NULL; ) { 45 curr = curr->next; 46 free(curr); 47 } 48 } 49 free(hash->table); 50 free(hash); 51} 52 53void hash_insert(hash_t *hash, unsigned long key, unsigned long val) 54{ 55 hash_entry_t *new_entry, *curr; 56 unsigned int bucket; 57 58 bucket = hash_fn(hash, key); 59 //Lookup 60 curr = hash->table[bucket]; 61 while (curr) { 62 /* found key */ 63 if (curr->key == key){ 64 curr->val = val; 65 return; 66 } 67 curr = curr->next; 68 } 69 70 /* key does not exist, allocate a new entry */ 71 new_entry = malloc(sizeof(hash_entry_t)); 72 new_entry->key = key; 73 new_entry->val = val; 74 75 /* put new entry, at the beggining of the bucket */ 76 new_entry->next = hash->table[bucket]; 77 hash->table[bucket] = new_entry; 78} 79 80unsigned long hash_lookup(hash_t *hash, unsigned long key) 81{ 82 unsigned int bucket; 83 hash_entry_t *curr; 84 85 bucket = hash_fn(hash,key); 86 curr = hash->table[bucket]; 87 for (;;){ 88 /* entry not found */ 89 if (curr == NULL) 90 return HASH_ENTRY_NOTFOUND; 91 92 /* entry found */ 93 if (curr->key == key) 94 break; 95 96 curr = curr->next; 97 } 98 return curr->val; 99 100} 101 102unsigned long hash_delete(hash_t *hash, unsigned long key) 103{ 104 unsigned int bucket; 105 hash_entry_t *curr, *prev; 106 unsigned long ret; 107 108 bucket = hash_fn(hash,key); 109 curr = hash->table[bucket]; 110 prev = curr; 111 for (;;){ 112 /* entry does not exist */ 113 if (curr == NULL) 114 return HASH_ENTRY_NOTFOUND; 115 116 /* found entry */ 117 if (curr->key == key) 118 break; 119 120 prev = curr; 121 curr = curr->next; 122 } 123 124 /* delete entry */ 125 ret = curr->val; 126 if (curr == hash->table[bucket]) 127 hash->table[bucket] = curr->next; 128 else 129 prev->next = curr->next; 130 free(curr); 131 return ret; 132} 133 134int hash_swap(hash_t *hash, unsigned long key1, unsigned long key2) 135{ 136 int bucket; 137 unsigned long tmp; 138 hash_entry_t *entry1, *entry2; 139 140 /* find first value */ 141 bucket = hash_fn(hash,key1); 142 entry1 = hash->table[bucket]; 143 for (;;){ 144 /* first entry not found */ 145 if (entry1 == NULL) 146 return -1; 147 148 /* first entry found */ 149 if (entry1->key == key1) 150 break; 151 152 entry1 = entry1->next; 153 } 154 155 /* find second value */ 156 bucket = hash_fn(hash,key2); 157 entry2 = hash->table[bucket]; 158 for (;;){ 159 /* first entry not found */ 160 if (entry2 == NULL) 161 return -1; 162 163 /* first entry found */ 164 if (entry2->key == key2) 165 break; 166 167 entry2 = entry2->next; 168 } 169 170 /* do the swap */ 171 tmp = entry1->val; 172 entry1->val = entry2->val; 173 entry2->val = tmp; 174 175 return 0; 176} 177