Date:2010-11-19 23:57:38 (13 years 4 months ago)
Author:Werner Almesberger
Commit:dec07f359a00778bc967e8e1fa32be082b264bd2
Message:qpkg/jrb.h: general code cleanup

- jrb.h: fixed indentation
- jrb.h: named anonymous parameters
- jrb.h: removed "extern" from function prototypes
Files: qpkg/jrb.h (2 diffs)

Change Details

qpkg/jrb.h
4646
4747
4848typedef struct jrb_node {
49  unsigned char red;
50  unsigned char internal;
51  unsigned char left;
52  unsigned char roothead; /* (bit 1 is root, bit 2 is head) */
53  struct jrb_node *flink;
54  struct jrb_node *blink;
55  struct jrb_node *parent;
56  void *key;
57  void *val;
49    unsigned char red;
50    unsigned char internal;
51    unsigned char left;
52    unsigned char roothead; /* (bit 1 is root, bit 2 is head) */
53    struct jrb_node *flink;
54    struct jrb_node *blink;
55    struct jrb_node *parent;
56    void *key;
57    void *val;
5858} *JRB;
5959
6060
61extern JRB make_jrb(void); /* Creates a new rb-tree */
61JRB make_jrb(void); /* Creates a new rb-tree */
6262
6363
6464/* Creates a node with key key and val val and inserts it into the tree.
6565   jrb_insert uses strcmp() as comparison funcion. jrb_inserti uses <>=,
6666   jrb_insertg uses func() */
6767
68extern JRB jrb_insert(JRB tree, void *key, void *val,
69    int (*func)(const void *, const void *));
68JRB jrb_insert(JRB tree, void *key, void *val,
69    int (*func)(const void *a, const void *b));
7070
7171/* returns an external node in t whose value is equal k. Returns NULL if
7272   there is no such node in the tree */
7373
74extern JRB jrb_find(JRB root, const void *,
75    int (*func)(const void *, const void *));
74JRB jrb_find(JRB root, const void *key,
75    int (*func)(const void *a, const void *b));
7676
7777/* returns an external node in t whose value is equal
7878  k or whose value is the smallest value greater than k. Sets found to
7979  1 if the key was found, and 0 otherwise. */
8080
81extern JRB jrb_find_gte(JRB root, const void *key,
82    int (*func)(const void *, const void *), int *found);
81JRB jrb_find_gte(JRB root, const void *key,
82    int (*func)(const void *a, const void *b), int *found);
8383
8484
8585/* Creates a node with key key and val val and inserts it into the
8686   tree before/after node nd. Does not check to ensure that you are
8787   keeping the correct order */
8888
89extern void jrb_delete_node(JRB node); /* Deletes and frees a node (but
90                                              not the key or val) */
91extern void jrb_free_tree(JRB root); /* Deletes and frees an entire tree */
89void jrb_delete_node(JRB node); /* Deletes and frees a node (but
90                                    not the key or val) */
91void jrb_free_tree(JRB root); /* Deletes and frees an entire tree */
9292
93extern void *jrb_val(JRB node); /* Returns node->v.val -- this is to shut
94                                       lint up */
93void *jrb_val(JRB node); /* Returns node->v.val -- this is to shut
94                             lint up */
9595
96extern int jrb_nblack(JRB n); /* returns # of black nodes in path from
97                                    n to the root */
96int jrb_nblack(JRB n); /* returns # of black nodes in path from
97                          n to the root */
9898int jrb_plength(JRB n); /* returns the # of nodes in path from
99                    n to the root */
99                 n to the root */
100100
101101#define jrb_first(n) ((n)->flink)
102102#define jrb_last(n) ((n)->blink)
...... 
108108#endif
109109
110110#define jrb_traverse(ptr, lst) \
111  for(ptr = jrb_first(lst); ptr != jrb_nil(lst); ptr = jrb_next(ptr))
111    for (ptr = jrb_first(lst); ptr != jrb_nil(lst); ptr = jrb_next(ptr))
112112
113113#define jrb_rtraverse(ptr, lst) \
114  for(ptr = jrb_last(lst); ptr != jrb_nil(lst); ptr = jrb_prev(ptr))
114    for (ptr = jrb_last(lst); ptr != jrb_nil(lst); ptr = jrb_prev(ptr))
115115
116116#endif

Archive Download the corresponding diff file

Branches:
master



interactive