1/***********************************************************************
2*                                                                      *
3*               This software is part of the ast package               *
4*          Copyright (c) 1985-2010 AT&T Intellectual Property          *
5*                      and is licensed under the                       *
6*                  Common Public License, Version 1.0                  *
7*                    by AT&T Intellectual Property                     *
8*                                                                      *
9*                A copy of the License is available at                 *
10*            http://www.opensource.org/licenses/cpl1.0.txt             *
11*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
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, Stack, Queue.
25**
26**	Written by Kiem-Phong Vo (05/25/96)
27*/
28
29#if __STD_C
30static Void_t* dtlist(reg Dt_t* dt, reg Void_t* obj, reg int type)
31#else
32static Void_t* dtlist(dt, obj, type)
33reg Dt_t*	dt;
34reg Void_t*	obj;
35reg int		type;
36#endif
37{
38	reg int		lk, sz, ky;
39	reg Dtcompar_f	cmpf;
40	reg Dtdisc_t*	disc;
41	reg Dtlink_t	*r, *t;
42	reg Void_t	*key, *k;
43
44	UNFLATTEN(dt);
45	disc = dt->disc; _DTDSC(disc,ky,sz,lk,cmpf);
46	dt->type &= ~DT_FOUND;
47
48	if(!obj)
49	{	if(type&(DT_LAST|DT_FIRST) )
50		{	if((r = dt->data->head) )
51			{	if(type&DT_LAST)
52					r = r->left;
53				dt->data->here = r;
54			}
55			return r ? _DTOBJ(r,lk) : NIL(Void_t*);
56		}
57		else if(type&(DT_DELETE|DT_DETACH))
58		{	if((dt->data->type&DT_LIST) || !(r = dt->data->head))
59				return NIL(Void_t*);
60			else	goto dt_delete;
61		}
62		else if(type&DT_CLEAR)
63		{	if(disc->freef || disc->link < 0)
64			{	for(r = dt->data->head; r; r = t)
65				{	t = r->right;
66					if(disc->freef)
67						(*disc->freef)(dt,_DTOBJ(r,lk),disc);
68					if(disc->link < 0)
69						(*dt->memoryf)(dt,(Void_t*)r,0,disc);
70				}
71			}
72			dt->data->head = dt->data->here = NIL(Dtlink_t*);
73			dt->data->size = 0;
74			return NIL(Void_t*);
75		}
76		else	return NIL(Void_t*);
77	}
78
79	if(type&(DT_INSERT|DT_ATTACH))
80	{	if(disc->makef && (type&DT_INSERT) &&
81		   !(obj = (*disc->makef)(dt,obj,disc)) )
82			return NIL(Void_t*);
83		if(lk >= 0)
84			r = _DTLNK(obj,lk);
85		else
86		{	r = (Dtlink_t*)(*dt->memoryf)
87				(dt,NIL(Void_t*),sizeof(Dthold_t),disc);
88			if(r)
89				((Dthold_t*)r)->obj = obj;
90			else
91			{	if(disc->makef && disc->freef && (type&DT_INSERT))
92					(*disc->freef)(dt,obj,disc);
93				return NIL(Void_t*);
94			}
95		}
96
97		if(dt->data->type&DT_LIST)
98		{	if((t = dt->data->here) && t != dt->data->head)
99			{	r->left = t->left;
100				t->left->right = r;
101				r->right = t;
102				t->left = r;
103			}
104			else	goto dt_stack;
105		}
106		else if(dt->data->type&DT_STACK)
107		{ dt_stack:
108			r->right = t = dt->data->head;
109			if(t)
110			{	r->left = t->left;
111				t->left = r;
112			}
113			else	r->left = r;
114			dt->data->head = r;
115		}
116		else /* if(dt->data->type&DT_QUEUE) */
117		{	if((t = dt->data->head) )
118			{	t->left->right = r;
119				r->left = t->left;
120				t->left = r;
121			}
122			else
123			{	dt->data->head = r;
124				r->left = r;
125			}
126			r->right = NIL(Dtlink_t*);
127		}
128
129		if(dt->data->size >= 0)
130			dt->data->size += 1;
131
132		dt->data->here = r;
133		return _DTOBJ(r,lk);
134	}
135
136	if((type&DT_MATCH) || !(r = dt->data->here) || _DTOBJ(r,lk) != obj)
137	{	key = (type&DT_MATCH) ? obj : _DTKEY(obj,ky,sz);
138		for(r = dt->data->head; r; r = r->right)
139		{	k = _DTOBJ(r,lk); k = _DTKEY(k,ky,sz);
140			if(_DTCMP(dt,key,k,disc,cmpf,sz) == 0)
141				break;
142		}
143	}
144
145	if(!r)
146		return NIL(Void_t*);
147	dt->type |= DT_FOUND;
148
149	if(type&(DT_DELETE|DT_DETACH))
150	{ dt_delete:
151		if(r->right)
152			r->right->left = r->left;
153		if(r == (t = dt->data->head) )
154		{	dt->data->head = r->right;
155			if(dt->data->head)
156				dt->data->head->left = t->left;
157		}
158		else
159		{	r->left->right = r->right;
160			if(r == t->left)
161				t->left = r->left;
162		}
163
164		dt->data->here = r == dt->data->here ? r->right : NIL(Dtlink_t*);
165		dt->data->size -= 1;
166
167		obj = _DTOBJ(r,lk);
168		if(disc->freef && (type&DT_DELETE))
169			(*disc->freef)(dt,obj,disc);
170		if(disc->link < 0)
171			(*dt->memoryf)(dt,(Void_t*)r,0,disc);
172		return obj;
173	}
174	else if(type&DT_NEXT)
175		r = r->right;
176	else if(type&DT_PREV)
177		r = r == dt->data->head ? NIL(Dtlink_t*) : r->left;
178
179	dt->data->here = r;
180	return r ? _DTOBJ(r,lk) : NIL(Void_t*);
181}
182
183#ifndef KPVDEL	/* to be remove next round */
184#define static
185#endif
186static Dtmethod_t _Dtlist  = { dtlist, DT_LIST  };
187static Dtmethod_t _Dtstack = { dtlist, DT_STACK };
188static Dtmethod_t _Dtqueue = { dtlist, DT_QUEUE };
189
190__DEFINE__(Dtmethod_t*,Dtlist,&_Dtlist);
191__DEFINE__(Dtmethod_t*,Dtstack,&_Dtstack);
192__DEFINE__(Dtmethod_t*,Dtqueue,&_Dtqueue);
193
194#ifdef NoF
195NoF(dtlist)
196#endif
197