Werner's Miscellanea
Sign in or create your account | Project List | Help
Werner's Miscellanea Commit Details
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 | ||
---|---|---|
46 | 46 | |
47 | 47 | |
48 | 48 | typedef 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; | |
58 | 58 | } *JRB; |
59 | 59 | |
60 | 60 | |
61 | extern JRB make_jrb(void); /* Creates a new rb-tree */ | |
61 | JRB make_jrb(void); /* Creates a new rb-tree */ | |
62 | 62 | |
63 | 63 | |
64 | 64 | /* Creates a node with key key and val val and inserts it into the tree. |
65 | 65 | jrb_insert uses strcmp() as comparison funcion. jrb_inserti uses <>=, |
66 | 66 | jrb_insertg uses func() */ |
67 | 67 | |
68 | extern JRB jrb_insert(JRB tree, void *key, void *val, | |
69 | int (*func)(const void *, const void *)); | |
68 | JRB jrb_insert(JRB tree, void *key, void *val, | |
69 | int (*func)(const void *a, const void *b)); | |
70 | 70 | |
71 | 71 | /* returns an external node in t whose value is equal k. Returns NULL if |
72 | 72 | there is no such node in the tree */ |
73 | 73 | |
74 | extern JRB jrb_find(JRB root, const void *, | |
75 | int (*func)(const void *, const void *)); | |
74 | JRB jrb_find(JRB root, const void *key, | |
75 | int (*func)(const void *a, const void *b)); | |
76 | 76 | |
77 | 77 | /* returns an external node in t whose value is equal |
78 | 78 | k or whose value is the smallest value greater than k. Sets found to |
79 | 79 | 1 if the key was found, and 0 otherwise. */ |
80 | 80 | |
81 | extern JRB jrb_find_gte(JRB root, const void *key, | |
82 | int (*func)(const void *, const void *), int *found); | |
81 | JRB jrb_find_gte(JRB root, const void *key, | |
82 | int (*func)(const void *a, const void *b), int *found); | |
83 | 83 | |
84 | 84 | |
85 | 85 | /* Creates a node with key key and val val and inserts it into the |
86 | 86 | tree before/after node nd. Does not check to ensure that you are |
87 | 87 | keeping the correct order */ |
88 | 88 | |
89 | extern void jrb_delete_node(JRB node); /* Deletes and frees a node (but | |
90 | not the key or val) */ | |
91 | extern void jrb_free_tree(JRB root); /* Deletes and frees an entire tree */ | |
89 | void jrb_delete_node(JRB node); /* Deletes and frees a node (but | |
90 | not the key or val) */ | |
91 | void jrb_free_tree(JRB root); /* Deletes and frees an entire tree */ | |
92 | 92 | |
93 | extern void *jrb_val(JRB node); /* Returns node->v.val -- this is to shut | |
94 | lint up */ | |
93 | void *jrb_val(JRB node); /* Returns node->v.val -- this is to shut | |
94 | lint up */ | |
95 | 95 | |
96 | extern int jrb_nblack(JRB n); /* returns # of black nodes in path from | |
97 | n to the root */ | |
96 | int jrb_nblack(JRB n); /* returns # of black nodes in path from | |
97 | n to the root */ | |
98 | 98 | int jrb_plength(JRB n); /* returns the # of nodes in path from |
99 | n to the root */ | |
99 | n to the root */ | |
100 | 100 | |
101 | 101 | #define jrb_first(n) ((n)->flink) |
102 | 102 | #define jrb_last(n) ((n)->blink) |
... | ... | |
108 | 108 | #endif |
109 | 109 | |
110 | 110 | #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)) | |
112 | 112 | |
113 | 113 | #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)) | |
115 | 115 | |
116 | 116 | #endif |
Branches:
master