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