← Back to branch summary

~ubuntu-branches/ubuntu/vivid/grass/vivid-proposed

« back to all changes in this revision

Viewing changes to imagery/i.atcorr/rbtree.cpp

  • Committer: Package Import Robot
  • Author(s): Bas Couwenberg
  • Date: 2015-02-20 23:12:08 UTC
  • mfrom: (8.2.6 experimental)
  • Revision ID: package-import@ubuntu.com-20150220231208-1u6qvqm84v430b10
Tags: 7.0.0-1~exp1
* New upstream release.
* Update python-ctypes-ternary.patch to use if/else instead of and/or.
* Drop check4dev patch, rely on upstream check.
* Add build dependency on libpq-dev to grass-dev for libpq-fe.h.
* Drop patches applied upstream, refresh remaining patches.
* Update symlinks for images switched from jpg to png.

Show diffs side-by-side

added added

removed removed

Lines of Context:
imagery/i.atcorr/rbtree.cpp
1
 
/*!
2
 
 * \file rbtree.c
3
 
 *
4
 
 * \brief binary search tree 
5
 
 *
6
 
 * Generic balanced binary search tree (Red Black Tree) implementation
7
 
 *
8
 
 * (C) 2009 by the GRASS Development Team
9
 
 *
10
 
 * This program is free software under the GNU General Public License
11
 
 * (>=v2).  Read the file COPYING that comes with GRASS for details.
12
 
 *
13
 
 * \author Original author Julienne Walker 2003, 2008
14
 
 *         GRASS implementation Markus Metz, 2009
15
 
 */
16
 
 
17
 
/* balanced binary search tree implementation
18
 
 * 
19
 
 * this one is a Red Black Tree, no parent pointers, no threads
20
 
 * The core code comes from Julienne Walker's tutorials on binary search trees
21
 
 * original license: public domain
22
 
 * http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
23
 
 * some ideas come from libavl (GPL >= 2)
24
 
 *
25
 
 * Red Black Trees are used to maintain a data structure with
26
 
 * search, insertion and deletion in O(log N) time
27
 
 */
28
 
 
29
 
#include <cassert>
30
 
#include <cstdlib>
31
 
#include <cstring>
32
 
 
33
 
extern "C"
34
 
{
35
 
#include <grass/gis.h>
36
 
#include <grass/glocale.h>
37
 
}
38
 
#include "rbtree.h"
39
 
 
40
 
/* internal functions */
41
 
struct RB_NODE *rbtree_single(struct RB_NODE *, int);
42
 
struct RB_NODE *rbtree_double(struct RB_NODE *, int);
43
 
void *rbtree_first(struct RB_TRAV *);
44
 
void *rbtree_next(struct RB_TRAV *);
45
 
struct RB_NODE *rbtree_make_node(size_t, void *);
46
 
int is_red(struct RB_NODE *);
47
 
 
48
 
 
49
 
/* create new tree and initialize
50
 
 * returns pointer to new tree, NULL for memory allocation error
51
 
 */
52
 
struct RB_TREE *rbtree_create(rb_compare_fn *compare, size_t rb_datasize)
53
 
{
54
 
    struct RB_TREE *tree = (struct RB_TREE *)malloc(sizeof(struct RB_TREE));
55
 
 
56
 
    if (tree == NULL) {
57
 
        G_warning("RB tree: Out of memory!");
58
 
        return NULL;
59
 
    }
60
 
 
61
 
    assert(compare);
62
 
 
63
 
    tree->datasize = rb_datasize;
64
 
    tree->rb_compare = compare;
65
 
    tree->count = 0;
66
 
    tree->root = NULL;
67
 
 
68
 
    return tree;
69
 
}
70
 
 
71
 
/* add an item to a tree
72
 
 * non-recursive top-down insertion
73
 
 * the algorithm does not allow duplicates and also does not warn about a duplicate
74
 
 * returns 1 on success, 0 on failure
75
 
 */
76
 
int rbtree_insert(struct RB_TREE *tree, void *data)
77
 
{
78
 
    assert(tree && data);
79
 
 
80
 
    if (tree->root == NULL) {
81
 
        /* create a new root node for tree */
82
 
        tree->root = rbtree_make_node(tree->datasize, data);
83
 
        if (tree->root == NULL)
84
 
            return 0;
85
 
    }
86
 
    else {
87
 
        struct RB_NODE head = { 0 };    /* False tree root */
88
 
        struct RB_NODE *g, *t;  /* Grandparent & parent */
89
 
        struct RB_NODE *p, *q;  /* Iterator & parent */
90
 
        int dir = 0, last = 0;
91
 
 
92
 
        /* Set up helpers */
93
 
        t = &head;
94
 
        g = p = NULL;
95
 
        q = t->link[1] = tree->root;
96
 
 
97
 
        /* Search down the tree */
98
 
        for (;;) {
99
 
            if (q == NULL) {
100
 
                /* Insert new node at the bottom */
101
 
                p->link[dir] = q = rbtree_make_node(tree->datasize, data);
102
 
                if (q == NULL)
103
 
                    return 0;
104
 
            }
105
 
            else if (is_red(q->link[0]) && is_red(q->link[1])) {
106
 
                /* Color flip */
107
 
                q->red = 1;
108
 
                q->link[0]->red = 0;
109
 
                q->link[1]->red = 0;
110
 
            }
111
 
 
112
 
            /* Fix red violation */
113
 
            if (is_red(q) && is_red(p)) {
114
 
                int dir2 = t->link[1] == g;
115
 
 
116
 
                if (q == p->link[last])
117
 
                    t->link[dir2] = rbtree_single(g, !last);
118
 
                else
119
 
                    t->link[dir2] = rbtree_double(g, !last);
120
 
            }
121
 
 
122
 
            last = dir;
123
 
            dir = tree->rb_compare(q->data, data);
124
 
 
125
 
            /* Stop if found. This check also disallows duplicates in the tree */
126
 
            if (dir == 0)
127
 
                break;
128
 
 
129
 
            dir = dir < 0;
130
 
 
131
 
            /* Move the helpers down */
132
 
            if (g != NULL)
133
 
                t = g;
134
 
 
135
 
            g = p, p = q;
136
 
            q = q->link[dir];
137
 
        }
138
 
 
139
 
        /* Update root */
140
 
        tree->root = head.link[1];
141
 
    }
142
 
 
143
 
    /* Make root black */
144
 
    tree->root->red = 0;
145
 
 
146
 
    tree->count++;
147
 
 
148
 
    return 1;
149
 
}
150
 
 
151
 
/* remove an item from a tree that matches given data
152
 
 * non-recursive top-down removal
153
 
 * returns 1 on successful removal
154
 
 * returns 0 if data item was not found
155
 
 */
156
 
int rbtree_remove(struct RB_TREE *tree, const void *data)
157
 
{
158
 
    struct RB_NODE head = { 0 };        /* False tree root */
159
 
    struct RB_NODE *q, *p, *g;  /* Helpers */
160
 
    struct RB_NODE *f = NULL;   /* Found item */
161
 
    int dir = 1, removed = 0;
162
 
 
163
 
    assert(tree && data);
164
 
 
165
 
    if (tree->root == NULL) {
166
 
        return 0;               /* empty tree, nothing to remove */
167
 
    }
168
 
 
169
 
    /* Set up helpers */
170
 
    q = &head;
171
 
    g = p = NULL;
172
 
    q->link[1] = tree->root;
173
 
 
174
 
    /* Search and push a red down */
175
 
    while (q->link[dir] != NULL) {
176
 
        int last = dir;
177
 
 
178
 
        /* Update helpers */
179
 
        g = p, p = q;
180
 
        q = q->link[dir];
181
 
        dir = tree->rb_compare(q->data, data);
182
 
 
183
 
        /* Save found node */
184
 
        if (dir == 0)
185
 
            f = q;
186
 
 
187
 
        dir = dir < 0;
188
 
 
189
 
        /* Push the red node down */
190
 
        if (!is_red(q) && !is_red(q->link[dir])) {
191
 
            if (is_red(q->link[!dir]))
192
 
                p = p->link[last] = rbtree_single(q, dir);
193
 
            else if (!is_red(q->link[!dir])) {
194
 
                struct RB_NODE *s = p->link[!last];
195
 
 
196
 
                if (s != NULL) {
197
 
                    if (!is_red(s->link[!last]) && !is_red(s->link[last])) {
198
 
                        /* Color flip */
199
 
                        p->red = 0;
200
 
                        s->red = 1;
201
 
                        q->red = 1;
202
 
                    }
203
 
                    else {
204
 
                        int dir2 = g->link[1] == p;
205
 
 
206
 
                        if (is_red(s->link[last]))
207
 
                            g->link[dir2] = rbtree_double(p, last);
208
 
                        else if (is_red(s->link[!last]))
209
 
                            g->link[dir2] = rbtree_single(p, last);
210
 
 
211
 
                        /* Ensure correct coloring */
212
 
                        q->red = g->link[dir2]->red = 1;
213
 
                        g->link[dir2]->link[0]->red = 0;
214
 
                        g->link[dir2]->link[1]->red = 0;
215
 
                    }
216
 
                }
217
 
            }
218
 
        }
219
 
    }
220
 
 
221
 
    /* Replace and remove if found */
222
 
    if (f != NULL) {
223
 
        free(f->data);
224
 
        f->data = q->data;
225
 
        p->link[p->link[1] == q] = q->link[q->link[0] == NULL];
226
 
        free(q);
227
 
        q = NULL;
228
 
        tree->count--;
229
 
        removed = 1;
230
 
    }
231
 
    else
232
 
        G_debug(2, "RB tree: data not found in search tree");
233
 
 
234
 
    /* Update root and make it black */
235
 
    tree->root = head.link[1];
236
 
    if (tree->root != NULL)
237
 
        tree->root->red = 0;
238
 
 
239
 
    return removed;
240
 
}
241
 
 
242
 
/* find data item in tree
243
 
 * returns pointer to data item if found else NULL
244
 
 */
245
 
void *rbtree_find(struct RB_TREE *tree, const void *data)
246
 
{
247
 
    struct RB_NODE *curr_node = tree->root;
248
 
    int cmp;
249
 
 
250
 
    assert(tree && data);
251
 
 
252
 
    while (curr_node != NULL) {
253
 
        cmp = tree->rb_compare(curr_node->data, data);
254
 
        if (cmp == 0)
255
 
            return curr_node->data;     /* found */
256
 
 
257
 
        curr_node = curr_node->link[cmp < 0];
258
 
    }
259
 
    return NULL;
260
 
}
261
 
 
262
 
/* initialize tree traversal
263
 
 * (re-)sets trav structure
264
 
 * returns 0
265
 
 */
266
 
int rbtree_init_trav(struct RB_TRAV *trav, struct RB_TREE *tree)
267
 
{
268
 
    assert(trav && tree);
269
 
 
270
 
    trav->tree = tree;
271
 
    trav->curr_node = tree->root;
272
 
    trav->first = 1;
273
 
    trav->top = 0;
274
 
 
275
 
    return 0;
276
 
}
277
 
 
278
 
/* traverse the tree in ascending order
279
 
 * useful to get all items in the tree non-recursively
280
 
 * struct RB_TRAV *trav needs to be initialized first
281
 
 * returns pointer to data, NULL when finished
282
 
 */
283
 
void *rbtree_traverse(struct RB_TRAV *trav)
284
 
{
285
 
    assert(trav);
286
 
 
287
 
    if (trav->curr_node == NULL) {
288
 
        if (trav->first)
289
 
            G_debug(1, "RB tree: empty tree");
290
 
        else
291
 
            G_debug(1, "RB tree: finished traversing");
292
 
 
293
 
        return NULL;
294
 
    }
295
 
 
296
 
    if (!trav->first)
297
 
        return rbtree_next(trav);
298
 
    else {
299
 
        trav->first = 0;
300
 
        return rbtree_first(trav);
301
 
    }
302
 
}
303
 
 
304
 
/* find start point to traverse the tree in ascending order
305
 
 * useful to get a selection of items in the tree
306
 
 * magnitudes faster than traversing the whole tree
307
 
 * may return first item that's smaller or first item that's larger
308
 
 * struct RB_TRAV *trav needs to be initialized first
309
 
 * returns pointer to data, NULL when finished
310
 
 */
311
 
void *rbtree_traverse_start(struct RB_TRAV *trav, const void *data)
312
 
{
313
 
    int dir = 0;
314
 
 
315
 
    assert(trav && data);
316
 
 
317
 
    if (trav->curr_node == NULL) {
318
 
        if (trav->first)
319
 
            G_warning("RB tree: empty tree");
320
 
        else
321
 
            G_warning("RB tree: finished traversing");
322
 
 
323
 
        return NULL;
324
 
    }
325
 
 
326
 
    if (!trav->first)
327
 
        return rbtree_next(trav);
328
 
 
329
 
    /* else first time, get start node */
330
 
 
331
 
    trav->first = 0;
332
 
    trav->top = 0;
333
 
 
334
 
    while (trav->curr_node != NULL) {
335
 
        dir = trav->tree->rb_compare(trav->curr_node->data, data);
336
 
        /* exact match, great! */
337
 
        if (dir == 0)
338
 
            return trav->curr_node->data;
339
 
        else {
340
 
            dir = dir < 0;
341
 
            /* end of branch, also reached if
342
 
             * smallest item is larger than search template or
343
 
             * largest item is smaller than search template */
344
 
            if (trav->curr_node->link[dir] == NULL)
345
 
                return trav->curr_node->data;
346
 
 
347
 
            trav->up[trav->top++] = trav->curr_node;
348
 
            trav->curr_node = trav->curr_node->link[dir];
349
 
        }
350
 
    }
351
 
 
352
 
    return NULL;                /* should not happen */
353
 
}
354
 
 
355
 
/* two functions needed to fully traverse the tree: initialize and continue
356
 
 * useful to get all items in the tree non-recursively
357
 
 * this one here uses a stack
358
 
 * parent pointers or threads would also be possible
359
 
 * but these would need to be added to RB_NODE
360
 
 * -> more memory needed for standard operations
361
 
 */
362
 
 
363
 
/* start traversing the tree
364
 
 * returns pointer to smallest data item
365
 
 */
366
 
void *rbtree_first(struct RB_TRAV *trav)
367
 
{
368
 
    /* get smallest item */
369
 
    while (trav->curr_node->link[0] != NULL) {
370
 
        trav->up[trav->top++] = trav->curr_node;
371
 
        trav->curr_node = trav->curr_node->link[0];
372
 
    }
373
 
 
374
 
    return trav->curr_node->data;       /* return smallest item */
375
 
}
376
 
 
377
 
/* continue traversing the tree in ascending order
378
 
 * returns pointer to data item, NULL when finished
379
 
 */
380
 
void *rbtree_next(struct RB_TRAV *trav)
381
 
{
382
 
    if (trav->curr_node->link[1] != NULL) {
383
 
        /* something on the right side: larger item */
384
 
        trav->up[trav->top++] = trav->curr_node;
385
 
        trav->curr_node = trav->curr_node->link[1];
386
 
 
387
 
        /* go down, find smallest item in this branch */
388
 
        while (trav->curr_node->link[0] != NULL) {
389
 
            trav->up[trav->top++] = trav->curr_node;
390
 
            trav->curr_node = trav->curr_node->link[0];
391
 
        }
392
 
    }
393
 
    else {
394
 
        /* at smallest item in this branch, go back up */
395
 
        struct RB_NODE *last;
396
 
 
397
 
        do {
398
 
            if (trav->top == 0) {
399
 
                trav->curr_node = NULL;
400
 
                break;
401
 
            }
402
 
            last = trav->curr_node;
403
 
            trav->curr_node = trav->up[--trav->top];
404
 
        } while (last == trav->curr_node->link[1]);
405
 
    }
406
 
 
407
 
    if (trav->curr_node != NULL) {
408
 
        return trav->curr_node->data;
409
 
    }
410
 
    else
411
 
        return NULL;            /* finished traversing */
412
 
}
413
 
 
414
 
/* destroy the tree */
415
 
void rbtree_destroy(struct RB_TREE *tree)
416
 
{
417
 
    struct RB_NODE *it;
418
 
    struct RB_NODE *save = tree->root;
419
 
 
420
 
    /*
421
 
    Rotate away the left links so that
422
 
    we can treat this like the destruction
423
 
    of a linked list
424
 
    */
425
 
    while((it = save) != NULL) {
426
 
        if (it->link[0] == NULL) {
427
 
            /* No left links, just kill the node and move on */
428
 
            save = it->link[1];
429
 
            free(it->data);
430
 
            it->data = NULL;
431
 
            free(it);
432
 
            it = NULL;
433
 
        }
434
 
        else {
435
 
            /* Rotate away the left link and check again */
436
 
            save = it->link[0];
437
 
            it->link[0] = save->link[1];
438
 
            save->link[1] = it;
439
 
        }
440
 
    }
441
 
    free(tree);
442
 
    tree = NULL;
443
 
}
444
 
 
445
 
/* used for debugging: check for errors in tree structure */
446
 
int rbtree_debug(struct RB_TREE *tree, struct RB_NODE *root)
447
 
{
448
 
    int lh, rh;
449
 
 
450
 
    if (root == NULL)
451
 
        return 1;
452
 
    else {
453
 
        struct RB_NODE *ln = root->link[0];
454
 
        struct RB_NODE *rn = root->link[1];
455
 
        int lcmp = 0, rcmp = 0;
456
 
 
457
 
        /* Consecutive red links */
458
 
        if (is_red(root)) {
459
 
            if (is_red(ln) || is_red(rn)) {
460
 
                G_warning("Red Black Tree debugging: Red violation");
461
 
                return 0;
462
 
            }
463
 
        }
464
 
 
465
 
        lh = rbtree_debug(tree, ln);
466
 
        rh = rbtree_debug(tree, rn);
467
 
 
468
 
        if (ln) {
469
 
            lcmp = tree->rb_compare(ln->data, root->data);
470
 
        }
471
 
 
472
 
        if (rn) {
473
 
            rcmp = tree->rb_compare(rn->data, root->data);
474
 
        }
475
 
 
476
 
        /* Invalid binary search tree:
477
 
         * left node >= parent or right node <= parent */
478
 
        if ((ln != NULL && lcmp > -1)
479
 
            || (rn != NULL && rcmp < 1)) {
480
 
            G_warning("Red Black Tree debugging: Binary tree violation");
481
 
            return 0;
482
 
        }
483
 
 
484
 
        /* Black height mismatch */
485
 
        if (lh != 0 && rh != 0 && lh != rh) {
486
 
            G_warning("Red Black Tree debugging: Black violation");
487
 
            return 0;
488
 
        }
489
 
 
490
 
        /* Only count black links */
491
 
        if (lh != 0 && rh != 0)
492
 
            return is_red(root) ? lh : lh + 1;
493
 
        else
494
 
            return 0;
495
 
    }
496
 
}
497
 
 
498
 
/*******************************************************
499
 
 *                                                     *
500
 
 *  internal functions for Red Black Tree maintenance  *
501
 
 *                                                     *
502
 
 *******************************************************/
503
 
 
504
 
/* add a new node to the tree */
505
 
struct RB_NODE *rbtree_make_node(size_t datasize, void *data)
506
 
{
507
 
    struct RB_NODE *new_node = (struct RB_NODE *)malloc(sizeof(*new_node));
508
 
 
509
 
    if (new_node == NULL)
510
 
        G_fatal_error("RB Search Tree: Out of memory!");
511
 
 
512
 
    new_node->data = malloc(datasize);
513
 
    if (new_node->data == NULL)
514
 
        G_fatal_error("RB Search Tree: Out of memory!");
515
 
 
516
 
    memcpy(new_node->data, data, datasize);
517
 
    new_node->red = 1;          /* 1 is red, 0 is black */
518
 
    new_node->link[0] = NULL;
519
 
    new_node->link[1] = NULL;
520
 
 
521
 
    return new_node;
522
 
}
523
 
 
524
 
/* check for red violation */
525
 
int is_red(struct RB_NODE *root)
526
 
{
527
 
    if (root)
528
 
        return root->red == 1;
529
 
 
530
 
    return 0;
531
 
}
532
 
 
533
 
/* single rotation */
534
 
struct RB_NODE *rbtree_single(struct RB_NODE *root, int dir)
535
 
{
536
 
    struct RB_NODE *newroot = root->link[!dir];
537
 
 
538
 
    root->link[!dir] = newroot->link[dir];
539
 
    newroot->link[dir] = root;
540
 
 
541
 
    root->red = 1;
542
 
    newroot->red = 0;
543
 
 
544
 
    return newroot;
545
 
}
546
 
 
547
 
/* double rotation */
548
 
struct RB_NODE *rbtree_double(struct RB_NODE *root, int dir)
549
 
{
550
 
    root->link[!dir] = rbtree_single(root->link[!dir], !dir);
551
 
    return rbtree_single(root, dir);
552
 
}