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

struct Hash added.

Hash now encapsulates the table of Node pointers, the table size and
also function pointers to comparison function and a hash
function. This helps make hlookup() cleaner by having three less
parameters to pass.

Changeset 7150a30f8650

Parent e5c9d1bc0a66

by Rup Palchowdhury

Changes to 3 files · Browse files at 7150a30f8650 Showing diff from parent e5c9d1bc0a66 Diff from another changeset...

Change 1 of 2 Show Entire File khash.c Stacked
 
1
2
 
3
4
5
 
 
 
 
 
 
 
 
 
 
 
 
6
7
8
 
16
17
18
19
20
21
 
22
23
24
25
26
27
 
 
 
 
28
29
30
31
 
 
32
33
34
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
29
30
31
 
 
 
32
33
34
 
 
 
 
35
36
37
38
39
40
 
 
41
42
43
44
45
@@ -1,8 +1,21 @@
 #include <stdio.h>  #include <stdlib.h> +#include "kcommon.h"  #include "klist.h"  #include "khash.h"   +Hash *newhash(unsigned n, fn_cmp cmp, fn_hash hash) { + Hash *h; + h = (Hash *)malloc(sizeof(Hash)); + h->tab = (Node **)malloc(sizeof(Node *) * n); + for (int i = 0; i < n; i++) + h->tab[i] = NULL; + h->n = n; + h->cmp = cmp; + h->hash = hash; + return h; +} +  /* default hash function, assumes data to be char buffer */  unsigned hash(void *data, unsigned size)  { @@ -16,19 +29,17 @@
  return h % size;  }   -Node *hlookup(Node *htab[], Node *n, int create, - unsigned (*hash)(void*, unsigned), unsigned hsize, - int (*cmp)(void*, void*)) +Node *hlookup(Hash *h, Node *n, int create)  {   Node *np; - unsigned h; - h = (*hash)(n->data, hsize); - for (np = htab[h]; np != NULL; np = np->next) - if ((*cmp)(n->data, np->data) == 0) + unsigned m; + m = (*h->hash)(n->data, h->n); + for (np = h->tab[m]; np != NULL; np = np->next) + if ((*h->cmp)(n->data, np->data) == 0)   return np;   if (create == 1) { - htab[h] = addfront(htab[h], n); - return htab[h]; + h->tab[m] = addfront(h->tab[m], n); + return h->tab[m];   }   return NULL;  }
Change 1 of 1 Show Entire File khash.h Stacked
 
1
2
3
 
 
 
 
 
 
 
 
 
 
 
4
5
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
@@ -1,5 +1,13 @@
-Node *hlookup(Node *htab[], Node *n, int create, - unsigned (*hash)(void*, unsigned), unsigned hsize, - int (*cmp)(void*, void*)); +typedef struct Hash Hash; + +struct Hash { + Node **tab; + unsigned n; + fn_cmp cmp; + fn_hash hash; +}; + +Hash *newhash(unsigned, fn_cmp, fn_hash); +Node *hlookup(Hash*, Node*, int);  unsigned hash(void*, unsigned);  void hstats(Node *htab[], unsigned);
Change 1 of 4 Show Entire File test.c Stacked
 
1
 
2
3
4
 
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
 
78
79
80
81
 
82
83
84
 
101
102
103
 
104
105
106
 
1
2
3
4
5
 
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
 
71
72
73
 
74
75
76
77
 
94
95
96
97
98
99
100
@@ -1,4 +1,5 @@
 #include <stdio.h> +#include "kcommon.h"  #include "ktree.h"  #include "klist.h"  #include "khash.h" @@ -19,40 +20,32 @@
    /* hash table test */   - /*   const int NHASH = 3; - Node *htab[NHASH]; - for (i = 0; i < NHASH; i++) - htab[i] = NULL; + Hash *h;   + h = newhash(NHASH, &postcmp, &hash);   for (i = 0; i < 6; i++) - np = hlookup(htab, newnode(newpost(w[i], i)), 1, - hash, NHASH, postcmp); - + np = hlookup(h, newnode(newpost(w[i], i)), 1);   c = 0;   for (i = 0; i < NHASH; i++) { - if (htab[i] != NULL) { + if (h->tab[i] != NULL) {   c++;   printf("%-3d htab[%d]: ", c, i); - for (np = htab[i]; np != NULL; np = np->next) { + for (np = h->tab[i]; np != NULL; np = np->next) {   pp = (Post *)np->data;   printf("%s,%d ", pp->s, pp->f);   }   printf("\n");   }   } - - - np = hlookup(htab, newnode(newpost(w[0], 0)), 0, - hash, NHASH, postcmp); - + np = hlookup(h, newnode(newpost(w[0], 0)), 0);   if (np != NULL) {   pp = (Post *)np->data;   printf("Found: %s %d\n", pp->s, pp->f);   }   else   printf("Not found\n"); - */ +     /* tree test */   /* @@ -78,7 +71,7 @@
  */     /* list test */ - + /*   Node *lt, *n, *tmp;     n = newnode((void *)newpost(s[1], 1)); @@ -101,6 +94,7 @@
  printf("\n");     freelist(lt, NULL); + */     return 0;  }