Graphviz 14.1.2~dev.20260118.1035
Loading...
Searching...
No Matches
dttree.c
Go to the documentation of this file.
1#include "config.h"
2
3#include <cdt/dthdr.h>
4#include <stdlib.h>
5
6/* Ordered set/multiset
7** dt: dictionary being searched
8** obj: the object to look for.
9** type: search type.
10**
11** Written by Kiem-Phong Vo (5/25/96)
12*/
13
14static void* dttree(Dt_t* dt, void* obj, int type)
15{
16 Dtlink_t *root, *t;
17 int cmp, lk, sz, ky;
18 void *o, *k, *key;
19 Dtlink_t *l, *r, *me = NULL, link;
20 Dtcompar_f cmpf;
21 Dtdisc_t* disc;
22
23 UNFLATTEN(dt);
24 disc = dt->disc; _DTDSC(disc,ky,sz,lk,cmpf);
25
26 root = dt->data.here;
27 if(!obj)
28 { if(!root || !(type&(DT_CLEAR|DT_FIRST|DT_LAST)) )
29 return NULL;
30
31 if(type&DT_CLEAR) /* delete all objects */
32 { if(disc->freef || disc->link < 0)
33 { do
34 { while((t = root->left) )
35 RROTATE(root,t);
36 t = root->right;
37 if(disc->freef)
38 disc->freef(_DTOBJ(root, lk));
39 if(disc->link < 0)
40 free(root);
41 } while((root = t) );
42 }
43
44 dt->data.size = 0;
45 dt->data.here = NULL;
46 return NULL;
47 }
48 else /* computing largest/smallest element */
49 { if(type&DT_LAST)
50 { while((t = root->right) )
51 LROTATE(root,t);
52 }
53 else /* type&DT_FIRST */
54 { while((t = root->left) )
55 RROTATE(root,t);
56 }
57
58 dt->data.here = root;
59 return _DTOBJ(root,lk);
60 }
61 }
62
63 /* note that link.right is LEFT tree and link.left is RIGHT tree */
64 l = r = &link;
65
66 /* allow apps to delete an object "actually" in the dictionary */
67 if(dt->meth->type == DT_OBAG && (type&(DT_DELETE|DT_DETACH)) )
68 { key = _DTKEY(obj,ky,sz);
69 for(o = dtsearch(dt,obj); o; o = dtnext(dt,o) )
70 { k = _DTKEY(o,ky,sz);
71 if(_DTCMP(key, k, cmpf, sz) != 0)
72 break;
73 if(o == obj)
74 { root = dt->data.here;
75 l->right = root->left;
76 r->left = root->right;
77 goto dt_delete;
78 }
79 }
80 }
81
82 if(type&(DT_MATCH|DT_SEARCH|DT_INSERT))
83 { key = (type&DT_MATCH) ? obj : _DTKEY(obj,ky,sz);
84 if(root)
85 goto do_search;
86 }
87 else if(type&DT_RENEW)
88 { me = obj;
89 obj = _DTOBJ(me,lk);
90 key = _DTKEY(obj,ky,sz);
91 if(root)
92 goto do_search;
93 }
94 else if(root && _DTOBJ(root,lk) != obj)
95 { key = _DTKEY(obj,ky,sz);
96 do_search:
97 while(1)
98 { k = _DTOBJ(root,lk); k = _DTKEY(k,ky,sz);
99 if((cmp = _DTCMP(key, k, cmpf, sz)) == 0)
100 break;
101 else if(cmp < 0)
102 { if((t = root->left) )
103 { k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
104 if((cmp = _DTCMP(key, k, cmpf, sz)) < 0)
105 { rrotate(root,t);
106 rlink(r,t);
107 if(!(root = t->left) )
108 break;
109 }
110 else if(cmp == 0)
111 { rlink(r,root);
112 root = t;
113 break;
114 }
115 else /* if(cmp > 0) */
116 { llink(l,t);
117 rlink(r,root);
118 if(!(root = t->right) )
119 break;
120 }
121 }
122 else
123 { rlink(r,root);
124 root = NULL;
125 break;
126 }
127 }
128 else /* if(cmp > 0) */
129 { if((t = root->right) )
130 { k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
131 if((cmp = _DTCMP(key, k, cmpf, sz)) > 0)
132 { lrotate(root,t);
133 llink(l,t);
134 if(!(root = t->right) )
135 break;
136 }
137 else if(cmp == 0)
138 { llink(l,root);
139 root = t;
140 break;
141 }
142 else /* if(cmp < 0) */
143 { rlink(r,t);
144 llink(l,root);
145 if(!(root = t->left) )
146 break;
147 }
148 }
149 else
150 { llink(l,root);
151 root = NULL;
152 break;
153 }
154 }
155 }
156 }
157
158 if(root)
159 { /* found it, now isolate it */
160 l->right = root->left;
161 r->left = root->right;
162
163 if(type&(DT_SEARCH|DT_MATCH))
164 { has_root:
165 root->left = link.right;
166 root->right = link.left;
167 if((dt->meth->type&DT_OBAG) && (type&(DT_SEARCH|DT_MATCH)) )
168 { key = _DTOBJ(root,lk); key = _DTKEY(key,ky,sz);
169 while((t = root->left) )
170 { /* find max of left subtree */
171 while((r = t->right) )
172 LROTATE(t,r);
173 root->left = t;
174
175 /* now see if it's in the same group */
176 k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
177 if(_DTCMP(key, k, cmpf, sz) != 0)
178 break;
179 RROTATE(root,t);
180 }
181 }
182 dt->data.here = root;
183 return _DTOBJ(root,lk);
184 }
185 else if(type&DT_NEXT)
186 { root->left = link.right;
187 root->right = NULL;
188 link.right = root;
189 dt_next:
190 if((root = link.left) )
191 { while((t = root->left) )
192 RROTATE(root,t);
193 link.left = root->right;
194 goto has_root;
195 }
196 else goto no_root;
197 }
198 else if(type&DT_PREV)
199 { root->right = link.left;
200 root->left = NULL;
201 link.left = root;
202 dt_prev:
203 if((root = link.right) )
204 { while((t = root->right) )
205 LROTATE(root,t);
206 link.right = root->left;
207 goto has_root;
208 }
209 else goto no_root;
210 }
211 else if(type&(DT_DELETE|DT_DETACH))
212 { /* taking an object out of the dictionary */
213 dt_delete:
214 obj = _DTOBJ(root,lk);
215 if(disc->freef && (type&DT_DELETE))
216 disc->freef(obj);
217 if(disc->link < 0)
218 free(root);
219 if (--dt->data.size < 0)
220 --dt->data.size;
221 goto no_root;
222 }
223 else if(type&DT_INSERT)
224 { if(dt->meth->type&DT_OSET)
225 goto has_root;
226 else
227 { root->left = NULL;
228 root->right = link.left;
229 link.left = root;
230 goto dt_insert;
231 }
232 }
233 else if(type&DT_RENEW) /* a duplicate */
234 { if(dt->meth->type&DT_OSET)
235 { if(disc->freef)
236 disc->freef(obj);
237 if(disc->link < 0)
238 free(me);
239 }
240 else
241 { me->left = NULL;
242 me->right = link.left;
243 link.left = me;
244 ++dt->data.size;
245 }
246 goto has_root;
247 }
248 }
249 else
250 { /* not found, finish up LEFT and RIGHT trees */
251 r->left = NULL;
252 l->right = NULL;
253
254 if(type&DT_NEXT)
255 goto dt_next;
256 else if(type&DT_PREV)
257 goto dt_prev;
258 else if(type&(DT_SEARCH|DT_MATCH))
259 { no_root:
260 while((t = r->left) )
261 r = t;
262 r->left = link.right;
263 dt->data.here = link.left;
264 return (type&DT_DELETE) ? obj : NULL;
265 }
266 else if(type&DT_INSERT)
267 { dt_insert:
268 if(disc->makef && (type&DT_INSERT))
269 obj = disc->makef(obj, disc);
270 if(obj)
271 { if(lk >= 0)
272 root = _DTLNK(obj,lk);
273 else
274 { root = malloc(sizeof(Dthold_t));
275 if(root)
276 ((Dthold_t*)root)->obj = obj;
277 else if(disc->makef && disc->freef &&
278 (type&DT_INSERT))
279 disc->freef(obj);
280 }
281 }
282 if(root)
283 { if (dt->data.size >= 0)
284 ++dt->data.size;
285 goto has_root;
286 }
287 else goto no_root;
288 }
289 else if(type&DT_RENEW)
290 { root = me;
291 ++dt->data.size;
292 goto has_root;
293 }
294 else /*if(type&DT_DELETE)*/
295 { obj = NULL;
296 goto no_root;
297 }
298 }
299
300 return NULL;
301}
302
303/* make this method available */
304static Dtmethod_t Dtoset_ = { dttree, DT_OSET };
305static Dtmethod_t Dtobag_ = { dttree, DT_OBAG };
306Dtmethod_t* Dtoset = &Dtoset_;
307Dtmethod_t* Dtobag = &Dtobag_;
308
309static Dtmethod_t Dttree_ = { dttree, DT_OSET };
310Dtmethod_t* Dttree = &Dttree_;
DT_MATCH
#define DT_MATCH
Definition cdt.h:134
_DTKEY
#define _DTKEY(o, ky, sz)
Definition cdt.h:169
_DTDSC
#define _DTDSC(dc, ky, sz, lk, cmpf)
Definition cdt.h:164
DT_LAST
#define DT_LAST
Definition cdt.h:133
DT_OBAG
#define DT_OBAG
Definition cdt.h:121
DT_PREV
#define DT_PREV
Definition cdt.h:129
_DTLNK
#define _DTLNK(o, lk)
Definition cdt.h:166
DT_NEXT
#define DT_NEXT
Definition cdt.h:128
Dtcompar_f
int(* Dtcompar_f)(void *, void *)
Definition cdt.h:48
DT_SEARCH
#define DT_SEARCH
Definition cdt.h:127
dtsearch
#define dtsearch(d, o)
Definition cdt.h:184
DT_DELETE
#define DT_DELETE
Definition cdt.h:126
DT_CLEAR
#define DT_CLEAR
Definition cdt.h:131
DT_INSERT
#define DT_INSERT
Definition cdt.h:125
DT_DETACH
#define DT_DETACH
Definition cdt.h:136
DT_RENEW
#define DT_RENEW
Definition cdt.h:130
DT_OSET
#define DT_OSET
Definition cdt.h:120
_DTCMP
#define _DTCMP(k1, k2, cmpf, sz)
Definition cdt.h:172
_DTOBJ
#define _DTOBJ(e, lk)
Definition cdt.h:167
DT_FIRST
#define DT_FIRST
Definition cdt.h:132
dtnext
#define dtnext(d, o)
Definition cdt.h:181
cmpf
static int cmpf(void *key1, void *key2)
Definition dijkstra.c:84
RROTATE
#define RROTATE(x, y)
Definition dthdr.h:35
LROTATE
#define LROTATE(x, y)
Definition dthdr.h:36
rrotate
#define rrotate(x, y)
Definition dthdr.h:30
rlink
#define rlink(r, x)
Definition dthdr.h:32
llink
#define llink(l, x)
Definition dthdr.h:33
lrotate
#define lrotate(x, y)
Definition dthdr.h:31
UNFLATTEN
#define UNFLATTEN(dt)
Definition dthdr.h:27
Dttree
Dtmethod_t * Dttree
Definition dttree.c:310
dttree
static void * dttree(Dt_t *dt, void *obj, int type)
Definition dttree.c:14
Dtoset_
static Dtmethod_t Dtoset_
Definition dttree.c:304
Dtobag_
static Dtmethod_t Dtobag_
Definition dttree.c:305
Dtoset
Dtmethod_t * Dtoset
ordered set (self-adjusting tree)
Definition dttree.c:306
Dttree_
static Dtmethod_t Dttree_
Definition dttree.c:309
Dtobag
Dtmethod_t * Dtobag
ordered multiset
Definition dttree.c:307
disc
static Dtdisc_t disc
Definition exparse.y:209
type
expr procedure type
Definition exparse.y:208
cmp
static int cmp(const void *key, const void *candidate)
Definition frmobjectui.c:220
malloc
void * malloc(YYSIZE_T)
free
void free(void *)
NULL
node NULL
Definition grammar.y:181
Dtdata_t::size
int size
Definition cdt.h:79
Dtdata_t::here
Dtlink_t * here
Definition cdt.h:73
Dthold_t
Definition cdt.h:59
Dtmethod_t
Definition cdt.h:65
Dtmethod_t::type
int type
Definition cdt.h:67
dt_s_
Definition cdt.h:98
dt_s_::meth
Dtmethod_t * meth
Definition cdt.h:102
dt_s_::data
Dtdata_t data
sharable data
Definition cdt.h:101
dt_s_::disc
Dtdisc_t * disc
Definition cdt.h:100
dtdisc_s_
Definition cdt.h:84
dtdisc_s_::freef
Dtfree_f freef
Definition cdt.h:89
dtdisc_s_::link
int link
Definition cdt.h:87
dtdisc_s_::makef
Dtmake_f makef
Definition cdt.h:88
dtlink_s_
Definition cdt.h:50
dtlink_s_::right
Dtlink_t * right
Definition cdt.h:51