File: radixmap.c

package info (click to toggle)
mongrel2 1.9.1-6
  • links: PTS, VCS
  • area: main
  • in suites: jessie-kfreebsd
  • size: 5,956 kB
  • sloc: ansic: 43,228; python: 2,827; sql: 1,555; makefile: 347; sh: 307; asm: 234; yacc: 145; php: 73; sed: 5
file content (289 lines) | stat: -rw-r--r-- 7,342 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
/*
* Based on code by Andre Reinald.
*/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <mem/halloc.h>
#include <endian.h>
#include "adt/radixmap.h"
#include "dbg.h"

// undefine this to run the more correct but slower sort
#define FAST_OPS

#if __BYTE_ORDER == __LITTLE_ENDIAN
#define ByteOf(x,y) (((uint8_t *)x)[(y)])
#elif __BYTE_ORDER == __BIG_ENDIAN
#define ByteOf(x,y) (((uint8_t *)x)[3-(y)])
#else
#error unknown byte order
#endif

static inline void radix_sort(short offset, uint64_t N, uint64_t *source, uint64_t *dest)
{
    uint64_t count[256] = {0};
    uint64_t *cp = NULL;
    uint64_t *sp = NULL;
    uint64_t *end = NULL;
    uint64_t s = 0;
    uint64_t c = 0;

    // count occurences of every byte value
    for (sp = source, end = source + N; sp < end; sp++) {
        count[ByteOf(sp, offset)]++;
    }

    // transform count into index by summing elements and storing into same array
    for (s = 0, cp = count, end = count + 256; cp < end; cp++) {
        c = *cp;
        *cp = s;
        s += c;
    }

    // fill dest with the right values in the right place
    for (sp = source, end = source + N; sp < end; sp++) {
        cp = count + ByteOf(sp, offset);
        dest[*cp] = *sp;
        ++(*cp);
    }
}

void RadixMap_sort(RadixMap *map)
{
    uint64_t *source = &map->contents[0].raw;
    uint64_t *temp = &map->temp[0].raw;

    radix_sort(0, map->end, source, temp);
    radix_sort(1, map->end, temp, source);
    radix_sort(2, map->end, source, temp);
    radix_sort(3, map->end, temp, source);
}

/**
 * This is primarily used by the tail sorted version to find the
 * lowest place to start sorting.  It's a quick binary search
 * of the data elements and returns whatever lowest value was
 * hit.
 */
RMElement *RadixMap_find_lowest(RadixMap *map, uint32_t to_find)
{
    int low = 0;
    int high = map->end - 1;
    RMElement *data = map->contents;

    while (low <= high) {
        int middle = low + (high - low)/2;
        uint32_t key = data[middle].data.key;

        if (to_find < key) {
            high = middle - 1;
        } else if (to_find > key) {
            low = middle + 1;
        } else {
            return &data[middle];
        }
    }

    return &data[low];
}

/**
 * A special version useful for things like add and delete that
 * takes a "hint", and then avoid sorting the whole array depending
 * on where the hint might fall.
 */
static inline void RadixMap_sort_tail(RadixMap *map, RMElement *hint)
{
    uint64_t *source = &map->contents[0].raw;
    uint64_t *temp = &map->temp[0].raw;
    size_t count = map->end;
    uint32_t max = 0;

    // if we only have to sort the top part then only do that
    if(count > 2) {
        if(hint->data.key == UINT32_MAX) {
            // this is a delete, so the hint is moving to the end,
            // only sort from the hint on
            source = &hint->raw;
            // we can just swap out the last one and drop the end by one
            *hint = map->contents[map->end - 1];
            count = map->contents + map->end - hint - 1;

            // that used to be the max
            max = hint->data.key;
        } else {
            // looks like this one is an add at the end
            // this is a simple optimization that gets decent performance
            RMElement *middle = RadixMap_find_lowest(map, hint->data.key);

            // middle is the bottom of the possible range
            count = map->contents + map->end - middle;
            source = &middle->raw;

            max = map->contents[map->end - 1].data.key;
        }

        // always have to sort the first two bytes worth
        radix_sort(0, count, source, temp);
        radix_sort(1, count, temp, source);

        if(max > UINT16_MAX) {
            // only sort if the max possible number is outside the first 2 bytes
            radix_sort(2, count, source, temp);
            radix_sort(3, count, temp, source);
        }
    } else {
        // shouldn't be a super common case, but if there's only
        // 2 elements then just a single comparison is best
        if(map->contents[0].data.key > map->contents[1].data.key) {
            map->temp[0] = map->contents[0];
            map->contents[0] = map->contents[1];
            map->contents[1] = map->temp[0];
        } else {
            // pass, there's only 2 elements, and they're already sorted
        }
    }
}


RMElement *RadixMap_find(RadixMap *map, uint32_t to_find)
{
    int low = 0;
    int high = map->end - 1;
    RMElement *data = map->contents;

    while (low <= high) {
        int middle = low + (high - low)/2;
        uint32_t key = data[middle].data.key;

        if (to_find < key) {
            high = middle - 1;
        } else if (to_find > key) {
            low = middle + 1;
        } else {
            return &data[middle];
        }
    }

    return NULL;
}


RadixMap *RadixMap_create(size_t max)
{
    RadixMap *map = NULL;
    map = calloc(sizeof(RadixMap), 1);

    check_mem(map);

    map->contents = calloc(sizeof(RMElement), max + 1);
    check_mem(map->contents);

    map->temp = calloc(sizeof(RMElement), max + 1);
    check_mem(map->temp);

    map->max = max;
    map->end = 0;

    return map;
error:
    if(map) {
        if(map->contents) {
            free(map->contents);
        }
        if(map->temp) {
            free(map->temp);
        }
        free(map);
    }
    return NULL;
}

void RadixMap_destroy(RadixMap *map)
{
    if(map) {
        free(map->contents);
        free(map->temp);
        free(map);
    }
}


int RadixMap_add(RadixMap *map, uint32_t key, uint32_t value)
{
    check(key < UINT32_MAX, "Key can't be equal to UINT32_MAX.");

    RMElement element = {.data = {.key = key, .value = value}};
    check(map->end + 1 < map->max, "RadixMap is full.");

    map->contents[map->end++] = element;

#ifdef FAST_OPS
    RadixMap_sort_tail(map, map->contents + map->end - 1);
#else
    RadixMap_sort(map);
#endif

    return 0;

error:
    return -1;
}

int RadixMap_delete(RadixMap *map, RMElement *el)
{
    check(map->end > 0, "There is nothing to delete.");
    check(el != NULL, "Can't delete a NULL element.");

    el->data.key = UINT32_MAX;

    if(map->end > 1) {
        // don't bother resorting a map of 1 length
#ifdef FAST_OPS
        RadixMap_sort_tail(map, el);
#else
        RadixMap_sort(map);
#endif
    }

    map->end--;

    return 0;
error:
    return -1;
}


uint32_t RadixMap_push(RadixMap *map, uint32_t value)
{
    RMElement *found = NULL;

    check(map->end + 1 < map->max, "RadixMap is full.");

    do {
        map->counter++;

        if(map->counter == UINT32_MAX) {
            // wrap it around so that we skip the ending trigger
            map->counter = 0;
        }

        found = RadixMap_find(map, map->counter);
    } while (found);

    if(map->end == 0 || map->contents[map->end-1].data.key < map->counter) {
        // this one already fits on the end so we're done
        RMElement element = {.data = {.key = map->counter, .value = value}};
        map->contents[map->end++] = element;
    } else {
        // looks like we probably wrapped around and need to do the slower add
        check(RadixMap_add(map, map->counter, value) == 0, "Failed to add on push.");
    }

    return map->counter;

error:
    return UINT32_MAX;
}