1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1985-2012 AT&T Intellectual Property *
5 * and is licensed under the *
6 * Eclipse Public License, Version 1.0 *
7 * by AT&T Intellectual Property *
8 * *
9 * A copy of the License is available at *
10 * http://www.eclipse.org/org/documents/epl-v10.html *
11 * (with md5 checksum b35adb5213ca9657e911e9befb180842) *
12 * *
13 * Information and Software Systems Research *
14 * AT&T Research *
15 * Florham Park NJ *
16 * *
17 * Glenn Fowler <gsf@research.att.com> *
18 * David Korn <dgk@research.att.com> *
19 * Phong Vo <kpv@research.att.com> *
20 * *
21 ***********************************************************************/
22 #include "dthdr.h"
23
24 /* List, Deque, Stack, Queue.
25 **
26 ** Written by Kiem-Phong Vo (05/25/96)
27 */
28
29 typedef struct _dtlist_s
30 { Dtdata_t data;
31 Dtlink_t* link; /* list of objects */
32 Dtlink_t* here; /* finger to searched objects */
33 } Dtlist_t;
34
35 #ifdef DEBUG
dtlistprint(Dt_t * dt,Dtlink_t * here,char * (* objprintf)(Void_t *))36 int dtlistprint(Dt_t* dt, Dtlink_t* here, char* (*objprintf)(Void_t*) )
37 {
38 int k;
39 char *obj, *endb, buf[1024];
40 Dtdisc_t *disc = dt->disc;
41 Dtlist_t *list = (Dtlist_t*)dt->data;
42
43 if(!here && !(here = list->link) )
44 return -1;
45
46 for(; here; here = here->_rght)
47 { endb = buf; /* indentation */
48 *endb++ = '(';
49 obj = (*objprintf)(_DTOBJ(disc, here));
50 k = strlen(obj); memcpy(endb, obj, k); endb += k;
51 *endb++ = ')';
52 *endb++ = '\n';
53 write(2, buf, endb-buf);
54 }
55
56 return 0;
57 }
58 #endif
59
60 /* terminal objects: DT_FIRST|DT_LAST */
61 #if __STD_C
lfirstlast(Dt_t * dt,int type)62 Void_t* lfirstlast(Dt_t* dt, int type)
63 #else
64 Void_t* lfirstlast(dt, type)
65 Dt_t* dt;
66 int type;
67 #endif
68 {
69 Dtlink_t *lnk;
70 Dtdisc_t *disc = dt->disc;
71 Dtlist_t *list = (Dtlist_t*)dt->data;
72
73 if((lnk = list->link) )
74 { if(type&DT_LAST)
75 lnk = lnk->_left;
76 list->here = lnk; /* finger points to this */
77 }
78
79 return lnk ? _DTOBJ(disc,lnk) : NIL(Void_t*);
80 }
81
82 /* DT_CLEAR */
83 #if __STD_C
lclear(Dt_t * dt)84 Void_t* lclear(Dt_t* dt)
85 #else
86 Void_t* lclear(dt)
87 Dt_t* dt;
88 #endif
89 {
90 Dtlink_t *lnk, *next;
91 Dtdisc_t *disc = dt->disc;
92 Dtlist_t *list = (Dtlist_t*)dt->data;
93
94 lnk = list->link;
95 list->link = list->here = NIL(Dtlink_t*);
96 list->data.size = 0;
97
98 if(disc->freef || disc->link < 0)
99 { for(; lnk; lnk = next)
100 { next = lnk->_rght;
101 _dtfree(dt, lnk, DT_DELETE);
102 }
103 }
104
105 return NIL(Void_t*);
106 }
107
108 /* DT_FLATTEN|DT_EXTRACT|DT_RESTORE */
109 #if __STD_C
llist(Dt_t * dt,Dtlink_t * lnk,int type)110 Void_t* llist(Dt_t* dt, Dtlink_t* lnk, int type)
111 #else
112 Void_t* llist(dt, lnk, type)
113 Dt_t* dt;
114 Dtlink_t* lnk;
115 int type;
116 #endif
117 {
118 Dtlist_t *list = (Dtlist_t*)dt->data;
119
120 if(type&(DT_FLATTEN|DT_EXTRACT) )
121 { if(lnk) /* error on calling */
122 return NIL(Void_t*);
123
124 lnk = list->link;
125 if(type&DT_EXTRACT)
126 { list->link = NIL(Dtlink_t*);
127 dt->data->size = 0;
128 }
129 }
130 else /* if(type&DT_RESTORE) */
131 { if(list->link != NIL(Dtlink_t*))
132 return NIL(Void_t*);
133
134 list->link = lnk;
135
136 dt->data->size = 0;
137 for(; lnk; lnk = lnk->_rght)
138 dt->data->size += 1;
139 }
140
141 return (Void_t*)lnk;
142 }
143
144 #if __STD_C
liststat(Dt_t * dt,Dtstat_t * st)145 static Void_t* liststat(Dt_t* dt, Dtstat_t* st)
146 #else
147 static Void_t* liststat(dt, st)
148 Dt_t* dt;
149 Dtstat_t* st;
150 #endif
151 {
152 if(st)
153 { memset(st, 0, sizeof(Dtstat_t));
154 st->meth = dt->meth->type;
155 st->size = dt->data->size;
156 st->space = sizeof(Dtlist_t) + (dt->disc->link >= 0 ? 0 : dt->data->size*sizeof(Dthold_t));
157 }
158
159 return (Void_t*)dt->data->size;
160 }
161
162 #if __STD_C
dtlist(Dt_t * dt,Void_t * obj,int type)163 static Void_t* dtlist(Dt_t* dt, Void_t* obj, int type)
164 #else
165 static Void_t* dtlist(dt, obj, type)
166 Dt_t* dt;
167 Void_t* obj;
168 int type;
169 #endif
170 {
171 Dtlink_t *r, *t, *h;
172 Void_t *key, *o, *k;
173 Dtdisc_t *disc = dt->disc;
174 Dtlist_t *list = (Dtlist_t*)dt->data;
175
176 type = DTTYPE(dt,type); /* map type for upward compatibility */
177 if(!(type&DT_OPERATIONS) )
178 return NIL(Void_t*);
179
180 DTSETLOCK(dt);
181
182 if(type&(DT_FIRST|DT_LAST) )
183 DTRETURN(obj, lfirstlast(dt, type));
184 else if(type&(DT_EXTRACT|DT_RESTORE|DT_FLATTEN) )
185 DTRETURN(obj, llist(dt, (Dtlink_t*)obj, type));
186 else if(type&DT_CLEAR)
187 DTRETURN(obj, lclear(dt));
188 else if(type&DT_STAT )
189 DTRETURN(obj, liststat(dt, (Dtstat_t*)obj));
190
191 h = list->here; /* save finger to last search object */
192 list->here = NIL(Dtlink_t*);
193
194 if(!obj)
195 { if((type&(DT_DELETE|DT_DETACH|DT_REMOVE)) && (dt->meth->type&(DT_STACK|DT_QUEUE)) )
196 if((r = list->link) ) /* special case for destack or dequeue */
197 goto dt_delete;
198 DTRETURN(obj, NIL(Void_t*)); /* error, needing non-void object */
199 }
200
201 if(type&DT_RELINK) /* relink object after some processing */
202 { r = (Dtlink_t*)obj;
203 goto do_insert;
204 }
205 else if(type&(DT_INSERT|DT_APPEND|DT_ATTACH))
206 { if(!(r = _dtmake(dt, obj, type)) )
207 DTRETURN(obj, NIL(Void_t*));
208 dt->data->size += 1;
209
210 do_insert:
211 if(dt->meth->type&DT_DEQUE)
212 { if(type&DT_APPEND)
213 goto dt_queue; /* append at end */
214 else goto dt_stack; /* insert at top */
215 }
216 else if(dt->meth->type&DT_LIST)
217 { if(type&DT_APPEND)
218 { if(!h || !h->_rght)
219 goto dt_queue;
220 r->_rght = h->_rght;
221 r->_rght->_left = r;
222 r->_left = h;
223 r->_left->_rght = r;
224 }
225 else
226 { if(!h || h == list->link )
227 goto dt_stack;
228 r->_left = h->_left;
229 r->_left->_rght = r;
230 r->_rght = h;
231 r->_rght->_left = r;
232 }
233 }
234 else if(dt->meth->type&DT_STACK)
235 { dt_stack:
236 r->_rght = t = list->link;
237 if(t)
238 { r->_left = t->_left;
239 t->_left = r;
240 }
241 else r->_left = r;
242 list->link = r;
243 }
244 else /* if(dt->meth->type&DT_QUEUE) */
245 { dt_queue:
246 if((t = list->link) )
247 { t->_left->_rght = r;
248 r->_left = t->_left;
249 t->_left = r;
250 }
251 else
252 { list->link = r;
253 r->_left = r;
254 }
255 r->_rght = NIL(Dtlink_t*);
256 }
257
258 list->here = r;
259 DTRETURN(obj, _DTOBJ(disc,r));
260 }
261
262 /* define key to match */
263 if(type&DT_MATCH)
264 { key = obj;
265 obj = NIL(Void_t*);
266 }
267 else key = _DTKEY(disc, obj);
268
269 /* try to find a matching object */
270 if(h && _DTOBJ(disc,h) == obj && (type & (DT_SEARCH|DT_NEXT|DT_PREV)) )
271 r = h; /* match at the finger, no search needed */
272 else /* linear search through the list */
273 { h = NIL(Dtlink_t*); /* track first/last obj with same key */
274 for(r = list->link; r; r = r->_rght)
275 { o = _DTOBJ(disc,r); k = _DTKEY(disc,o);
276 if(_DTCMP(dt, key, k, disc) != 0)
277 continue;
278 else if(type & (DT_REMOVE|DT_NEXT|DT_PREV) )
279 { if(o == obj) /* got exact object, done */
280 break;
281 else if(type&DT_NEXT) /* track last object */
282 h = r;
283 else if(type&DT_PREV) /* track first object */
284 h = h ? h : r;
285 else continue;
286 }
287 else if(type & DT_ATLEAST )
288 h = r; /* track last object */
289 else break;
290 }
291 r = h ? h : r;
292 }
293 if(!r)
294 DTRETURN(obj, NIL(Void_t*));
295
296 if(type&(DT_DELETE|DT_DETACH|DT_REMOVE))
297 { dt_delete:
298 if(r->_rght)
299 r->_rght->_left = r->_left;
300 if(r == (t = list->link) )
301 { list->link = r->_rght;
302 if((h = list->link) )
303 h->_left = t->_left;
304 }
305 else
306 { r->_left->_rght = r->_rght;
307 if(r == t->_left)
308 t->_left = r->_left;
309 }
310
311 list->here = r == list->here ? r->_rght : NIL(Dtlink_t*);
312
313 obj = _DTOBJ(disc,r);
314 _dtfree(dt, r, type);
315 dt->data->size -= 1;
316
317 DTRETURN(obj, obj);
318 }
319
320 if(type&DT_NEXT)
321 r = r->_rght;
322 else if(type&DT_PREV)
323 r = r == list->link ? NIL(Dtlink_t*) : r->_left;
324 /* else: if(type&(DT_SEARCH|DT_MATCH|DT_ATLEAST|DT_ATMOST)) */
325
326 list->here = r;
327 if(r)
328 DTRETURN(obj, _DTOBJ(disc,r));
329 else DTRETURN(obj, NIL(Void_t*));
330
331 dt_return:
332 DTANNOUNCE(dt,obj,type);
333 DTCLRLOCK(dt);
334 return obj;
335 }
336
337 #if __STD_C
listevent(Dt_t * dt,int event,Void_t * arg)338 static int listevent(Dt_t* dt, int event, Void_t* arg)
339 #else
340 static int listevent(dt, event, arg)
341 Dt_t* dt;
342 int event;
343 Void_t* arg;
344 #endif
345 {
346 Dtlist_t *list = (Dtlist_t*)dt->data;
347
348 if(event == DT_OPEN)
349 { if(list) /* already initialized */
350 return 0;
351 if(!(list = (Dtlist_t*)(*dt->memoryf)(dt, 0, sizeof(Dtlist_t), dt->disc)) )
352 { DTERROR(dt, "Error in allocating a list data structure");
353 return -1;
354 }
355 memset(list, 0, sizeof(Dtlist_t));
356 dt->data = (Dtdata_t*)list;
357 return 1;
358 }
359 else if(event == DT_CLOSE)
360 { if(!list) /* already closed */
361 return 0;
362 if(list->link) /* remove all items */
363 (void)lclear(dt);
364 (void)(*dt->memoryf)(dt, (Void_t*)list, 0, dt->disc);
365 dt->data = NIL(Dtdata_t*);
366 return 0;
367 }
368 else return 0;
369 }
370
371 static Dtmethod_t _Dtlist = { dtlist, DT_LIST, listevent, "Dtlist" };
372 static Dtmethod_t _Dtdeque = { dtlist, DT_DEQUE, listevent, "Dtdeque" };
373 static Dtmethod_t _Dtstack = { dtlist, DT_STACK, listevent, "Dtstack" };
374 static Dtmethod_t _Dtqueue = { dtlist, DT_QUEUE, listevent, "Dtqueue" };
375
376 __DEFINE__(Dtmethod_t*,Dtlist,&_Dtlist);
377 __DEFINE__(Dtmethod_t*,Dtdeque,&_Dtdeque);
378 __DEFINE__(Dtmethod_t*,Dtstack,&_Dtstack);
379 __DEFINE__(Dtmethod_t*,Dtqueue,&_Dtqueue);
380
381 #ifdef NoF
382 NoF(dtlist)
383 #endif
384