mega-sena/mod_lp.c

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include <stdlib.h>
   4
   5 #include "module.h"
   6 #include "mod_lp.h"
   7
   8 struct ohtbl {
   9         int positions;
  10         int size;
  11         void **table;
  12
  13         /* debug stuff */
  14         int gr_collision;
  15         int nr_collisions;
  16         int no_collisions;
  17 };
  18
  19 #define HASH_TABLE_SIZE 10240          /* 10k */
  20 #define NAME_LENGTH        17          /* bytes */
  21
  22 static struct ohtbl htable;
  23
  24 static inline unsigned int tdb_hash(char *name)
  25 {
  26         unsigned value; /* Used to compute the hash value.  */
  27         unsigned   i;   /* Used to cycle through random values. */
  28
  29         /* Set the initial value from the key size. */
  30         for (value = 0x238F13AF * strlen(name), i=0; name[i]; i++)
  31                 value = (value + (((unsigned char *)name)[i] << (i*5 % 24)));
  32
  33         return (1103515243 * value + 12345);
  34 }
  35
  36 static int ohtbl_init(void)
  37 {
  38         int i;
  39         const int positions = HASH_TABLE_SIZE;
  40
  41         htable.table = malloc(sizeof(void *) * positions);
  42         if (!htable.table)
  43                 return -1;
  44
  45         for (i = 0; i < positions; i++)
  46                 htable.table[i] = NULL;
  47
  48         htable.positions = positions;
  49         htable.gr_collision = -1;
  50         htable.size = htable.nr_collisions = htable.no_collisions = 0;
  51
  52         return 0;
  53 }
  54
  55 static void ohtbl_destroy(void)
  56 {
  57         int i;
  58
  59         for (i = 0; i < htable.positions; i++)
  60                 if (htable.table[i])
  61                         free(htable.table[i]);
  62
  63         free(htable.table);
  64 }
  65
  66 static int ohtbl_lookup(char *name, unsigned int *h)
  67 {
  68         int i;
  69         unsigned int hash;
  70
  71         hash = tdb_hash(name) % htable.positions;
  72
  73         for (i = 0; i < htable.positions; i++) {
  74                 if (htable.table[hash])
  75                         if (!memcmp(htable.table[hash], name, NAME_LENGTH)) {
  76                                 /* found */
  77                                 if (h)
  78                                         *h = hash;
  79                                 return 1;
  80                         }
  81
  82                 hash = (hash + 1) % htable.positions;
  83         }
  84
  85         /* Not found */
  86         return 0;
  87 }
  88
  89 static int ohtbl_insert(char *name)
  90 {
  91         int ret, i;
  92         unsigned int hash;
  93
  94         ret = ohtbl_lookup(name, NULL);
  95         if (ret) {
  96                 /* key already exists */
  97                 return 1;
  98         }
  99
 100         hash = tdb_hash(name) % htable.positions;
 101
 102         for (i = 0; i < htable.positions; i++) {
 103                 if (!htable.table[hash]) {
 104                         htable.table[hash] = (void *) name;
 105                         htable.size++;
 106
 107                         if (!i)
 108                                 htable.no_collisions++;
 109                         else if (i > htable.gr_collision)
 110                                 htable.gr_collision = i;
 111
 112                         return 0;
 113                 }
 114
 115                 htable.nr_collisions++;
 116                 hash = (hash + 1) % htable.positions;
 117         }
 118
 119         /* Table is full */
 120         return -1;
 121 }
 122
 123 static void ohtbl_stats(void)
 124 {
 125         float lfactor, probes;
 126         struct ohtbl *p = &htable;
 127
 128         lfactor = (float) p->size / p->positions;
 129         probes = 1 / (1 - lfactor);
 130
 131         printf("\n-> Hash table statistics\n");
 132         printf("Table size:      %4d\n", p->positions);
 133         printf(" o free:         %4d\n", p->positions - p->size);
 134         printf(" o in use:       %4d\n", p->size);
 135         printf("Perfect hashing: %4d\n", p->no_collisions);
 136         printf("Collisions:      %4d\n", p->nr_collisions);
 137         printf(" o nr keys:      %4d\n", p->size - p->no_collisions);
 138         printf(" o greater:      %4d\n", p->gr_collision + 1);
 139         printf("Load factor:     %4.2f\n", lfactor);
 140         printf("P. to probe:     %4.2f\n\n", probes);
 141 }
 142
 143 struct module lp_module = {
 144         .mod_name    = "Linear Probing hashing",
 145         .mod_init    = ohtbl_init,
 146         .mod_insert  = ohtbl_insert,
 147         .mod_lookup  = ohtbl_lookup,
 148         .mod_destroy = ohtbl_destroy,
 149         .mod_stats   = ohtbl_stats,
 150 };