1 /*
2 * Motif
3 *
4 * Copyright (c) 1987-2012, The Open Group. All rights reserved.
5 *
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)
10 * any later version.
11 *
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
16 * details.
17 *
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
22 *
23 */
24
25 #include "xmlist.h"
26
27 /************************************************************
28 *
29 * Stack code.
30 *
31 ************************************************************/
32
33 #define STACK_INC 25
34
35 /************************************************************
36 *
37 * Stack Manipulation code.
38 *
39 ************************************************************/
40
41 /* Function Name: _XmStackInit
42 * Description: Initializes the stack.
43 * Arguments: none
44 * Returns: the stack
45 */
46
47 XmStack
_XmStackInit()48 _XmStackInit()
49 {
50 return((XmStack) XtCalloc(sizeof(XmStackRec), (Cardinal) 1));
51 }
52
53 /* Function Name: _XmStackFree
54 * Description: Frees all data associated with the stack.
55 * Arguments: stack - the stack
56 * Returns: none
57 */
58
59 void
_XmStackFree(XmStack stack)60 _XmStackFree(XmStack stack)
61 {
62 XtFree((XtPointer) stack->elems);
63 XtFree((XtPointer) stack);
64 }
65
66 /* Function Name: _XmStackPush
67 * Description: Pushes an element onto the stack
68 * Arguments: stack - the stack
69 * elem - element to push onto it.
70 * Returns: none
71 */
72
73 void
_XmStackPush(XmStack stack,XtPointer elem)74 _XmStackPush(XmStack stack, XtPointer elem)
75 {
76 if ((++stack->top) >= stack->alloc) {
77 stack->alloc += STACK_INC;
78 stack->elems =
79 (XtPointer *) XtRealloc((XtPointer) stack->elems,
80 sizeof(XtPointer) * stack->alloc);
81 }
82
83 stack->elems[stack->top] = elem;
84
85 #ifdef STACK_DEBUG
86 printf("Pushing %d as elem %d\n", (int) elem, stack->top);
87 #endif
88 }
89
90 /* Function Name: _XmStackPop
91 * Description: Pops an element off of the stack.
92 * Arguments: stack - stack to pop off of.
93 * Returns: elem - the element that has been popped.
94 */
95
96 XtPointer
_XmStackPop(XmStack stack)97 _XmStackPop(XmStack stack)
98 {
99 if (stack->top <= 0)
100 return(NULL); /* no elements on the stack. */
101
102 #ifdef STACK_DEBUG
103 printf("Popping %d from elem %d\n",
104 (int) stack->elems[stack->top], stack->top);
105 #endif
106
107 return(stack->elems[(stack->top)--]);
108 }
109
110 /************************************************************
111 *
112 * Queue code.
113 *
114 ************************************************************/
115
116 #ifdef QUEUE_DEBUG
117 #define QUEUE_INC 5
118 #else
119 #define QUEUE_INC 25
120 #endif
121
122 /************************************************************
123 *
124 * Queue Manipulation code.
125 *
126 ************************************************************/
127
128 /* Function Name: _XmQueueInit
129 * Description: Initializes the queue.
130 * Arguments: none
131 * Returns: the queue
132 */
133
134 XmQueue
_XmQueueInit()135 _XmQueueInit()
136 {
137 return((XmQueue) XtCalloc(sizeof(XmQueueRec), (Cardinal) 1));
138 }
139
140 /* Function Name: _XmQueueFree
141 * Description: Frees all data associated with the queue.
142 * Arguments: queue - the queue
143 * Returns: none
144 */
145
146 void
_XmQueueFree(XmQueue queue)147 _XmQueueFree(XmQueue queue)
148 {
149 int count;
150 _XmQElem *elem = queue->first;
151 XmStack stack = _XmStackInit();
152
153 for (count = 0; count < 2; count++) {
154 while (elem != NULL) {
155 if (elem->alloced)
156 _XmStackPush(stack, (XtPointer) elem);
157 elem = elem->next;
158 }
159
160 elem = queue->free_elems;
161 }
162
163 while ((elem = (_XmQElem *) _XmStackPop(stack)) != NULL)
164 XtFree((XtPointer) elem);
165
166 _XmStackFree(stack);
167
168 XtFree((XtPointer) queue);
169 }
170
171 /* Function Name: QueuePush
172 * Description: Pushes an element onto the queue
173 * Arguments: queue - the queue
174 * data_in - the data to push onto the queue.
175 * Returns: none
176 */
177
178 /*
179 * This is being removed because its name was not changed when compiled
180 * -DBX. This means that there is already a QueuePush() defined in the
181 * BX 3.1 bx.o, so integrating the EPak into BX causes multiply defined
182 * symbols. Luckily, this function is not currently used in EPak. We
183 * can remove this only when we don't support EPak integration into
184 * BX 3.0 or BX 3.1.
185 */
186
187 #ifdef notdef
188 void
QueuePush(XmQueue queue,XtPointer data_in)189 QueuePush(XmQueue queue, XtPointer data_in)
190 {
191 _XmQElem *elem = _Xm_GetNewElement(queue);
192
193 _Xm_AddQueue(queue, queue->last, elem);
194
195 if (queue->first == NULL)
196 queue->first = elem;
197
198 queue->last = elem;
199
200 elem->data = data_in;
201
202 #ifdef QUEUE_DEBUG
203 printf("Pushing %d\n", (int) data_in);
204 #endif
205 }
206 #endif
207
208 /* Function Name: _XmQueuePop
209 * Description: Pops an element off of the queue.
210 * Arguments: queue - queue to pop off of.
211 * Returns: elem - the element that has been popped.
212 */
213
214 XtPointer
_XmQueuePop(XmQueue queue)215 _XmQueuePop(XmQueue queue)
216 {
217 _XmQElem *first = _Xm_RemQueue(&queue->first);
218
219 if (queue->first == NULL)
220 queue->last = NULL;
221
222 if (first == NULL)
223 return(NULL);
224
225 _Xm_AddQueue(NULL, queue->free_elems, first);
226
227 #ifdef QUEUE_DEBUG
228 printf("Popping %d\n", (int) first->data);
229 #endif
230
231 return(first->data);
232 }
233
234 /* Function Name: _XmQueueCount
235 * Description: Returns the number of items in the queue
236 * Arguments: queue - queue to check.
237 * Returns: number of items in queue.
238 */
239
240
241 int
_XmQueueCount(XmQueue queue)242 _XmQueueCount(XmQueue queue)
243 {
244 register int i;
245 register _XmQElem *elem = queue->first;
246
247 for (i = 0; elem != NULL; i++)
248 elem = elem->next;
249
250 return(i);
251 }
252
253 /* Function Name: _XmQueuePrint
254 * Description: Prints out the real and free nodes of the queue.
255 * Arguments: queue - queue to print.
256 * Returns: none.
257 */
258
259
260 #ifdef QUEUE_DEBUG
261 void
_XmQueuePrint(XmQueue queue)262 _XmQueuePrint(XmQueue queue)
263 {
264 _XmQElem *elem;
265
266 printf("Elements:\n");
267 for (elem = queue->first; elem != NULL; elem = elem->next)
268 printf("Element - %d\n", elem->data);
269
270 printf("Reverse Elements:\n");
271 for (elem = queue->last; elem != NULL; elem = elem->prev)
272 printf("Element - %d\n", elem->data);
273
274 printf("Free Elements:\n");
275 for (elem = queue->free_elems; elem != NULL; elem = elem->next)
276 printf("Free Element - %d\n", elem->data);
277 }
278 #endif
279
280 /************************************************************
281 *
282 * Internal Used (Utils Lib) functions.
283 *
284 ************************************************************/
285
286 /* Function Name: _Xm_AddQueue
287 * Description: Adds an element to the queue, after the element specified.
288 * Arguments: queue - Queue to add to, if NULL then we may be adding
289 * to the free items list.
290 * after - the element is added after this one.
291 * elem - element to add.
292 * Returns: none.
293 */
294
295 void
_Xm_AddQueue(XmQueue queue,_XmQElem * after,_XmQElem * elem)296 _Xm_AddQueue(XmQueue queue, _XmQElem *after, _XmQElem *elem)
297 {
298 if (elem != NULL) {
299 elem->prev = after;
300 if (after == NULL)
301 /*
302 * If queue is NULL then this is being added to the
303 * free elements queue, and we make certain assumptions, like
304 * we are always adding to then end of the list, so that
305 * we never will try to add before the first element.
306 */
307 if (queue != NULL) {
308 elem->next = queue->first;
309 if (elem->next != NULL)
310 elem->next->prev = elem;
311 }
312 else
313 elem->next = NULL;
314 else
315 elem->next = after->next;
316 }
317
318 if (after != NULL) {
319 if (after->next != NULL)
320 after->next->prev = elem;
321 after->next = elem;
322 }
323
324 }
325
326 /* Function Name: _Xm_RemQueue
327 * Description: Removes the specified element form a queue, and sets
328 * the queue to point to the next element.
329 * Arguments: queue - the queue to remove it from.
330 * Returns: the element removed.
331 */
332
333 _XmQElem *
_Xm_RemQueue(_XmQElem ** queue)334 _Xm_RemQueue(_XmQElem ** queue)
335 {
336 _XmQElem * elem = *queue;
337
338 if (elem != NULL) {
339 *queue = elem->next;
340
341 if (elem->next != NULL)
342 elem->next->prev = elem->prev;
343
344 if (elem->prev != NULL)
345 elem->prev->next = elem->next;
346 }
347
348 return(elem);
349 }
350
351 /* Function Name: GetNewElement
352 * Description: Gets an element off the free_elems list, allocates
353 * more elems if necessary.
354 * Arguments: queue - the queue to get the element from.
355 * Returns: an element.
356 */
357
358 _XmQElem *
_Xm_GetNewElement(XmQueue queue)359 _Xm_GetNewElement(XmQueue queue)
360 {
361 _XmQElem *elem;
362
363 if ((elem = _Xm_RemQueue(&queue->free_elems)) == NULL) {
364 register int i;
365
366 /*
367 * We are out of free elements, alloc some more.
368 */
369
370 queue->free_elems = (_XmQElem *) XtCalloc(sizeof(_XmQElem), QUEUE_INC);
371 queue->free_elems->alloced = True;
372
373 queue->free_elems->next = elem = queue->free_elems + 1;
374 for (i = 1; i < (QUEUE_INC - 1); i++, elem++) {
375 elem->prev = elem - 1;
376 elem->next = elem + 1;
377 }
378 elem->prev = elem - 1;
379
380 /*
381 * Pop an element off the free elements queue.
382 */
383
384 elem = _Xm_RemQueue(&queue->free_elems);
385 }
386
387 return(elem);
388 }
389
390 /************************************************************
391 *
392 * List code.
393 *
394 ************************************************************/
395
396 /*
397 * This code is very dependant on the queue manipulation code, they
398 * are sharing much functionality, several of these functions are just
399 * wrappers around the queue maipulation code.
400 */
401
402 /* Function Name: _XmListInit
403 * Description: Initializes the list.
404 * Arguments: none
405 * Returns: the queue
406 */
407
408 XmList
_XmListInit()409 _XmListInit()
410 {
411 return((XmList) _XmQueueInit());
412 }
413
414 /* Function Name: _XmListFree
415 * Description: Frees all data associated with the list.
416 * Arguments: list - the list
417 * Returns: none
418 */
419
420 void
_XmListFree(XmList list)421 _XmListFree(XmList list)
422 {
423 _XmQueueFree((XmQueue) list);
424 }
425
426 /* Function Name: _XmListAddAfter
427 * Description: Adds an element after the specified element.
428 * Arguments: list - the list
429 * elem - The element to add this one after.
430 * If NULL then add this element to the beginning of
431 * the list
432 * data_in - the data to push onto the queue.
433 * Returns: The new added element.
434 */
435
436 XmListElem *
_XmListAddAfter(XmList list,XmListElem * elem_in,XtPointer data_in)437 _XmListAddAfter(XmList list, XmListElem *elem_in, XtPointer data_in)
438 {
439 XmListElem *elem = (XmListElem *) _Xm_GetNewElement((XmQueue) list);
440
441 _Xm_AddQueue((XmQueue) list, elem_in, elem);
442
443 if (elem_in == NULL)
444 list->first = elem;
445
446 if (elem_in == list->last)
447 list->last = elem;
448
449 elem->data = data_in;
450
451 return(elem);
452 }
453
454 /* Function Name: _XmListAddBefore
455 * Description: Adds an element before the specified element.
456 * Arguments: list - the list
457 * elem - The element to add this one before.
458 * If NULL then add this element to the end of
459 * the list.
460 * data_in - the data to push onto the queue.
461 * Returns: The new added element.
462 */
463
464 XmListElem *
_XmListAddBefore(XmList list,XmListElem * elem_in,XtPointer data_in)465 _XmListAddBefore(XmList list, XmListElem *elem_in, XtPointer data_in)
466 {
467 XmListElem *after;
468
469 if (elem_in == NULL)
470 after = list->last;
471 else
472 after = elem_in->prev;
473
474 return(_XmListAddAfter(list, after, data_in));
475 }
476
477 /* Function Name: _XmListRemove
478 * Description: Removes an element from the list.
479 * Arguments: list - the list to remove the element from.
480 * Returns: none.
481 */
482
483 void
_XmListRemove(XmList list,XmListElem * elem)484 _XmListRemove(XmList list, XmListElem *elem)
485 {
486 XmListElem *dead = (XmListElem *) _Xm_RemQueue((_XmQElem **) &elem);
487
488 /*
489 * if NULL is passed, then no action is taken.
490 */
491
492 if (dead == NULL)
493 return;
494
495 if (list->first == dead)
496 if ((list->first = dead->next) == NULL)
497 list->last = NULL;
498
499 if (list->last == dead)
500 if ((list->last = dead->prev) == NULL)
501 list->first = NULL;
502
503 _Xm_AddQueue(NULL, list->free_elems, (_XmQElem *) dead);
504 }
505
506 /* Function Name: _XmListCount
507 * Description: Returns the number of items in the list.
508 * Arguments: list - list to check.
509 * Returns: number of items in list.
510 */
511
512
513 int
_XmListCount(XmList list)514 _XmListCount(XmList list)
515 {
516 return(_XmQueueCount((XmQueue) list));
517 }
518
519 /* Function Name: _XmListExec
520 * Description: Executes a function on all nodes in the list.
521 * Arguments: list - the list to use.
522 * start - the element to start with.
523 * end - the element to end with.
524 * exec_func - the function to execute.
525 * data - data to pass to the function.
526 * Returns: NULL is returned if all items from start to end
527 * have been operated on. Otherwise the node in which
528 * the operation stopped is returned.
529 *
530 * NOTES: If start is NULL the start is the first element in the list.
531 * If end is NULL then all elements after start will be searched.
532 * The list is always executed if forward order from start ->
533 * start->next, start->next->next...
534 *
535 */
536
537 XmListElem *
_XmListExec(XmList list,XmListElem * start,XmListElem * end,XmListFunc func,XtPointer data)538 _XmListExec(XmList list, XmListElem *start, XmListElem *end,
539 XmListFunc func, XtPointer data)
540 {
541 if (start == NULL)
542 start = list->first;
543
544 for ( ; (start != end) && (start != NULL); start = start->next) {
545 if (!(*func)(start, data))
546 return(start);
547 }
548
549 return(NULL);
550 }
551
552 /* Function Name: _XmListPrint
553 * Description: Prints out the real and free nodes of the list.
554 * Arguments: list - list to print.
555 * Returns: none.
556 */
557
558
559 #ifdef QUEUE_DEBUG
560 void
_XmListPrint(XmList list)561 _XmListPrint(XmList list)
562 {
563 _XmQueuePrint((XmQueue) list);
564 }
565 #endif
566
567