xref: /titanic_41/usr/src/lib/libast/common/cdt/dtlist.c (revision 3e14f97f673e8a630f076077de35afdd43dc1587)
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
dtlist(reg Dt_t * dt,reg Void_t * obj,reg int type)30 static Void_t* dtlist(reg Dt_t* dt, reg Void_t* obj, reg int type)
31 #else
32 static Void_t* dtlist(dt, obj, type)
33 reg Dt_t*	dt;
34 reg Void_t*	obj;
35 reg 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
186 static Dtmethod_t _Dtlist  = { dtlist, DT_LIST  };
187 static Dtmethod_t _Dtstack = { dtlist, DT_STACK };
188 static 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
195 NoF(dtlist)
196 #endif
197