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

prettyprinting improved, interfaces cleaned.

Changeset 3485cdf86ef9

Parent e967d110a6c1

by Rup Palchowdhury

Changes to 6 files · Browse files at 3485cdf86ef9 Showing diff from parent e967d110a6c1 Diff from another changeset...

Change 1 of 2 Show Entire File khash.c Stacked
 
24
25
26
27
28
 
29
30
31
32
33
34
35
 
36
37
38
 
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
 
24
25
26
 
 
27
28
29
30
 
 
31
 
32
33
34
35
 
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
@@ -24,15 +24,12 @@
  free(h);  }   -/* default hash function, assumes data to be char buffer */ -unsigned hash(void *data, unsigned size) +unsigned strhash(void *data, unsigned size)  {   static unsigned MULTIPLIER = 31;   unsigned h; - unsigned char *s; - s = (unsigned char *)data;   h = 0; - for (unsigned char *p = (unsigned char *)s; *p != '\0'; p++) + for (unsigned char *p = data; *p != '\0'; p++)   h = MULTIPLIER * h + *p;   return h % size;  } @@ -53,37 +50,37 @@
  return NULL;  }   -void hstats(Hash *h, unsigned size) +void fprinthashstats(FILE *stream, Hash *h)  { - float free, avglen; - int c, maxlen, chainlen; - Node *np; - c = maxlen = 0; - for (int i = 0; i < size; i++) { - if (h->tab[i] != NULL) { - c++; - chainlen = 0; - for (np = h->tab[i]; np != NULL; np = np->next) - chainlen++; - if (chainlen > maxlen) maxlen = chainlen; - } + float unused, avg; + int c, max, chain; + c = max = 0; + for (int i = 0; i < h->n; i++) { + if (h->tab[i] == NULL) + continue; + c++; + chain = 0; + for (Node *np = h->tab[i]; np != NULL; np = np->next) + chain++; + if (chain > max) max = chain;   }   - free = (float)(size - c) / (float)size * 100; - avglen = (float)h->nel / (float)c; - fprintf(stderr, "free space: %5.1f%% (%d/%d)\n", free, size - c, size); - fprintf(stderr, "#elements: %d\n", h->nel); - fprintf(stderr, "chain length (max/avg): %5.1f/%d\n", avglen, maxlen); + unused = (float)(h->n - c) / (float)h->n; + avg = (float)h->nel / (float)c; + fprintf(stream, "unused : %-4.2f (%d/%d)\n", unused, h->n - c, h->n); + fprintf(stream, "elements : %-d\n", h->nel); + fprintf(stream, "chain avg: %-5.1f\n", avg); + fprintf(stream, "chain max: %-d\n", max);  }   -void printhash(Hash *h, void (*printdata)(void*)) +void fprinthash(FILE *stream, Hash *h, void (*printdata)(FILE*, void*))  {   for (int i = 0; i < h->n; i++) { - fprintf(stderr, "[%d] ", i);   for (Node *np = h->tab[i]; np != NULL; np = np->next) { - printdata(np->data); - fprintf(stderr, " "); + fprintf(stream, "%d ", i); + (*printdata)(stream, np->data); + fprintf(stream, " ");   } - fprintf(stderr, "\n"); + fprintf(stream, "\n");   }  }
Change 1 of 1 Show Entire File khash.h Stacked
 
10
11
12
13
14
 
 
 
 
10
11
12
 
 
13
14
15
@@ -10,5 +10,6 @@
 Hash *newhash(unsigned, fn_cmp, fn_hash);  void freehash(Hash*, void (*freedata)(void*));  Node *hlookup(Hash*, Node*, int); -unsigned hash(void*, unsigned); -void hstats(Hash*, unsigned); +unsigned strhash(void*, unsigned); +void fprinthashstats(FILE*, Hash*); +void fprinthash(FILE*, Hash*, void (*printdata)(FILE*, void*));
Change 1 of 1 Show Entire File klist.c Stacked
 
72
73
74
75
 
76
77
78
 
72
73
74
 
75
76
77
78
@@ -72,7 +72,7 @@
  }   prev = i;   } - printf("delnode: matching node not found"); + fprintf(stderr, "delnode: matching node not found");   return NULL;  }  
Change 1 of 2 Show Entire File kpost.c Stacked
 
12
13
14
15
 
16
17
18
 
28
29
30
31
 
32
33
34
35
 
36
37
38
 
39
40
 
 
 
 
 
 
41
 
12
13
14
 
15
16
17
18
 
28
29
30
 
31
32
 
 
 
33
34
35
 
36
37
 
38
39
40
41
42
43
44
@@ -12,7 +12,7 @@
  return t;  }   -int kpostcmp(void *t, void *t1) +int cmpkpost(void *t, void *t1)  {   return strcmp(((KPost *)t)->s, ((KPost *)t1)->s);  } @@ -28,14 +28,17 @@
  free(t);  }   -void printkpost(void *d, void *arg) +void fprintkpost(FILE *stream, void *d)  { - char *fmt; - fmt = (char *)arg; - printf(fmt, ((KPost *)d)->s, ((KPost *)d)->f); + fprintf(stream, "%s:%d", ((KPost *)d)->s, ((KPost *)d)->f);  }   -unsigned int hashkpost(unsigned int (*fn)(char*, int), void *data, int modulo) +unsigned hashkpost(void *data, unsigned size)  { - return (*fn)(((KPost *)data)->s, modulo); + static unsigned MULTIPLIER = 31; + unsigned h; + h = 0; + for (char *p = ((KPost *)data)->s; *p != '\0'; p++) + h = MULTIPLIER * h + *p; + return h % size;  }
Change 1 of 1 Show Entire File kpost.h Stacked
 
6
7
8
9
 
10
11
12
13
 
 
 
6
7
8
 
9
10
11
 
 
12
13
@@ -6,8 +6,8 @@
 };    KPost *newkpost(char*, int); -int kpostcmp(void*, void*); +int cmpkpost(void*, void*);  int kpost_match_handler(void*, void*);  void freekpost(void*); -void printkpost(void*, void*); -unsigned int hashkpost(unsigned int (*fn)(char*, int), void*, int); +void fprintkpost(FILE*, void*); +unsigned int hashkpost(void*, unsigned);
Change 1 of 1 Show Entire File test.c Stacked
 
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
 
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
@@ -17,39 +17,27 @@
    int i, c;   Node *np; - KPost *pp;     /* hash table test */     const int NHASH = 3;   Hash *h;   - h = newhash(NHASH, &kpostcmp, &hash); + h = newhash(NHASH, cmpkpost, hashkpost);   for (i = 0; i < 6; i++)   np = hlookup(h, newnode(newkpost(w[i], i)), 1);   c = 0; - for (i = 0; i < NHASH; i++) { - if (h->tab[i] != NULL) { - c++; - printf("%-3d htab[%d]: ", c, i); - for (np = h->tab[i]; np != NULL; np = np->next) { - pp = (KPost *)np->data; - printf("%s,%d ", pp->s, pp->f); - } - printf("\n"); - } - }   - hstats(h, NHASH); + fprinthash(stdout, h, fprintkpost); + fprinthashstats(stdout, h);     np = hlookup(h, newnode(newkpost(w[3], 0)), 0); - if (np != NULL) { - pp = (KPost *)(np->data); - printf("Found: %s %d\n", pp->s, pp->f); - } + if (np != NULL) + fprintf(stdout, "Found: ");   else - printf("Not found\n"); - + printf("Not found: "); + fprintkpost(stdout, np->data); + fprintf(stdout, "\n");   freehash(h, free);     /* tree test */