Download code

Jump to: navigation, search

Back to Hash_table_(C)

Download for Windows: zip

Download for UNIX: zip, tar.gz, tar.bz2

hashtbl.h

 1 /* The authors of this work have released all rights to it and placed it
 2 in the public domain under the Creative Commons CC0 1.0 waiver
 3 (http://creativecommons.org/publicdomain/zero/1.0/).
 4 
 5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 
13 Retrieved from: http://en.literateprograms.org/Hash_table_(C)?oldid=19638
14 */
15 
16 #ifndef HASHTBL_H_INCLUDE_GUARD
17 #define HASHTBL_H_INCLUDE_GUARD
18 
19 #include<stdlib.h>
20 
21 typedef size_t hash_size;
22 
23 struct hashnode_s {
24 	char *key;
25 	void *data;
26 	struct hashnode_s *next;
27 };
28 
29 typedef struct hashtbl {
30 	hash_size size;
31 	struct hashnode_s **nodes;
32 	hash_size (*hashfunc)(const char *);
33 } HASHTBL;
34 
35 
36 HASHTBL *hashtbl_create(hash_size size, hash_size (*hashfunc)(const char *));
37 void hashtbl_destroy(HASHTBL *hashtbl);
38 int hashtbl_insert(HASHTBL *hashtbl, const char *key, void *data);
39 int hashtbl_remove(HASHTBL *hashtbl, const char *key);
40 void *hashtbl_get(HASHTBL *hashtbl, const char *key);
41 int hashtbl_resize(HASHTBL *hashtbl, hash_size size);
42 
43 #endif


hijacker
hijacker
hijacker
hijacker

hashtbl.c

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Hash_table_(C)?oldid=19638
 14 */
 15 
 16 #include"hashtbl.h"
 17 
 18 #include<string.h>
 19 #include<stdio.h>
 20 
 21 static char *mystrdup(const char *s)
 22 {
 23 	char *b;
 24 	if(!(b=malloc(strlen(s)+1))) return NULL;
 25 	strcpy(b, s);
 26 	return b;
 27 }
 28 
 29 static hash_size def_hashfunc(const char *key)
 30 {
 31 	hash_size hash=0;
 32 	
 33 	while(*key) hash+=(unsigned char)*key++;
 34 
 35 	return hash;
 36 }
 37 
 38 HASHTBL *hashtbl_create(hash_size size, hash_size (*hashfunc)(const char *))
 39 {
 40 	HASHTBL *hashtbl;
 41 
 42 	if(!(hashtbl=malloc(sizeof(HASHTBL)))) return NULL;
 43 
 44 	if(!(hashtbl->nodes=calloc(size, sizeof(struct hashnode_s*)))) {
 45 		free(hashtbl);
 46 		return NULL;
 47 	}
 48 
 49 	hashtbl->size=size;
 50 
 51 	if(hashfunc) hashtbl->hashfunc=hashfunc;
 52 	else hashtbl->hashfunc=def_hashfunc;
 53 
 54 	return hashtbl;
 55 }
 56 
 57 void hashtbl_destroy(HASHTBL *hashtbl)
 58 {
 59 	hash_size n;
 60 	struct hashnode_s *node, *oldnode;
 61 	
 62 	for(n=0; n<hashtbl->size; ++n) {
 63 		node=hashtbl->nodes[n];
 64 		while(node) {
 65 			free(node->key);
 66 			oldnode=node;
 67 			node=node->next;
 68 			free(oldnode);
 69 		}
 70 	}
 71 	free(hashtbl->nodes);
 72 	free(hashtbl);
 73 }
 74 
 75 int hashtbl_insert(HASHTBL *hashtbl, const char *key, void *data)
 76 {
 77 	struct hashnode_s *node;
 78 	hash_size hash=hashtbl->hashfunc(key)%hashtbl->size;
 79 
 80 /*	fprintf(stderr, "hashtbl_insert() key=%s, hash=%d, data=%s\n", key, hash, (char*)data);*/
 81 
 82 	node=hashtbl->nodes[hash];
 83 	while(node) {
 84 		if(!strcmp(node->key, key)) {
 85 			node->data=data;
 86 			return 0;
 87 		}
 88 		node=node->next;
 89 	}
 90 
 91 	if(!(node=malloc(sizeof(struct hashnode_s)))) return -1;
 92 	if(!(node->key=mystrdup(key))) {
 93 		free(node);
 94 		return -1;
 95 	}
 96 	node->data=data;
 97 	node->next=hashtbl->nodes[hash];
 98 	hashtbl->nodes[hash]=node;
 99 
100 	return 0;
101 }
102 
103 int hashtbl_remove(HASHTBL *hashtbl, const char *key)
104 {
105 	struct hashnode_s *node, *prevnode=NULL;
106 	hash_size hash=hashtbl->hashfunc(key)%hashtbl->size;
107 
108 	node=hashtbl->nodes[hash];
109 	while(node) {
110 		if(!strcmp(node->key, key)) {
111 			free(node->key);
112 			if(prevnode) prevnode->next=node->next;
113 			else hashtbl->nodes[hash]=node->next;
114 			free(node);
115 			return 0;
116 		}
117 		prevnode=node;
118 		node=node->next;
119 	}
120 
121 	return -1;
122 }
123 
124 void *hashtbl_get(HASHTBL *hashtbl, const char *key)
125 {
126 	struct hashnode_s *node;
127 	hash_size hash=hashtbl->hashfunc(key)%hashtbl->size;
128 
129 /*	fprintf(stderr, "hashtbl_get() key=%s, hash=%d\n", key, hash);*/
130 
131 	node=hashtbl->nodes[hash];
132 	while(node) {
133 		if(!strcmp(node->key, key)) return node->data;
134 		node=node->next;
135 	}
136 
137 	return NULL;
138 }
139 int hashtbl_resize(HASHTBL *hashtbl, hash_size size)
140 {
141 	HASHTBL newtbl;
142 	hash_size n;
143 	struct hashnode_s *node, *nextnode;
144 
145 	newtbl.size=size;
146 	newtbl.hashfunc=hashtbl->hashfunc;
147 
148 	if(!(newtbl.nodes=calloc(size, sizeof(struct hashnode_s*)))) return -1;
149 
150 	for(n=0; n<hashtbl->size; ++n) {
151 		for(node=hashtbl->nodes[n]; node; node=nextnode) {
152 			nextnode=node->next;
153 			hashtbl_insert(&newtbl, node->key, node->data);
154 			hashtbl_remove(hashtbl, node->key);
155 		}
156 	}
157 
158 	free(hashtbl->nodes);
159 	hashtbl->size=newtbl.size;
160 	hashtbl->nodes=newtbl.nodes;
161 
162 	return 0;
163 }


hijacker
hijacker
hijacker
hijacker

Makefile

# The authors of this work have released all rights to it and placed it
# in the public domain under the Creative Commons CC0 1.0 waiver
# (http://creativecommons.org/publicdomain/zero/1.0/).
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
# 
# Retrieved from: http://en.literateprograms.org/Hash_table_(C)?oldid=19638

all: hashtbl

hashtbl: hashtbl.o main.o
	cc -o hashtbl -Wall -pedantic -g hashtbl.o main.o

hashtbl.o: hashtbl.c hashtbl.h
	cc -o hashtbl.o -Wall -pedantic -g -c hashtbl.c

main.o: main.c hashtbl.h
	cc -o main.o -Wall -pedantic -g -c main.c


hijacker
hijacker
hijacker
hijacker

main.c

 1 /* The authors of this work have released all rights to it and placed it
 2 in the public domain under the Creative Commons CC0 1.0 waiver
 3 (http://creativecommons.org/publicdomain/zero/1.0/).
 4 
 5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 
13 Retrieved from: http://en.literateprograms.org/Hash_table_(C)?oldid=19638
14 */
15 
16 #include"hashtbl.h"
17 #include<stdio.h>
18 
19 int main()
20 {
21 	HASHTBL *hashtbl;
22 	char *spain, *italy;
23 
24 	if(!(hashtbl=hashtbl_create(16, NULL))) {
25 		fprintf(stderr, "ERROR: hashtbl_create() failed\n");
26 		exit(EXIT_FAILURE);
27 	}
28 
29 	hashtbl_insert(hashtbl, "France", "Paris");
30 	hashtbl_insert(hashtbl, "England", "London");
31 	hashtbl_insert(hashtbl, "Sweden", "Stockholm");
32 	hashtbl_insert(hashtbl, "Germany", "Berlin");
33 	hashtbl_insert(hashtbl, "Norway", "Oslo");
34 	hashtbl_insert(hashtbl, "Italy", "Rome");
35 	hashtbl_insert(hashtbl, "Spain", "Madrid");
36 	hashtbl_insert(hashtbl, "Estonia", "Tallinn");
37 	hashtbl_insert(hashtbl, "Netherlands", "Amsterdam");
38 	hashtbl_insert(hashtbl, "Ireland", "Dublin");
39 
40 	printf("After insert:\n");
41 	italy=hashtbl_get(hashtbl, "Italy");
42 	printf("Italy: %s\n", italy?italy:"-");
43 	spain=hashtbl_get(hashtbl, "Spain");
44 	printf("Spain: %s\n", spain?spain:"-");
45 
46 	hashtbl_remove(hashtbl, "Spain");
47 
48 	printf("After remove:\n");
49 	spain=hashtbl_get(hashtbl, "Spain");
50 	printf("Spain: %s\n", spain?spain:"-");
51 
52 	hashtbl_resize(hashtbl, 8);
53 
54 	printf("After resize:\n");
55 	italy=hashtbl_get(hashtbl, "Italy");
56 	printf("Italy: %s\n", italy?italy:"-");
57 
58 	hashtbl_destroy(hashtbl);
59 
60 	return 0;
61 }


hijacker
hijacker
hijacker
hijacker