Graphviz  2.41.20170921.2350
dtlist.c
Go to the documentation of this file.
1 #include "dthdr.h"
2 
3 /* List, Deque, Stack, Queue.
4 **
5 ** Written by Kiem-Phong Vo (05/25/96)
6 */
7 
8 static void* dtlist(reg Dt_t* dt, reg void* obj, reg int type)
9 {
10  reg int lk, sz, ky;
11  reg Dtcompar_f cmpf;
12  reg Dtdisc_t* disc;
13  reg Dtlink_t *r, *t;
14  reg void *key, *k;
15 
16  UNFLATTEN(dt);
17  disc = dt->disc; _DTDSC(disc,ky,sz,lk,cmpf);
18  dt->type &= ~DT_FOUND;
19 
20  if(!obj)
21  { if(type&(DT_LAST|DT_FIRST) )
22  { if((r = dt->data->head) )
23  { if(type&DT_LAST)
24  r = r->left;
25  dt->data->here = r;
26  }
27  return r ? _DTOBJ(r,lk) : NIL(void*);
28  }
29  else if(type&(DT_DELETE|DT_DETACH))
30  { if((dt->data->type&(DT_LIST|DT_DEQUE)) || !(r = dt->data->head))
31  return NIL(void*);
32  else goto dt_delete;
33  }
34  else if(type&DT_CLEAR)
35  { if(disc->freef || disc->link < 0)
36  { for(r = dt->data->head; r; r = t)
37  { t = r->right;
38  if(disc->freef)
39  (*disc->freef)(dt,_DTOBJ(r,lk),disc);
40  if(disc->link < 0)
41  (*dt->memoryf)(dt,(void*)r,0,disc);
42  }
43  }
44  dt->data->head = dt->data->here = NIL(Dtlink_t*);
45  dt->data->size = 0;
46  return NIL(void*);
47  }
48  else return NIL(void*);
49  }
50 
51  if(type&(DT_INSERT|DT_ATTACH))
52  { if(disc->makef && (type&DT_INSERT) &&
53  !(obj = (*disc->makef)(dt,obj,disc)) )
54  return NIL(void*);
55  if(lk >= 0)
56  r = _DTLNK(obj,lk);
57  else
58  { r = (Dtlink_t*)(*dt->memoryf)
59  (dt,NIL(void*),sizeof(Dthold_t),disc);
60  if(r)
61  ((Dthold_t*)r)->obj = obj;
62  else
63  { if(disc->makef && disc->freef && (type&DT_INSERT))
64  (*disc->freef)(dt,obj,disc);
65  return NIL(void*);
66  }
67  }
68 
69  if(dt->data->type&DT_DEQUE)
70  { if(type&DT_APPEND)
71  goto dt_queue;
72  else goto dt_stack;
73  }
74  else if(dt->data->type&DT_LIST)
75  { if(type&DT_APPEND)
76  { if(!(t = dt->data->here) || !t->right)
77  goto dt_queue;
78  r->right = t->right;
79  r->right->left = r;
80  r->left = t;
81  r->left->right = r;
82  }
83  else
84  { if(!(t = dt->data->here) || t == dt->data->head)
85  goto dt_stack;
86  r->left = t->left;
87  r->left->right = r;
88  r->right = t;
89  r->right->left = r;
90  }
91  }
92  else if(dt->data->type&DT_STACK)
93  { dt_stack:
94  r->right = t = dt->data->head;
95  if(t)
96  { r->left = t->left;
97  t->left = r;
98  }
99  else r->left = r;
100  dt->data->head = r;
101  }
102  else /* if(dt->data->type&DT_QUEUE) */
103  { dt_queue:
104  if((t = dt->data->head) )
105  { t->left->right = r;
106  r->left = t->left;
107  t->left = r;
108  }
109  else
110  { dt->data->head = r;
111  r->left = r;
112  }
113  r->right = NIL(Dtlink_t*);
114  }
115 
116  if(dt->data->size >= 0)
117  dt->data->size += 1;
118 
119  dt->data->here = r;
120  return _DTOBJ(r,lk);
121  }
122 
123  if((type&DT_MATCH) || !(r = dt->data->here) || _DTOBJ(r,lk) != obj)
124  { key = (type&DT_MATCH) ? obj : _DTKEY(obj,ky,sz);
125  for(r = dt->data->head; r; r = r->right)
126  { k = _DTOBJ(r,lk); k = _DTKEY(k,ky,sz);
127  if(_DTCMP(dt,key,k,disc,cmpf,sz) == 0)
128  break;
129  }
130  }
131 
132  if(!r)
133  return NIL(void*);
134  dt->type |= DT_FOUND;
135 
136  if(type&(DT_DELETE|DT_DETACH))
137  { dt_delete:
138  if(r->right)
139  r->right->left = r->left;
140  if(r == (t = dt->data->head) )
141  { dt->data->head = r->right;
142  if(dt->data->head)
143  dt->data->head->left = t->left;
144  }
145  else
146  { r->left->right = r->right;
147  if(r == t->left)
148  t->left = r->left;
149  }
150 
151  dt->data->here = r == dt->data->here ? r->right : NIL(Dtlink_t*);
152  dt->data->size -= 1;
153 
154  obj = _DTOBJ(r,lk);
155  if(disc->freef && (type&DT_DELETE))
156  (*disc->freef)(dt,obj,disc);
157  if(disc->link < 0)
158  (*dt->memoryf)(dt,(void*)r,0,disc);
159  return obj;
160  }
161  else if(type&DT_NEXT)
162  r = r->right;
163  else if(type&DT_PREV)
164  r = r == dt->data->head ? NIL(Dtlink_t*) : r->left;
165 
166  dt->data->here = r;
167  return r ? _DTOBJ(r,lk) : NIL(void*);
168 }
169 
170 #ifndef KPVDEL /* to be remove next round */
171 #define static
172 #endif
173 static Dtmethod_t _Dtlist = { dtlist, DT_LIST };
174 static Dtmethod_t _Dtdeque = { dtlist, DT_DEQUE };
175 static Dtmethod_t _Dtstack = { dtlist, DT_STACK };
176 static Dtmethod_t _Dtqueue = { dtlist, DT_QUEUE };
177 
179 Dtmethod_t* Dtdeque = &_Dtdeque;
182 
183 #ifdef NoF
184 NoF(dtlist)
185 #endif
int(* Dtcompar_f)(Dt_t *, void *, void *, Dtdisc_t *)
Definition: cdt.h:40
#define DT_CLEAR
Definition: cdt.h:146
#define DT_FIRST
Definition: cdt.h:147
#define reg
Definition: dthdr.h:14
CDT_API Dtmethod_t _Dtqueue
Definition: cdt.h:181
CDT_API Dtmethod_t * Dtstack
Definition: cdt.h:169
Definition: cdt.h:80
CDT_API Dtmethod_t _Dtstack
Definition: cdt.h:182
CDT_API Dtmethod_t _Dtlist
Definition: cdt.h:180
#define DT_APPEND
Definition: cdt.h:153
CDT_API Dtmethod_t * Dtdeque
Definition: cdt.h:171
CDT_API Dtmethod_t * Dtqueue
Definition: cdt.h:170
#define DT_DETACH
Definition: cdt.h:152
#define DT_PREV
Definition: cdt.h:144
#define DT_QUEUE
Definition: cdt.h:131
#define DT_FOUND
Definition: cdt.h:122
Definition: cdt.h:53
#define NIL(t)
Definition: dthdr.h:13
#define DT_NEXT
Definition: cdt.h:143
#define _DTDSC(dc, ky, sz, lk, cmpf)
Definition: cdt.h:205
#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_STACK
Definition: cdt.h:130
struct _dthold_s Dthold_t
Definition: cdt.h:29
#define DT_LIST
Definition: cdt.h:129
#define UNFLATTEN(dt)
Definition: dthdr.h:38
#define DT_MATCH
Definition: cdt.h:149
CDT_API Dtmethod_t * Dtlist
Definition: cdt.h:168
#define DT_INSERT
Definition: cdt.h:140
#define DT_LAST
Definition: cdt.h:148
#define left
Definition: dthdr.h:16
Definition: cdt.h:99
#define _DTKEY(o, ky, sz)
Definition: cdt.h:209
#define _DTOBJ(e, lk)
Definition: cdt.h:208
#define DT_DEQUE
Definition: cdt.h:132