2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
6 * These libraries and programs are free software; you can
7 * redistribute them and/or modify them under the terms of the GNU
8 * Lesser General Public License as published by the Free Software
9 * Foundation; either version 2 of the License, or (at your option)
12 * These libraries and programs are distributed in the hope that
13 * they will be useful, but WITHOUT ANY WARRANTY; without even the
14 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 * PURPOSE. See the GNU Lesser General Public License for more
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with these librararies and programs; if not, write
20 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
21 * Floor, Boston, MA 02110-1301 USA
23 /* $XConsortium: list.c /main/4 1995/11/09 12:45:31 rswiston $ */
25 * (c) Copyright 1993, 1994 Hewlett-Packard Company
26 * (c) Copyright 1993, 1994 International Business Machines Corp.
27 * (c) Copyright 1993, 1994 Novell, Inc.
28 * (c) Copyright 1993, 1994 Sun Microsystems, Inc.
31 #include <EUSCompat.h>
34 #include <sys/param.h>
42 _DtCmsEnumerateProc enumerate;
43 _DtCmsCompareProc compare;
48 hc_lookup_node (Hc_list *hc_list, caddr_t key)
51 register List_node *p_node;
52 register _DtCmsComparisonResult result;
54 p_node = hc_list->root;
55 private = (Private *) hc_list->private;
56 while (p_node != NULL)
58 result = private->compare (key, p_node->data);
59 if (result == _DtCmsIsGreater)
61 p_node = hc_lookup_next (p_node);
63 else if (result == _DtCmsIsEqual)
76 hc_lookup (Hc_list *hc_list, caddr_t key)
80 p_node = hc_lookup_node (hc_list, key);
82 return ((caddr_t) p_node->data);
87 hc_size (Hc_list *hc_list)
90 register List_node *p_node;
92 p_node = hc_list->root;
93 while (p_node != NULL)
96 p_node = hc_lookup_next (p_node);
103 hc_create(_DtCmsGetKeyProc get, _DtCmsCompareProc compare)
106 List_node *root = NULL;
109 p = (Private *) calloc (1, sizeof (*p));
111 list = (Hc_list *) calloc (1, sizeof (*list));
113 list->private = (caddr_t) p;
117 p->compare = compare;
123 hc_destroy(Hc_list *hc_list, Destroy_proc destroy_func)
126 List_node *p_node, *p_next;
130 if ((p = (Private *) hc_list->private) != NULL)
133 p_node = hc_list->root;
134 while (p_node != NULL)
136 p_next = hc_lookup_next(p_node);
137 if (p_node->data != NULL)
140 destroy_func(p_node->data);
148 hc_insert_node (Hc_list *hc_list, register List_node *p_node, caddr_t key)
151 register List_node *p_curr;
155 private = (Private *) hc_list->private;
157 p_curr = hc_list->root;
158 while (p_curr != NULL)
160 if (private->compare (key, p_curr->data) == _DtCmsIsGreater)
162 if (p_curr->rlink != NULL)
163 p_curr = p_curr->rlink;
166 /* Insert at end of the list */
167 p_curr->rlink = p_node;
168 p_node->llink = p_curr;
174 /* Insert at head of the list */
175 if ((p_node->llink = p_curr->llink) == NULL)
178 /* Insert before the current node */
179 p_curr->llink = p_node->llink->rlink = p_node;
180 p_node->rlink = p_curr;
185 /* Insert at head of the list */
186 p_node->rlink = hc_list->root;
187 if (p_node->rlink != NULL)
188 p_node->rlink->llink = p_node;
189 hc_list->root = p_node;
206 p_node = (List_node *) calloc (1, sizeof(*p_node));
209 stat = hc_insert_node (hc_list, p_node, key);
211 if (stat == rb_ok && node_r)
218 hc_delete_node (Hc_list *hc_list, List_node *p_node)
220 if (p_node->llink == NULL)
221 hc_list->root = p_node->rlink;
223 p_node->llink->rlink = p_node->rlink;
224 if (p_node->rlink != NULL)
225 p_node->rlink->llink = p_node->llink;
230 hc_delete (Hc_list *hc_list, caddr_t key)
232 register List_node *p_node;
233 register Private *private;
235 p_node = hc_list->root;
236 private = (Private *) hc_list->private;
237 while (p_node != NULL)
239 if (private->compare (key, p_node->data) == _DtCmsIsEqual)
241 (void) hc_delete_node (hc_list, p_node);
244 p_node = hc_lookup_next(p_node);
250 hc_lookup_smallest (Hc_list *hc_list)
252 if ((hc_list == NULL) || (hc_list->root == NULL))
254 return ((caddr_t) hc_list->root->data);
258 hc_lookup_next_larger (Hc_list *hc_list, caddr_t key)
260 register List_node *p_node;
261 register Private *private;
263 p_node = hc_list->root;
264 private = (Private *) hc_list->private;
265 while (p_node != NULL)
267 if (private->compare (key, p_node->data) == _DtCmsIsLess)
268 return ((caddr_t) p_node->data);
269 p_node = hc_lookup_next(p_node);
275 hc_lookup_largest (Hc_list *hc_list)
277 register List_node *p_node;
279 if ((hc_list == NULL) || (hc_list->root == NULL))
282 p_node = hc_list->root;
283 while (p_node->rlink != NULL)
284 p_node = hc_lookup_next (p_node);
285 return ((caddr_t) p_node->data);
289 hc_lookup_next_smaller (Hc_list *hc_list, caddr_t key)
291 register List_node *p_node;
292 register Private *private;
294 p_node = hc_list->root;
295 private = (Private *) hc_list->private;
296 while (p_node != NULL)
298 if (private->compare (key, p_node->data) != _DtCmsIsGreater)
300 if (p_node->llink == NULL)
303 return ((caddr_t) p_node->llink->data);
305 p_node = hc_lookup_next(p_node);
311 hc_check_list (Hc_list *hc_list)
313 if ((hc_list == NULL) || (hc_list->root == NULL))
320 hc_enumerate_down(Hc_list *hc_list, _DtCmsEnumerateProc doit)
322 register List_node *p_node;
324 p_node = hc_list->root;
325 while (p_node != NULL)
327 if (doit ((caddr_t)p_node, p_node->data))
329 p_node = p_node->llink;
334 hc_enumerate_up(Hc_list *hc_list, _DtCmsEnumerateProc doit)
336 register List_node *p_node;
338 p_node = hc_list->root;
339 while (p_node != NULL)
341 if (doit ((caddr_t)p_node, p_node->data))
343 p_node = hc_lookup_next (p_node);