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