home *** CD-ROM | disk | FTP | other *** search
/ Chip 1998 February / CHIP_2_98.iso / misc / src / install / hash.c < prev    next >
C/C++ Source or Header  |  1997-09-17  |  3KB  |  160 lines
  1. #include <stdlib.h>
  2. #include <unistd.h>
  3. #include <stdio.h>
  4. #include <string.h>
  5.  
  6. #include "hash.h"
  7.  
  8. #define CHUNK 4
  9.  
  10. struct bucket {
  11.     char **data;
  12.     int allocated;
  13.     int firstFree; /* as in data[firstFree] */
  14. };
  15.  
  16. struct hash_table {
  17.     int size;
  18.     int entries;
  19.     int totalData;
  20.     int overHead;
  21.     struct bucket *bucket;
  22. };
  23.  
  24. struct hash_table *htNewTable(int size)
  25. {
  26.     struct hash_table *res;
  27.     int i = 0;
  28.  
  29.     res = malloc(sizeof(struct hash_table));
  30.     res->bucket = malloc(sizeof(struct bucket) * size);
  31.     res->size = size;
  32.     res->totalData = 0;
  33.     res->entries = 0;
  34.     res->overHead = sizeof(struct bucket) * size + CHUNK * sizeof(char *);
  35.  
  36.     while (i < size) {
  37.     res->bucket[i].data = malloc(CHUNK * sizeof(char *));
  38.     res->bucket[i].allocated = CHUNK;
  39.     res->bucket[i].firstFree = 0;
  40.     i++;
  41.     }
  42.     
  43.     return res;
  44. }
  45.  
  46. void htFreeHashTable(struct hash_table *ht)
  47. {
  48.     while (ht->size--) {
  49.     free(ht->bucket[ht->size].data);
  50.     }
  51.     free(ht->bucket);
  52.     free(ht);
  53. }
  54.  
  55. void htHashStats(struct hash_table *t)
  56. {
  57.     int i = 0;
  58.     int empty = 0;
  59.  
  60.     while (i < t->size) {
  61.     if (t->bucket[i].firstFree != 0) {
  62.         /*printf("Bucket %d used %d\n", i, t->bucket[i].firstFree);*/
  63.     } else {
  64.         empty++;
  65.     }
  66.     i++;
  67.     }
  68.  
  69.     printf("Total Buckets : %d\n", t->size);
  70.     printf("Empty Buckets : %d\n", empty);
  71.     printf("Total Entries : %d\n", t->entries);
  72.     printf("Total Data    : %d\n", t->totalData);
  73.     printf("Total Overhead: %d\n", t->overHead);
  74.     printf("Avergage Depth: %f\n", (double)t->entries / (double)t->size);
  75. }
  76.  
  77. static unsigned int htHashString(char *s)
  78. {
  79.     unsigned int res = 0;
  80.  
  81.     while (*s)
  82.     res = ((res<<1) + (int)(*(s++)));
  83.  
  84.     return res;
  85. }
  86.  
  87. static char *in_table_aux(struct hash_table *t, int hash, char *s)
  88. {
  89.     int x;
  90.  
  91.     x = 0;
  92.     while (x < t->bucket[hash].firstFree) {
  93.     if (! strcmp(t->bucket[hash].data[x], s)) {
  94.         return t->bucket[hash].data[x];
  95.     }
  96.     x++;
  97.     }
  98.     
  99.     return NULL;
  100. }
  101.  
  102. char *htInTable(struct hash_table *t, char *s)
  103. {
  104.     int hash;
  105.  
  106.     hash = htHashString(s) % t->size;
  107.     return in_table_aux(t, hash, s);
  108. }
  109.  
  110. void htAddToTable(struct hash_table *t, char *s)
  111. {
  112.     int hash;
  113.  
  114.     hash = htHashString(s) % t->size;
  115.     if (in_table_aux(t, hash, s)) {
  116.     return;
  117.     }
  118.  
  119.     if (t->bucket[hash].firstFree == t->bucket[hash].allocated) {
  120.     t->bucket[hash].allocated += CHUNK;
  121.     t->bucket[hash].data =
  122.         realloc(t->bucket[hash].data,
  123.             t->bucket[hash].allocated * sizeof(char *));
  124.     /*printf("Bucket %d grew to %d\n", hash, t->bucket[hash].allocated);*/
  125.     t->overHead += sizeof(char *) * CHUNK;
  126.     }
  127.     /*printf("In bucket %d, item %d\n", hash, t->bucket[hash].firstFree);*/
  128.     t->bucket[hash].data[t->bucket[hash].firstFree++] = strdup(s);
  129.     t->totalData += strlen(s) + 1;
  130.     t->entries++;
  131. }
  132.  
  133. int htNumEntries(struct hash_table *t) {
  134.     return t->entries;
  135. }
  136.  
  137. void htIterStart(htIterator * iter) {
  138.     iter->bucket = 0;
  139.     iter->item = -1;
  140. }
  141.  
  142. int htIterGetNext(struct hash_table * t, htIterator * iter, char ** s) {
  143.     iter->item++;
  144.     
  145.     while (iter->bucket < t->size) {
  146.     if (iter->item < t->bucket[iter->bucket].firstFree) {
  147.         *s = t->bucket[iter->bucket].data[iter->item];
  148.         return 1;
  149.     }
  150.  
  151.     iter->item++;
  152.     if (iter->item >= t->bucket[iter->bucket].firstFree) {
  153.         iter->bucket++;
  154.         iter->item = 0;
  155.     }
  156.     }
  157.  
  158.     return 0;
  159. }
  160.