home *** CD-ROM | disk | FTP | other *** search
/ CD Actual 13 / CDA13.ISO / MISC / SRC / UPGRADE / HASH.C next >
Encoding:
C/C++ Source or Header  |  1996-07-28  |  2.1 KB  |  103 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 hash_table *new_table(int size)
  11. {
  12.     struct hash_table *res;
  13.     int i = 0;
  14.  
  15.     res = malloc(sizeof(struct hash_table));
  16.     res->bucket = malloc(sizeof(struct bucket) * size);
  17.     res->size = size;
  18.  
  19.     while (i < size) {
  20.     res->bucket[i].data = malloc(CHUNK * sizeof(char *));
  21.     res->bucket[i].allocated = CHUNK;
  22.     res->bucket[i].firstFree = 0;
  23.     i++;
  24.     }
  25.     
  26.     return res;
  27. }
  28.  
  29. void hash_stats(struct hash_table *t)
  30. {
  31.     int i = 0;
  32.     int entries = 0;
  33.     int empty = 0;
  34.  
  35.     while (i < t->size) {
  36.     if (t->bucket[i].firstFree != 0) {
  37.         /*printf("Bucket %d used %d\n", i, t->bucket[i].firstFree);*/
  38.         entries += t->bucket[i].firstFree;
  39.     } else {
  40.         empty++;
  41.     }
  42.     i++;
  43.     }
  44.  
  45.     printf("Total Buckets : %d\n", t->size);
  46.     printf("Empty Buckets : %d\n", empty);
  47.     printf("Total Entries : %d\n", entries);
  48.     printf("Avergage Depth: %f\n", (double)entries / (double)t->size);
  49. }
  50.  
  51. unsigned int hash_string(char *s)
  52. {
  53.     unsigned int res = 0;
  54.  
  55.     while (*s)
  56.     res = ((res<<1) + (int)(*(s++)));
  57.  
  58.     return res;
  59. }
  60.  
  61. char *in_table_aux(struct hash_table *t, int hash, char *s)
  62. {
  63.     int x;
  64.  
  65.     x = 0;
  66.     while (x < t->bucket[hash].firstFree) {
  67.     if (! strcmp(t->bucket[hash].data[x], s)) {
  68.         return t->bucket[hash].data[x];
  69.     }
  70.     x++;
  71.     }
  72.     
  73.     return NULL;
  74. }
  75.  
  76. char *in_table(struct hash_table *t, char *s)
  77. {
  78.     int hash;
  79.  
  80.     hash = hash_string(s) % t->size;
  81.     return in_table_aux(t, hash, s);
  82. }
  83.  
  84. void add_to_table(struct hash_table *t, char *s)
  85. {
  86.     int hash;
  87.  
  88.     hash = hash_string(s) % t->size;
  89.     if (in_table_aux(t, hash, s)) {
  90.     return;
  91.     }
  92.  
  93.     if (t->bucket[hash].firstFree == t->bucket[hash].allocated) {
  94.     t->bucket[hash].allocated += CHUNK;
  95.     t->bucket[hash].data =
  96.         realloc(t->bucket[hash].data,
  97.             t->bucket[hash].allocated * sizeof(char *));
  98.     /*printf("Bucket %d grew to %d\n", hash, t->bucket[hash].allocated);*/
  99.     }
  100.     /*printf("Adding to bucket %d, item %d\n", hash, t->bucket[hash].firstFree); */
  101.     t->bucket[hash].data[t->bucket[hash].firstFree++] = strdup(s);
  102. }
  103.