← Back to branch summary

~ubuntu-branches/ubuntu/wily/grass/wily

« back to all changes in this revision

Viewing changes to include/rbtree.h

Tags: 7.0.0~rc1+ds1-1~exp1
http://bugs.debian.org/776349
* New upstream release candidate.
* Repack upstream tarball, remove precompiled Python objects.
* Add upstream metadata.
* Update gbp.conf and Vcs-Git URL to use the experimental branch.
* Update watch file for GRASS 7.0.
* Drop build dependencies for Tcl/Tk, add build dependencies:
  python-numpy, libnetcdf-dev, netcdf-bin, libblas-dev, liblapack-dev
* Update Vcs-Browser URL to use cgit instead of gitweb.
* Update paths to use grass70.
* Add configure options: --with-netcdf, --with-blas, --with-lapack,
  remove --with-tcltk-includes.
* Update patches for GRASS 7.
* Update copyright file, changes:
  - Update copyright years
  - Group files by license
  - Remove unused license sections
* Add patches for various typos.
* Fix desktop file with patch instead of d/rules.
* Use minimal dh rules.
* Bump Standards-Version to 3.9.6, no changes.
* Use dpkg-maintscript-helper to replace directories with symlinks.
  (closes: #776349)
* Update my email to use @debian.org address.

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/rbtree.h
 
1
/*************************************************************
 
2
 *                          USAGE                            *
 
3
 *************************************************************
 
4
 *
 
5
 * NOTE: duplicates are not supported
 
6
 *
 
7
 * custom compare function
 
8
 * extern int my_compare_fn(const void *, const void *);
 
9
 * int my_compare_fn(const void *a, const void *b) {
 
10
 *   if ((mydatastruct *) a < (mydatastruct *) b)
 
11
 *     return -1;
 
12
 *   else if ((mydatastruct *) a > (mydatastruct *) b)
 
13
 *     return 1;
 
14
 *   else if ((mydatastruct *) a == (mydatastruct *) b)
 
15
 *     return 0;
 
16
 * }
 
17
 * 
 
18
 * create and initialize tree:
 
19
 * struct RB_TREE *mytree = rbtree_create(my_compare_fn, item_size);
 
20
 *
 
21
 * insert items to tree:
 
22
 * struct mydatastruct data = <some data>;
 
23
 * if (rbtree_insert(mytree, &data) == 0)
 
24
 *       G_warning("could not insert data");
 
25
 *
 
26
 * find item in tree:
 
27
 * struct mydatastruct data = <some data>;
 
28
 * if (rbtree_find(mytree, &data) == 0)
 
29
 *       G_message("data not found");
 
30
 *
 
31
 * delete item from tree:
 
32
 * struct mydatastruct data = <some data>;
 
33
 * if (rbtree_remove(mytree, &data) == 0)
 
34
 *        G_warning("could not find data in tree");
 
35
 *
 
36
 * traverse tree (get all items in tree in ascending order):
 
37
 * struct RB_TRAV trav;
 
38
 * rbtree_init_trav(&trav, tree);
 
39
 * while ((data = rbtree_traverse(&trav)) != NULL) {
 
40
 *   if (my_compare_fn(data, threshold_data) == 0) break;
 
41
 *         <do something with data>;
 
42
 *  }
 
43
 *
 
44
 * get a selection of items: all data > data1 and < data2
 
45
 * start in tree where data is last smaller or first larger compared to data1
 
46
 * struct RB_TRAV trav;
 
47
 * rbtree_init_trav(&trav, tree);
 
48
 * data = rbtree_traverse_start(&trav, &data1);
 
49
 *       <do something with data>;
 
50
 * while ((data = rbtree_traverse(&trav)) != NULL) {
 
51
 *       if (data > data2) break;
 
52
 *   <do something with data>;
 
53
 * }
 
54
 *
 
55
 * destroy tree:
 
56
 * rbtree_destroy(mytree);
 
57
 *
 
58
 * debug the whole tree with
 
59
 * rbtree_debug(mytree, mytree->root);
 
60
 * 
 
61
 *************************************************************/
 
62
 
 
63
#ifndef GRASS_RBTREE_H
 
64
#define GRASS_RBTREE_H
 
65
 
 
66
#include <stddef.h>
 
67
 
 
68
/* maximum RB Tree height */
 
69
#define RBTREE_MAX_HEIGHT 64        /* should be more than enough */
 
70
 
 
71
/* routine to compare data items
 
72
 * return -1 if rb_a < rb_b
 
73
 * return  0 if rb_a == rb_b
 
74
 * return  1 if rb_a > rb_b
 
75
 */
 
76
typedef int rb_compare_fn(const void *rb_a, const void *rb_b);
 
77
 
 
78
struct RB_NODE
 
79
{
 
80
    unsigned char red;              /* 0 = black, 1 = red */
 
81
    void *data;                     /* any kind of data */
 
82
    struct RB_NODE *link[2];        /* link to children: link[0] for smaller, link[1] for larger */
 
83
};
 
84
 
 
85
struct RB_TREE
 
86
{
 
87
    struct RB_NODE *root;           /* root node */
 
88
    size_t datasize;                /* item size */
 
89
    size_t count;                   /* number of items in tree. */
 
90
    rb_compare_fn *rb_compare;      /* function to compare data */
 
91
};
 
92
 
 
93
struct RB_TRAV
 
94
{
 
95
    struct RB_TREE *tree;           /* tree being traversed */
 
96
    struct RB_NODE *curr_node;      /* current node */
 
97
    struct RB_NODE *up[RBTREE_MAX_HEIGHT];  /* stack of parent nodes */
 
98
    int top;                        /* index for stack */
 
99
    int first;                      /* little helper flag */
 
100
};
 
101
 
 
102
#include <grass/defs/rbtree.h>
 
103
 
 
104
#endif