aboutsummaryrefslogblamecommitdiff
path: root/6.5/hash.c
blob: cd9cf73c45dcf430e11edf611e4623e19ac9069f (plain) (tree) 
73526f5






























































5c032ac


















73526f5






































1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118






























































                                                                          

















                                                                   





































                                                        
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include "hash.h"

void nlfree(struct nlist *p);
uint32_t hash(char *s, uint32_t hashsize);
struct nlist *lookup(struct nlist *hashtab[], uint32_t hashsize, char *s);
void pnl(struct nlist *np);

uint32_t hash(char *s, uint32_t hashsize)
{
	uint32_t hashval;

	for (hashval = 0; *s != '\0'; ++s)
		hashval = *s + 31*hashval;

	return hashval % hashsize;
}

struct nlist *lookup(struct nlist *hashtab[], uint32_t hashsize, char *s)
{
	struct nlist *np;

	for (np = hashtab[hash(s, hashsize)]; np != NULL; np = np->next)
		if (!strcmp(s, np->name))
			return np;

	return NULL;
}

struct nlist *install(struct nlist *hashtab[], uint32_t hashsize,
		      char *name, char *defn)
{
	struct nlist *np;
	uint32_t hashval;

	if ((np = lookup(hashtab, hashsize, name)) == NULL) {
		np = (struct nlist *) malloc(sizeof(*np));
		if (np == NULL || (np->name = strdup(name)) == NULL) {
			nlfree(np);
			return NULL;
		}

		hashval = hash(name, hashsize);
		np->next = hashtab[hashval];
		hashtab[hashval] = np;
	} else {
		free(np->defn);
	}

	if ((np->defn = strdup(defn)) == NULL) {
		undef(hashtab, hashsize, name);
		return NULL;
	}

	return np;
}

void undef(struct nlist *hashtab[], uint32_t hashsize, char *name)
{
	struct nlist *np, *prev;
	uint32_t h;

	prev = NULL;
	h = hash(name, hashsize);
	for (np = hashtab[h]; np != NULL; prev = np, np = np->next)
		if (!strcmp(name, np->name))
			break;

	if (np != NULL) {
		if (prev == NULL)
			hashtab[h] = np->next;
		else
			prev->next = np->next;

		np->next = NULL;
		nlfree(np);
		return;
	}
}

void pnl(struct nlist *np)
{
	if (np != NULL) {
		pnl(np->next);
		printf("%10s %s\n", np->name, np->defn);
	}
}

void phashtab(struct nlist *hashtab[], int lim)
{
	int i;

	for (i = 0; i < lim; ++i)
		pnl(hashtab[i]);
}

void nlfree(struct nlist *p)
{
	if (p != NULL ) {
		nlfree(p->next);
		if (p->defn != NULL)
			free(p->defn);
		if (p->name != NULL)
			free(p->name);
		free(p);
	}
}

void hashfree(struct nlist *hashtab[], int lim)
{
	int i;

	for (i = 0; i < lim; ++i)
		nlfree(hashtab[i]);
}