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