mega-sena/old/megasena-stats-lp.c

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include <stdlib.h>
   4 #include <unistd.h>
   5 #include <fcntl.h>
   6 #include <errno.h>
   7 #include <limits.h>
   8 #include <signal.h>
   9 #include <sys/types.h>
  10 #include <sys/stat.h>
  11
  12 struct ohtbl {
  13         int positions;
  14         int size;
  15         void **table;
  16
  17         /* debug stuff */
  18         int gr_collision;
  19         int nr_collisions;
  20         int no_collisions;
  21 };
  22
  23 #define HASH_TABLE_SIZE 10240          /* 10k */
  24 #define LOTTERY_MAX         6          /* bytes */
  25 #define NAME_LENGTH        17          /* bytes */
  26
  27 static sig_atomic_t show_status, reload_table;
  28 static unsigned long nr_runs, nr_found, ulong_max;
  29
  30 static void sig_handler(int signum)
  31 {
  32         switch (signum) {
  33         case SIGUSR1:
  34                 show_status = 1;
  35                 break;
  36         case SIGHUP:
  37                 reload_table = 1;
  38                 break;
  39         }
  40 }
  41
  42 static inline unsigned int tdb_hash(char *name)
  43 {
  44         unsigned value; /* Used to compute the hash value.  */
  45         unsigned   i;   /* Used to cycle through random values. */
  46
  47         /* Set the initial value from the key size. */
  48         for (value = 0x238F13AF * strlen(name), i=0; name[i]; i++)
  49                 value = (value + (((unsigned char *)name)[i] << (i*5 % 24)));
  50
  51         return (1103515243 * value + 12345);
  52 }
  53
  54 static int ohtbl_init(struct ohtbl *p, int positions)
  55 {
  56         int i;
  57
  58         p->table = malloc(sizeof(void *) * positions);
  59         if (!p->table)
  60                 return -1;
  61
  62         for (i = 0; i < positions; i++)
  63                 p->table[i] = NULL;
  64
  65         p->positions = positions;
  66         p->gr_collision = -1;
  67         p->size = p->nr_collisions = p->no_collisions = 0;
  68
  69         return 0;
  70 }
  71
  72 static void ohtbl_destroy(struct ohtbl *p)
  73 {
  74         int i;
  75
  76         for (i = 0; i < p->positions; i++)
  77                 if (p->table[i])
  78                         free(p->table[i]);
  79
  80         free(p->table);
  81 }
  82
  83 static int ohtbl_lookup(struct ohtbl *p, char *name, unsigned int *h)
  84 {
  85         int i;
  86         unsigned int hash;
  87
  88         hash = tdb_hash(name) % p->positions;
  89
  90         for (i = 0; i < p->positions; i++) {
  91                 if (p->table[hash])
  92                         if (!memcmp(p->table[hash], name, NAME_LENGTH)) {
  93                                 /* found */
  94                                 if (h)
  95                                         *h = hash;
  96                                 return 1;
  97                         }
  98
  99                 hash = (hash + 1) % p->positions;
 100         }
 101
 102         /* Not found */
 103         return 0;
 104 }
 105
 106 static int ohtbl_insert(struct ohtbl *p, char *name)
 107 {
 108         int ret, i;
 109         unsigned int hash;
 110
 111         ret = ohtbl_lookup(p, name, NULL);
 112         if (ret) {
 113                 /* key already exists */
 114                 return 1;
 115         }
 116
 117         hash = tdb_hash(name) % p->positions;
 118
 119         for (i = 0; i < p->positions; i++) {
 120                 if (!p->table[hash]) {
 121                         p->table[hash] = (void *) name;
 122                         p->size++;
 123
 124                         if (!i)
 125                                 p->no_collisions++;
 126                         else if (i > p->gr_collision)
 127                                 p->gr_collision = i;
 128
 129                         return 0;
 130                 }
 131
 132                 p->nr_collisions++;
 133                 hash = (hash + 1) % p->positions;
 134         }
 135
 136         /* Table is full */
 137         return -1;
 138 }
 139
 140 static void ohtbl_show_stats(struct ohtbl *p)
 141 {
 142         float lfactor, probes;
 143
 144         lfactor = (float) p->size / p->positions;
 145         probes = 1 / (1 - lfactor);
 146
 147         printf("\n-> Hash table statistics\n");
 148         printf("Table size:      %4d\n", p->positions);
 149         printf(" o free:         %4d\n", p->positions - p->size);
 150         printf(" o in use:       %4d\n", p->size);
 151         printf("Perfect hashing: %4d\n", p->no_collisions);
 152         printf("Collisions:      %4d\n", p->nr_collisions);
 153         printf(" o nr keys:      %4d\n", p->size - p->no_collisions);
 154         printf(" o greater:      %4d\n", p->gr_collision + 1);
 155         printf("Load factor:     %4.2f\n", lfactor);
 156         printf("P. to probe:     %4.2f\n\n", probes);
 157 }
 158
 159 static int ohtbl_load_data_file(struct ohtbl *table, const char *fname)
 160 {
 161         FILE *file;
 162         char line[24];
 163
 164         file = fopen(fname, "r");
 165         if (!file)
 166                 return -1;
 167
 168         memset(line, 0, sizeof(line));
 169
 170         while (fgets(line, sizeof(line), file) != NULL) {
 171                 int err;
 172                 char *p;
 173
 174                 if (line[0] == '#') {
 175                         if (!strchr(line, '\n')) {
 176                                 int c;
 177
 178                                 while ((c = getc(file)) != '\n')
 179                                         /* NOTHING */;
 180                         }
 181                         memset(line, 0, sizeof(line));
 182                         continue;
 183                 }
 184
 185                 p = strchr(line, '\n');
 186                 if (p)
 187                         *p = '\0';
 188
 189                 p = strdup(line);
 190                 if (!p) {
 191                         fclose(file);
 192                         return -1;
 193                 }
 194
 195                 err = ohtbl_insert(table, p);
 196                 if (err) {
 197                         free(p);
 198                         if (err == -1) {
 199                                 fclose(file);
 200                                 return -1;
 201                         }
 202                         /* else key already exists */
 203                 }
 204                 memset(line, 0, sizeof(line));
 205         }
 206
 207         fclose(file);
 208         return 0;
 209 }
 210
 211 static int set_seed(void)
 212 {
 213         int fd, ret;
 214         size_t bytes;
 215         unsigned int seed;
 216
 217         fd = open("/dev/random", O_RDONLY);
 218         if (fd < 0)
 219                 return -1;
 220
 221         bytes = read(fd, &seed, sizeof(seed));
 222         if (bytes != sizeof(seed)) {
 223                 ret = -1;
 224                 goto out;
 225         }
 226
 227         ret = 0;
 228         srand(seed);
 229         printf("\n-> Seed: %#X\n", seed);
 230
 231 out:
 232         close(fd);
 233         return ret;
 234 }
 235
 236 static void lottery(char *result, size_t size)
 237 {
 238         int num, i, j;
 239         int numbers[LOTTERY_MAX];
 240
 241         memset(result, 0, size);
 242         memset(numbers, -1, sizeof(numbers));
 243
 244         for (i = 0; i < LOTTERY_MAX; i++) {
 245                 for (;;) {
 246                         int found = 0;
 247
 248                         num = 1 + (int) (60.0 * (rand() / (RAND_MAX + 6.0)));
 249
 250                         for (j = 0; j < i; j++)
 251                                 if (numbers[j] == num) {
 252                                         found = 1;
 253                                         break;
 254                                 }
 255
 256                         if (!found) {
 257                                 numbers[i] = num;
 258                                 break;
 259                         }
 260                 }
 261         }
 262
 263         snprintf(result, size, "%02d %02d %02d %02d %02d %02d",
 264                 numbers[0], numbers[1], numbers[2],
 265                 numbers[3], numbers[4], numbers[5]);
 266 }
 267
 268 static void show_pid(void)
 269 {
 270         printf("-> PID: %d\n\n", getpid());
 271 }
 272
 273 int main(int argc, char *argv[])
 274 {
 275         int ret;
 276         char result[24];
 277         unsigned int hash;
 278         struct ohtbl table;
 279
 280         if (argc != 2) {
 281                 printf("usage: %s < data-file >\n", argv[0]);
 282                 exit(1);
 283         }
 284
 285         setlinebuf(stdout);
 286
 287         ret = ohtbl_init(&table, HASH_TABLE_SIZE);
 288         if (ret) {
 289                 perror("ohtabl_init()");
 290                 ret = 1;
 291                 goto out;
 292         }
 293
 294         ret = ohtbl_load_data_file(&table, argv[1]);
 295         if (ret) {
 296                 perror("ohtbl_load_data_file()");
 297                 ret = 1;
 298                 goto out;
 299         }
 300
 301         ohtbl_show_stats(&table);
 302
 303         ret = set_seed();
 304         if (ret) {
 305                 perror("set_seed()");
 306                 ret = 1;
 307                 goto out;
 308         }
 309
 310         show_pid();
 311
 312         signal(SIGUSR1, sig_handler);
 313         signal(SIGHUP, sig_handler);
 314
 315         for (;;) {
 316
 317                 /*
 318                  * The following checks will probably make the program
 319                  * run slower, but I've implemented them because they're
 320                  * cool features (specially the reload table one).
 321                  *
 322                  * If you want full speed you should consider measuring
 323                  * this thing and removing these features if needed.
 324                  */
 325
 326                 if (show_status) {
 327                         printf("-> Ran %lu (* %lu) times with %lu matches\n",
 328                                nr_runs, ulong_max, nr_found);
 329                         show_status = 0;
 330                 }
 331
 332                 if (reload_table) {
 333                         /*
 334                          * XXX: Reading all the file again isn't a smart
 335                          * way to do this, we could start reading from
 336                          * the last line read.
 337                          */
 338                         ret = ohtbl_load_data_file(&table, argv[1]);
 339                         if (ret) {
 340                                 perror("ohtbl_load_data_file()");
 341                                 fprintf(stderr, "Aborting reload\n");
 342                         }
 343                         ohtbl_show_stats(&table);
 344                         reload_table = 0;
 345                 }
 346
 347                 lottery(result, sizeof(result));
 348
 349                 ret = ohtbl_lookup(&table, result, &hash);
 350                 if (ret) {
 351                         printf("-> HIT in run %lu: [%d] %s\n",
 352                                nr_runs, hash, result);
 353                         nr_found++;
 354                 }
 355
 356                 if (++nr_runs == ULONG_MAX) {
 357                         if (++ulong_max == ULONG_MAX) {
 358                                 printf("-> ulong_max blew up [%lu]\n",
 359                                        ulong_max);
 360                                 ulong_max = 0;
 361                         }
 362                         nr_runs = 0;
 363                 }
 364         }
 365
 366 out:
 367         ohtbl_destroy(&table);
 368         return ret;
 369 }