1 /*******************************************************************************
2 *
3 * McStas, neutron ray-tracing package
4 * Copyright (C) 1997-2007, All rights reserved
5 * Risoe National Laboratory, Roskilde, Denmark
6 * Institut Laue Langevin, Grenoble, France
7 *
8 * Kernel: list.c
9 *
10 * %Identification
11 * Written by: K.N.
12 * Date: Jul 3, 1997
13 * Origin: Risoe
14 * Release: McStas X.Y.Z
15 * Version: $Revision$
16 *
17 * Implementation of lists.
18 *
19 *******************************************************************************/
20
21 #include "mccode.h"
22
23
24 /*******************************************************************************
25 * Implement lists of void pointers as an abstract data type, so that we can
26 * change to a better/different implementation at a later time.
27 *******************************************************************************/
28
29 /* The implementation of lists. Simple version: fixed-size array. */
30 struct List_header
31 {
32 int size;
33 int maxsize;
34 void **elements;
35 };
36
37 #define MAX_ELEMENTS 500000
38
39 /* Position in a list for doing list traversals. */
40 struct List_position
41 {
42 struct List_header *list; /* The list we are traversing. */
43 int index; /* Next element to return. */
44 };
45
46
47 /*******************************************************************************
48 * Create a new list.
49 *******************************************************************************/
50 List
list_create(void)51 list_create(void)
52 {
53 List l;
54
55 palloc(l);
56 l->maxsize = MAX_ELEMENTS;
57 nalloc(l->elements, l->maxsize);
58 l->size = 0;
59 return l;
60 }
61
62
63 /*******************************************************************************
64 * Add an element to a list, adding at the end.
65 *******************************************************************************/
66 void
list_add(List l,void * e)67 list_add(List l, void *e)
68 {
69 int i;
70
71 /* Check if there is room for the new element. */
72 if(l->size >= l->maxsize)
73 fatal_error("list_add: List too small (%d).", MAX_ELEMENTS);
74
75 i = l->size;
76 l->size++;
77 l->elements[i] = e;
78 }
79
80
81 /*******************************************************************************
82 * Delete a list and deallocate memory. Caller must supply a function that
83 * frees the list elements.
84 *******************************************************************************/
85
86 void
list_free(List l,void (* freer)(void *))87 list_free(List l, void (*freer)(void *))
88 {
89 int i;
90
91 for(i = 0; i < l->size; i++)
92 {
93 (*freer)(l->elements[i]);
94 }
95 memfree(l->elements);
96 memfree(l);
97 }
98
99
100 /*******************************************************************************
101 * Get the length of (number of elements in) a list.
102 *******************************************************************************/
103 int
list_len(List l)104 list_len(List l)
105 {
106 return l->size;
107 }
108
109
110 /*******************************************************************************
111 * Prepare to start traversing a list.
112 *******************************************************************************/
113 List_handle
list_iterate(List l)114 list_iterate(List l)
115 {
116 List_handle lh;
117
118 palloc(lh);
119 lh->list = l;
120 lh->index = 0;
121 return lh;
122 }
123
124
125 /*******************************************************************************
126 * Get the next element during a traversal of a list. Returns NULL when no
127 * more elements exist in the list.
128 *******************************************************************************/
129 void *
list_next(List_handle lh)130 list_next(List_handle lh)
131 {
132 if (!lh) return(NULL);
133 /* Check if there are any more elements */
134 if(lh->index >= lh->list->size)
135 {
136 return NULL;
137 }
138 else
139 {
140 int i = lh->index;
141 lh->index++;
142 return lh->list->elements[i];
143 }
144 }
145
146
147 /*******************************************************************************
148 * End a list traversal, freeing the memory allocated to the handle.
149 *******************************************************************************/
150 void
list_iterate_end(List_handle lh)151 list_iterate_end(List_handle lh)
152 {
153 memfree(lh);
154 }
155
156 /*******************************************************************************
157 * Catenate list2 to list1
158 *******************************************************************************/
list_cat(List l1,List l2)159 List list_cat(List l1, List l2)
160 {
161 List_handle liter;
162 void* litem;
163 liter = list_iterate(l2);
164 while(litem = list_next(liter))
165 list_add(l1, litem);
166 list_iterate_end(liter);
167 return(l1);
168 }
169