← Back to branch summary

~ubuntu-branches/ubuntu/trusty/gobject-introspection/trusty

« back to all changes in this revision

Viewing changes to girepository/cmph/fch_buckets.c

  • Committer: Bazaar Package Importer
  • Author(s): Emilio Pozuelo Monfort
  • Date: 2011-03-22 00:32:36 UTC
  • mfrom: (1.4.1 upstream) (3.3.33 multiarch)
  • Revision ID: james.westby@ubuntu.com-20110322003236-4spdgfk1vai6xay1
Tags: 0.10.4-2
Upload to unstable.

Show diffs side-by-side

added added

removed removed

Lines of Context:
girepository/cmph/fch_buckets.c
 
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
}