?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Introduce pet-projects dir
[lcapit-junk-code.git] / mega-sena / old / megasena-stats-ck.c
blob0c0f6728d47635521ea33ed4d8283ad8e9e9cf65
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 cuckoo_array {
13 void **array;
14 unsigned int size;
15 };
16
17 struct cuckoo_tbl {
18 int size;
19 unsigned int positions;
20 struct cuckoo_array first, second;
21 };
22
23 #define HASH_TABLE_SIZE 3072 /* 3k */
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 inline unsigned int joaat_hash(char *name)
55 {
56 int i;
57 unsigned int hash = 0;
58
59 for (i = 0; i < (int) strlen(name); i++) {
60 hash += name[i];
61 hash += (hash << 10);
62 hash ^= (hash >> 6);
63 }
64
65 hash += (hash << 3);
66 hash ^= (hash >> 11);
67 hash += (hash << 15);
68
69 return hash;
70 }
71
72 static int cuckoo_init(struct cuckoo_tbl *tbl, unsigned int positions)
73 {
74 unsigned int i;
75
76 tbl->first.array = malloc(sizeof(void *) * positions);
77 if (!tbl->first.array)
78 return -1;
79
80 tbl->second.array = malloc(sizeof(void *) * positions);
81 if (!tbl->second.array) {
82 free(tbl->first.array);
83 return -1;
84 }
85
86 for (i = 0; i < positions; i++)
87 tbl->first.array[i] = tbl->second.array[i] = NULL;
88
89 tbl->positions = positions;
90 tbl->size = tbl->first.size = tbl->second.size = 0;
91
92 return 0;
93 }
94
95 static void cuckoo_destroy(struct cuckoo_tbl *tbl)
96 {
97 unsigned int i;
98
99 for (i = 0; i < tbl->positions; i++) {
100 if (tbl->first.array[i])
101 free(tbl->first.array[i]);
102
103 if (tbl->second.array[i])
104 free(tbl->second.array[i]);
105 }
106
107 free(tbl->first.array);
108 free(tbl->second.array);
109 }
110
111 static inline int cuckoo_lookup(struct cuckoo_tbl *tbl, char *name,
112 unsigned int *h)
113 {
114 unsigned int hash;
115
116 hash = tdb_hash(name) % tbl->positions;
117 if (tbl->first.array[hash] == NULL)
118 return 0;
119
120 if (!memcmp(tbl->first.array[hash], name, NAME_LENGTH))
121 goto found;
122
123 hash = joaat_hash(name) % tbl->positions;
124 if (tbl->second.array[hash] == NULL)
125 return 0;
126
127 if (!memcmp(tbl->second.array[hash], name, NAME_LENGTH))
128 goto found;
129
130 return 0;
131
132 found:
133 if (h)
134 *h = hash;
135 return 1;
136 }
137
138 static int cuckoo_insert(struct cuckoo_tbl *tbl, char *name)
139 {
140 int ret;
141 void *el, *tmp;
142 unsigned int i, hash;
143
144 ret = cuckoo_lookup(tbl, name, NULL);
145 if (ret) {
146 /* key already exists */
147 return 1;
148 }
149
150 el = (void *) name;
151
152 for (i = 0; i < tbl->positions; i++) {
153
154 hash = tdb_hash(el) % tbl->positions;
155 if (tbl->first.array[hash] == NULL) {
156 tbl->first.array[hash] = el;
157 tbl->first.size++;
158 goto out;
159 }
160
161 tmp = tbl->first.array[hash];
162 tbl->first.array[hash] = el;
163 el = tmp;
164
165 hash = joaat_hash(el) % tbl->positions;
166 if (tbl->second.array[hash] == NULL) {
167 tbl->second.array[hash] = el;
168 tbl->second.size++;
169 goto out;
170 }
171
172 tmp = tbl->second.array[hash];
173 tbl->second.array[hash] = el;
174 el = tmp;
175 }
176
177 fprintf(stderr, "Out of Max loop, aborting\n");
178 abort();
179
180 out:
181 tbl->size++;
182 return 0;
183 }
184
185 #if 0
186 static struct cuckoo_tbl *rehash(struct cuckoo_tbl *tbl)
187 {
188 int err;
189 unsigned int i;
190 struct cuckoo_tbl *new_table;
191
192 new_table = malloc(sizeof(struct cuckoo_tbl));
193 if (!new_table)
194 return NULL;
195
196 err = cuckoo_init(new_table, tbl->positions * 2);
197 if (err)
198 goto out_err;
199
200 for (i = 0; i < tbl->positions; i++) {
201 if (tbl->first.array[i]) {
202 err = cuckoo_insert(new_table,
203 tbl->first.array[i]);
204 if (err)
205 goto out_err;
206 }
207
208 if (tbl->second.array[i]) {
209 err = cuckoo_insert(new_table,
210 tbl->second.array[i]);
211 if (err)
212 goto out_err;
213 }
214 }
215
216 cuckoo_destroy(tbl);
217 free(tbl);
218
219 return new_table;
220
221 out_err:
222 free(new_table);
223 return NULL;
224 }
225 #endif
226
227 static void cuckoo_print_stats(struct cuckoo_tbl *tbl)
228 {
229 printf("\n-> Hash table statistics\n");
230 printf("First table size: %4d\n", tbl->positions);
231 printf(" o in use: %4d\n", tbl->first.size);
232 printf(" o free: %4d\n", tbl->positions - tbl->first.size);
233 printf("Second table size: %4d\n", tbl->positions);
234 printf(" o in use: %4d\n", tbl->second.size);
235 printf(" o free: %4d\n", tbl->positions - tbl->second.size);
236 printf("\n");
237 }
238
239 static int cuckoo_load_file(struct cuckoo_tbl *tbl, const char *fname)
240 {
241 FILE *file;
242 char line[24];
243
244 file = fopen(fname, "r");
245 if (!file)
246 return -1;
247
248 memset(line, 0, sizeof(line));
249
250 while (fgets(line, sizeof(line), file) != NULL) {
251 int err;
252 char *p;
253
254 if (line[0] == '#') {
255 if (!strchr(line, '\n')) {
256 int c;
257
258 while ((c = getc(file)) != '\n')
259 /* NOTHING */;
260 }
261 memset(line, 0, sizeof(line));
262 continue;
263 }
264
265 p = strchr(line, '\n');
266 if (p)
267 *p = '\0';
268
269 p = strdup(line);
270 if (!p) {
271 fclose(file);
272 return -1;
273 }
274
275 err = cuckoo_insert(tbl, p);
276 if (err) {
277 free(p);
278 if (err == -1) {
279 fclose(file);
280 return -1;
281 }
282 /* else key already exists */
283 }
284 memset(line, 0, sizeof(line));
285 }
286
287 fclose(file);
288 return 0;
289 }
290
291 /* FIXME: duplicated from cuckoo_load_file() */
292 static int cuckoo_self_test(struct cuckoo_tbl *tbl, const char *fname)
293 {
294 int found, ret;
295 FILE *file;
296 char line[24];
297
298 file = fopen(fname, "r");
299 if (!file)
300 return -1;
301
302 ret = 0;
303 memset(line, 0, sizeof(line));
304
305 while (fgets(line, sizeof(line), file) != NULL) {
306 char *p;
307
308 if (line[0] == '#') {
309 if (!strchr(line, '\n')) {
310 int c;
311
312 while ((c = getc(file)) != '\n')
313 /* NOTHING */;
314 }
315 memset(line, 0, sizeof(line));
316 continue;
317 }
318
319 p = strchr(line, '\n');
320 if (p)
321 *p = '\0';
322
323 found = cuckoo_lookup(tbl, line, NULL);
324 if (!found) {
325 printf(" Could not found: %s\n", line);
326 ret = -1;
327 break;
328 }
329
330 memset(line, 0, sizeof(line));
331 }
332
333 fclose(file);
334
335 found = cuckoo_lookup(tbl, "aaaaaaaaaaaaaaaaa", NULL);
336 if (found) {
337 fprintf(stderr, "found unknow string\n");
338 ret = 1;
339 }
340
341 return ret;
342 }
343
344 static int set_seed(void)
345 {
346 int fd, ret;
347 size_t bytes;
348 unsigned int seed;
349
350 fd = open("/dev/random", O_RDONLY);
351 if (fd < 0)
352 return -1;
353
354 bytes = read(fd, &seed, sizeof(seed));
355 if (bytes != sizeof(seed)) {
356 ret = -1;
357 goto out;
358 }
359
360 ret = 0;
361 srand(seed);
362 printf("\n-> Seed: %#X\n", seed);
363
364 out:
365 close(fd);
366 return ret;
367 }
368
369 static void lottery(char *result, size_t size)
370 {
371 int num, i, j;
372 int numbers[LOTTERY_MAX];
373
374 memset(result, 0, size);
375 memset(numbers, -1, sizeof(numbers));
376
377 for (i = 0; i < LOTTERY_MAX; i++) {
378 for (;;) {
379 int found = 0;
380
381 num = 1 + (int) (60.0 * (rand() / (RAND_MAX + 6.0)));
382
383 for (j = 0; j < i; j++)
384 if (numbers[j] == num) {
385 found = 1;
386 break;
387 }
388
389 if (!found) {
390 numbers[i] = num;
391 break;
392 }
393 }
394 }
395
396 snprintf(result, size, "%02d %02d %02d %02d %02d %02d",
397 numbers[0], numbers[1], numbers[2],
398 numbers[3], numbers[4], numbers[5]);
399 }
400
401 static void show_pid(void)
402 {
403 printf("-> PID: %d\n\n", getpid());
404 }
405
406 int main(int argc, char *argv[])
407 {
408 int stest, ret;
409 unsigned int hash;
410 struct cuckoo_tbl table;
411 char result[24], *fname;
412
413 stest = 0;
414
415 if (argc == 2) {
416 fname = argv[1];
417 } else if (argc == 3) {
418 fname = argv[1];
419 stest = 1;
420 } else {
421 printf("usage: %s < data-file >\n", argv[0]);
422 exit(1);
423 }
424
425 setlinebuf(stdout);
426
427 ret = cuckoo_init(&table, HASH_TABLE_SIZE);
428 if (ret) {
429 perror("cuckoo_init()");
430 ret = 1;
431 goto out;
432 }
433
434 ret = cuckoo_load_file(&table, fname);
435 if (ret) {
436 perror("cuckoo_load_file()");
437 ret = 1;
438 goto out;
439 }
440
441 cuckoo_print_stats(&table);
442
443 if (stest) {
444 ret = cuckoo_self_test(&table, fname);
445 printf("Performing self-test: ");
446 ret ? printf("FAILED!\n") : printf("PASSED!\n");
447 exit(0);
448 }
449
450 ret = set_seed();
451 if (ret) {
452 perror("set_seed()");
453 ret = 1;
454 goto out;
455 }
456
457 show_pid();
458
459 signal(SIGUSR1, sig_handler);
460 signal(SIGHUP, sig_handler);
461
462 for (;;) {
463
464 /*
465 * The following checks will probably make the program
466 * run slower, but I've implemented them because they're
467 * cool features (specially the reload table one).
468 *
469 * If you want full speed you should consider measuring
470 * this thing and removing these features if needed.
471 */
472
473 if (show_status) {
474 printf("-> Ran %lu (* %lu) times with %lu matches\n",
475 nr_runs, ulong_max, nr_found);
476 show_status = 0;
477 }
478
479 if (reload_table) {
480 /*
481 * XXX: Reading all the file again isn't a smart
482 * way to do this, we could start reading from
483 * the last line read.
484 */
485 ret = cuckoo_load_file(&table, argv[1]);
486 if (ret) {
487 perror("cuckoo_load_file()");
488 fprintf(stderr, "Aborting reload\n");
489 }
490 cuckoo_print_stats(&table);
491 reload_table = 0;
492 }
493
494 lottery(result, sizeof(result));
495
496 ret = cuckoo_lookup(&table, result, &hash);
497 if (ret) {
498 printf("-> HIT in run %lu: [%d] %s\n",
499 nr_runs, hash, result);
500 nr_found++;
501 }
502
503 if (++nr_runs == ULONG_MAX) {
504 if (++ulong_max == ULONG_MAX) {
505 printf("-> ulong_max blew up [%lu]\n",
506 ulong_max);
507 ulong_max = 0;
508 }
509 nr_runs = 0;
510 }
511 }
512
513 out:
514 cuckoo_destroy(&table);
515 return ret;
516 }
Capitulino's junk code