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