odds and sods
[tridge/junkcode.git] / hashreplace.c
1 #include <stdio.h>
2 #include <unistd.h>
3 #include <stdlib.h>
4 #include <string.h>
5 #include <math.h>
6 #include <time.h>
7
8
9 #define TOTAL_SIZE (1024*1024)
10 #define HASH_SIZE (1000)
11 #define NBUCKETS 8
12
13 typedef unsigned u32;
14
15 struct hash_entry {
16         u32 offset;
17         u32 tag;
18 };
19
20
21
22 static struct hash_entry hash_table[HASH_SIZE];
23
24 static int bucket_flat(u32 offset, u32 limit)
25 {
26         u32 b = (offset / (limit/NBUCKETS));
27         return NBUCKETS - b;
28 }
29
30 static int bucket(u32 offset, u32 limit)
31 {
32         u32 rem = limit-offset;
33         u32 m = limit>>NBUCKETS;
34         int i = 0;
35         u32 b = m;
36
37         if (m == 0) return 0;
38
39         while (rem > b) {
40                 i++;
41                 b += (m<<i);
42         }
43
44         return i;
45 }
46
47
48 static void print_distribution(u32 limit)
49 {
50         u32 counts[NBUCKETS+1];
51         int i;
52         memset(counts, 0, sizeof(counts));
53
54         for (i=0;i<HASH_SIZE;i++) {
55                 u32 b = bucket(hash_table[i].offset, limit);
56                 counts[b]++;
57         }
58
59         for (i=0;i<NBUCKETS+1;i++) {
60                 printf("bucket %3d  %.3f\n", 
61                        i, (100.0 * counts[i]) / HASH_SIZE);
62         }
63 }
64
65
66 static int replace(u32 old_offset, u32 new_offset)
67 {
68         u32 x;
69
70         x = 1.2 * sqrt(new_offset * old_offset) / HASH_SIZE;
71
72         if (x == 0) return 1;
73
74         if (random() % x == 0) return 1;
75         return 0;
76 }
77
78 static u32 lbs(u32 x)
79 {
80         u32 i;
81         for (i=0;i<32;i++) {
82                 if (x & (1<<i)) break;
83         }
84         return i;
85 }
86
87 static int yy_replace(u32 old_offset, u32 new_offset)
88 {
89         u32 x = 20;
90
91         if (1.0*lbs(old_offset) < (bucket(old_offset, new_offset)+1)) {
92                 return 1;
93         }
94
95         return 0;
96 }
97
98 static int XX_replace(u32 old_offset, u32 new_offset)
99 {
100         double p;
101         p = 0.5 / (((double)new_offset) / (HASH_SIZE * NBUCKETS));
102         return (random() % 1000) < 1000 * p;
103 }
104
105 static void fill_hash_table(void)
106 {
107         int i;
108         for (i=0;i<TOTAL_SIZE/2;i++) {
109                 u32 tag = random();
110                 u32 t = tag % HASH_SIZE;
111
112                 if (hash_table[t].offset == 0 ||
113                     replace(hash_table[t].offset, i)) {
114                         hash_table[t].offset = i;
115                         hash_table[t].tag = tag;
116                 }
117         }
118
119         print_distribution(i);
120         printf("\n");
121
122         for (;i<TOTAL_SIZE;i++) {
123                 u32 tag = random();
124                 u32 t = tag % HASH_SIZE;
125
126                 if (hash_table[t].offset == 0 ||
127                     replace(hash_table[t].offset, i)) {
128                         hash_table[t].offset = i;
129                         hash_table[t].tag = tag;
130                 }
131         }
132
133         print_distribution(i);
134 }
135
136  int main(int argc, const char *argv[])
137 {
138         srandom(time(NULL));
139         fill_hash_table();
140         return 0;
141 }