1 #include "vqueue.h"
2 #include "fch_buckets.h"
3 #include <stdio.h>
4 #include <assert.h>
5 #include <stdlib.h>
6 //#define DEBUG
7 #include "debug.h"
8
9 typedef struct __fch_bucket_entry_t
10 {
11 char * value;
12 cmph_uint32 length;
13 } fch_bucket_entry_t;
14
15 typedef struct __fch_bucket_t
16 {
17 fch_bucket_entry_t * entries;
18 cmph_uint32 capacity, size;
19 } fch_bucket_t;
20
21
22
23 static void fch_bucket_new(fch_bucket_t *bucket)
24 {
25 assert(bucket);
26 bucket->size = 0;
27 bucket->entries = NULL;
28 bucket->capacity = 0;
29 }
30
31 static void fch_bucket_destroy(fch_bucket_t *bucket)
32 {
33 cmph_uint32 i;
34 assert(bucket);
35 for (i = 0; i < bucket->size; i++)
36 {
37 free((bucket->entries + i)->value);
38 }
39 free(bucket->entries);
40 }
41
42
43 static void fch_bucket_reserve(fch_bucket_t *bucket, cmph_uint32 size)
44 {
45 assert(bucket);
46 if (bucket->capacity < size)
47 {
48 cmph_uint32 new_capacity = bucket->capacity + 1;
49 DEBUGP("Increasing current capacity %u to %u\n", bucket->capacity, size);
50 while (new_capacity < size)
51 {
52 new_capacity *= 2;
53 }
54 bucket->entries = (fch_bucket_entry_t *)realloc(bucket->entries, sizeof(fch_bucket_entry_t)*new_capacity);
55 assert(bucket->entries);
56 bucket->capacity = new_capacity;
57 DEBUGP("Increased\n");
58 }
59 }
60
61 static void fch_bucket_insert(fch_bucket_t *bucket, char *val, cmph_uint32 val_length)
62 {
63 assert(bucket);
64 fch_bucket_reserve(bucket, bucket->size + 1);
65 (bucket->entries + bucket->size)->value = val;
66 (bucket->entries + bucket->size)->length = val_length;
67 ++(bucket->size);
68 }
69
70
71 static cmph_uint8 fch_bucket_is_empty(fch_bucket_t *bucket)
72 {
73 assert(bucket);
74 return (cmph_uint8)(bucket->size == 0);
75 }
76
77 static cmph_uint32 fch_bucket_size(fch_bucket_t *bucket)
78 {
79 assert(bucket);
80 return bucket->size;
81 }
82
83 static char * fch_bucket_get_key(fch_bucket_t *bucket, cmph_uint32 index_key)
84 {
85 assert(bucket); assert(index_key < bucket->size);
86 return (bucket->entries + index_key)->value;
87 }
88
89 static cmph_uint32 fch_bucket_get_length(fch_bucket_t *bucket, cmph_uint32 index_key)
90 {
91 assert(bucket); assert(index_key < bucket->size);
92 return (bucket->entries + index_key)->length;
93 }
94
95 static void fch_bucket_print(fch_bucket_t * bucket, cmph_uint32 index)
96 {
97 cmph_uint32 i;
98 assert(bucket);
99 fprintf(stderr, "Printing bucket %u ...\n", index);
100 for (i = 0; i < bucket->size; i++)
101 {
102 fprintf(stderr, " key: %s\n", (bucket->entries + i)->value);
103 }
104 }
105
106 //////////////////////////////////////////////////////////////////////////////////////
107
108 struct __fch_buckets_t
109 {
110 fch_bucket_t * values;
111 cmph_uint32 nbuckets, max_size;
112
113 };
114
115 fch_buckets_t * fch_buckets_new(cmph_uint32 nbuckets)
116 {
117 cmph_uint32 i;
118 fch_buckets_t *buckets = (fch_buckets_t *)malloc(sizeof(fch_buckets_t));
119 assert(buckets);
120 buckets->values = (fch_bucket_t *)calloc((size_t)nbuckets, sizeof(fch_bucket_t));
121 for (i = 0; i < nbuckets; i++) fch_bucket_new(buckets->values + i);
122 assert(buckets->values);
123 buckets->nbuckets = nbuckets;
124 buckets->max_size = 0;
125 return buckets;
126 }
127
128 cmph_uint8 fch_buckets_is_empty(fch_buckets_t * buckets, cmph_uint32 index)
129 {
130 assert(index < buckets->nbuckets);
131 return fch_bucket_is_empty(buckets->values + index);
132 }
133
134 void fch_buckets_insert(fch_buckets_t * buckets, cmph_uint32 index, char * key, cmph_uint32 length)
135 {
136 assert(index < buckets->nbuckets);
137 fch_bucket_insert(buckets->values + index, key, length);
138 if (fch_bucket_size(buckets->values + index) > buckets->max_size)
139 {
140 buckets->max_size = fch_bucket_size(buckets->values + index);
141 }
142 }
143
144 cmph_uint32 fch_buckets_get_size(fch_buckets_t * buckets, cmph_uint32 index)
145 {
146 assert(index < buckets->nbuckets);
147 return fch_bucket_size(buckets->values + index);
148 }
149
150
151 char * fch_buckets_get_key(fch_buckets_t * buckets, cmph_uint32 index, cmph_uint32 index_key)
152 {
153 assert(index < buckets->nbuckets);
154 return fch_bucket_get_key(buckets->values + index, index_key);
155 }
156
157 cmph_uint32 fch_buckets_get_keylength(fch_buckets_t * buckets, cmph_uint32 index, cmph_uint32 index_key)
158 {
159 assert(index < buckets->nbuckets);
160 return fch_bucket_get_length(buckets->values + index, index_key);
161 }
162
163 cmph_uint32 fch_buckets_get_max_size(fch_buckets_t * buckets)
164 {
165 return buckets->max_size;
166 }
167
168 cmph_uint32 fch_buckets_get_nbuckets(fch_buckets_t * buckets)
169 {
170 return buckets->nbuckets;
171 }
172
173 cmph_uint32 * fch_buckets_get_indexes_sorted_by_size(fch_buckets_t * buckets)
174 {
175 cmph_uint32 i = 0;
176 cmph_uint32 sum = 0, value;
177 cmph_uint32 *nbuckets_size = (cmph_uint32 *) calloc((size_t)buckets->max_size + 1, sizeof(cmph_uint32));
178 cmph_uint32 * sorted_indexes = (cmph_uint32 *) calloc((size_t)buckets->nbuckets, sizeof(cmph_uint32));
179
180 // collect how many buckets for each size.
181 for(i = 0; i < buckets->nbuckets; i++) nbuckets_size[fch_bucket_size(buckets->values + i)] ++;
182
183 // calculating offset considering a decreasing order of buckets size.
184 value = nbuckets_size[buckets->max_size];
185 nbuckets_size[buckets->max_size] = sum;
186 for(i = (int)buckets->max_size - 1; i >= 0; i--)
187 {
188 sum += value;
189 value = nbuckets_size[i];
190 nbuckets_size[i] = sum;
191
192 }
193 for(i = 0; i < buckets->nbuckets; i++)
194 {
195 sorted_indexes[nbuckets_size[fch_bucket_size(buckets->values + i)]] = (cmph_uint32)i;
196 nbuckets_size[fch_bucket_size(buckets->values + i)] ++;
197 }
198 free(nbuckets_size);
199 return sorted_indexes;
200 }
201
202 void fch_buckets_print(fch_buckets_t * buckets)
203 {
204 cmph_uint32 i;
205 for (i = 0; i < buckets->nbuckets; i++) fch_bucket_print(buckets->values + i, i);
206 }
207
208 void fch_buckets_destroy(fch_buckets_t * buckets)
209 {
210 cmph_uint32 i;
211 for (i = 0; i < buckets->nbuckets; i++) fch_bucket_destroy(buckets->values + i);
212 free(buckets->values);
213 free(buckets);
214 }