Repositories » libk0
Clone URL:  
Pushed to one repository · View In Graph Contained in tip

Generalized the hash table interface.

Changeset 937fc39b5c64

Parent 801015b4c7b1

by Rup Palchowdhury

Changes to 3 files · Browse files at 937fc39b5c64 Showing diff from parent 801015b4c7b1 Diff from another changeset...

Change 1 of 1 Show Entire File khash.c Stacked
 
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
 
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
 
 
 
 
 
 
 
 
 
 
 
 
 
@@ -3,42 +3,30 @@
 #include "klist.h"  #include "khash.h"   -unsigned int hash(char *s, int modulo) +/* default hash function, assumes data to be char buffer */ +unsigned hash(void *data, unsigned size)  { - unsigned int h; - unsigned char *p; + static unsigned MULTIPLIER = 31; + unsigned h; + unsigned char *p, *s; + s = (unsigned char *)data;   h = 0;   for (p = (unsigned char *)s; *p != '\0'; p++)   h = MULTIPLIER * h + *p; - return h % modulo; + return h % size;  }    Node *hlookup(Node *htab[], Node *n, int create, - unsigned int (*hashdata)(unsigned int (*hash)(char*, int), - void*, int), - int modulo, - int (*nodecmp)(void*, void*)) + unsigned (*hash)(void*, unsigned), unsigned hsize, + int (*cmp)(void*, void*))  {   Node *i; - unsigned int h; - h = (*hashdata)(hash, n->data, modulo); + unsigned h; + h = (*hash)(n->data, hsize);   for (i = htab[h]; i != NULL; i = i->next) - if ((*nodecmp)(n->data, i->data) == 0) + if ((*cmp)(n->data, i->data) == 0)   return i;   if (create == 1)   htab[h] = addfront(htab[h], n);   return NULL;  } - -void printhtab(Node *htab[], int nhash, void (*printdata)(void*, void*)) -{ - int i; - for (i = 0; i < nhash; i++) { - if (htab[i] == NULL) { - printf(".\n"); - continue; - } - apply(htab[i], printdata, "%s:%1.0f "); - printf("\n"); - } -}
Change 1 of 1 Show Entire File khash.h Stacked
 
1
2
3
4
5
6
7
8
9
 
 
 
 
 
1
 
 
 
 
 
 
 
2
3
4
@@ -1,9 +1,4 @@
-enum {MULTIPLIER = 31};  Node *hlookup(Node *htab[], Node *n, int create, - unsigned int (*hashdata)(unsigned int (*hash)(char*, int), - void*, int), - int modulo, - int (*nodecmp)(void*, void*)); -unsigned int hash(char*, int); -void printhtab(Node *htab[], int nhash, void (*printdata)(void*, void*)); - + unsigned (*hash)(void*, unsigned), unsigned hsize, + int (*cmp)(void*, void*)); +unsigned hash(void*, unsigned);
Change 1 of 2 Show Entire File test.c Stacked
 
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
 
49
50
51
 
52
53
54
 
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
 
65
66
67
68
69
70
71
@@ -10,34 +10,50 @@
 {   char s[NUMNODES][10] = {"f", "b", "g", "a", "d",   "i", "c", "e", "h", "h"}; - int i; - Node *lt, *n, *tmp; + char w[6][4] = {"cat", "mat", "bat", "hat", "rat", "sat"}; + int i, c; + Node *lt, *n, *np;   TNode *t, *t_; + Post *pp;     /* hash table test */ - /* - const int NHASH = 5; + + const int NHASH = 3;   Node *htab[NHASH];   for (i = 0; i < NHASH; i++)   htab[i] = NULL;   - for (i = 0; i < 9; i++) { - tmp = hlookup(htab, newnode(newpost(s[i], i)), 1, - hashpost, NHASH, postcmp); + for (i = 0; i < 6; i++) + np = hlookup(htab, newnode(newpost(w[i], i)), 1, + hash, NHASH, postcmp); + + c = 0; + for (i = 0; i < NHASH; i++) { + if (htab[i] != NULL) { + c++; + printf("%-3d htab[%d]: ", c, i); + for (np = htab[i]; np != NULL; np = np->next) { + pp = (Post *)np->data; + printf("%s,%d ", pp->s, pp->f); + } + printf("\n"); + }   }   - printhtab(htab, NHASH, printpost); + /* + np = hlookup(htab, newnode(newpost(s[0], 0)), 0, + hash, NHASH, postcmp);   - tmp = hlookup(htab, newnode(newpost(s[0], 0)), 0, - hashpost, NHASH, postcmp); - - if (tmp != NULL) - printpost(tmp->data, "Found: %s %1.0f\n"); + if (np != NULL) { + pp = (Post *)np->data; + printf("Found: %s %d\n", pp->s, pp->f); + }   else   printf("Not found\n");   */     /* tree test */ + /*   TNode *found;   t = NULL;   for (i = 0; i < NUMNODES; i++) @@ -49,6 +65,7 @@
  found = nrtlookup(t, newtnode(newpost("h", 1)), postcmp);   if (found != NULL)   printpost(found->data, "nrtlookup: %s %d\n"); + */   /*   printf("inorder:\n");   applyinorder(t, printpost, "%s %d\n");