Debian Codegraph @

dune/uggrid/parallel/ddd/xfer/sll.ct

raw
1 // SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root
2 // SPDX-License-Identifier: LGPL-2.1-or-later
3 /****************************************************************************/
4 /* */
5 /* File: sll.ct */
6 /* */
7 /* Purpose: template routines for linked lists with freelist */
8 /* */
9 /* Author: Klaus Birken */
10 /* Institut fuer Computeranwendungen III */
11 /* Universitaet Stuttgart */
12 /* Pfaffenwaldring 27 */
13 /* 70569 Stuttgart */
14 /* internet: [email protected] */
15 /* */
16 /* History: 960826 kb created */
17 /* 970303 kb added memory management in segms */
18 /* */
19 /* Remarks: */
20 /* */
21 /****************************************************************************/
22
23
24
25 /****************************************************************************/
26 /* */
27 /* definition of exported global variables */
28 /* */
29 /****************************************************************************/
30
31 /* segment of items */
32 struct Segm(T)
33 {
34 Segm(T) *next;
35 int nItems;
36
37 T item[SEGM_SIZE];
38 };
39
40 /****************************************************************************/
41 /* */
42 /* routines */
43 /* */
44 /****************************************************************************/
45
46
47 static Segm(T) *NewSegm(T) (DDD::DDDContext& context)
48 {
49 auto& ctx = context.xferContext();
50 Segm(T) *segm;
51
52 segm = (Segm(T) *) OO_Allocate (sizeof(Segm(T)));
53 if (segm==NULL)
54 {
55 DDD_PrintError('F', 6060, STR_NOMEM " during XferEnd()");
56 return(NULL);
57 }
58
59 segm->next = reinterpret_cast<Segm(T)*>(ctx.segms(T));
60 ctx.segms(T) = reinterpret_cast<DDD::Xfer::Segm(T)*>(segm);
61 segm->nItems = 0;
62
63 return(segm);
64 }
65
66
67 static void FreeSegms(T) (DDD::DDDContext& context)
68 {
69 auto& ctx = context.xferContext();
70 Segm(T) *segm = reinterpret_cast<Segm(T)*>(ctx.segms(T));
71 Segm(T) *next = NULL;
72
73 while (segm!=NULL)
74 {
75 next = segm->next;
76 OO_Free (segm /*,sizeof(Segm(T))*/ );
77
78 segm = next;
79 }
80
81 ctx.segms(T) = nullptr;
82 }
83
84
85
86 T *New(T) (DDD::DDDContext& context)
87 {
88 auto& ctx = context.xferContext();
89 Segm(T) *segm = reinterpret_cast<Segm(T)*>(ctx.segms(T));
90 T *item;
91
92 if (segm==NULL || segm->nItems==SEGM_SIZE)
93 {
94 segm = NewSegm(T) (context);
95 if (segm==NULL)
96 return(NULL);
97 }
98
99 item = &(segm->item[segm->nItems++]);
100
101
102 /* insert item into linked list and count it */
103 item->sll_next = reinterpret_cast<T*>(ctx.list(T));
104 ctx.list(T) = reinterpret_cast<DDD::Xfer::T*>(item);
105 ctx.n(T)++;
106
107 #ifdef SLL_WithOrigOrder
108 /* insert unique counter */
109 item->sll_n = ctx.n(T);
110 #endif
111
112 return(item);
113 }
114
115
116
117
118 /*
119 create pointer array from linked list and sort it
120 according to given comparison function compar().
121 */
122
123 T **SortedArray(T) (DDD::DDDContext& context, int (*compar) (const void *, const void *))
124 {
125 auto& ctx = context.xferContext();
126 T **array;
127
128 if (ctx.n(T)>0)
129 {
130 /* alloc array */
131 array = (T **) OO_Allocate(sizeof(T *) * ctx.n(T));
132 if (array==NULL)
133 {
134 DDD_PrintError('F', 6061, STR_NOMEM " during XferEnd()");
135 return(NULL);
136 }
137
138 /* fill array with pointer */
139 int i = 0;
140 for (T* item = reinterpret_cast<T*>(ctx.list(T));
141 i < ctx.n(T);
142 item = item->sll_next, i++)
143 {
144 array[i] = item;
145 }
146
147 /* sort by using compar function */
148 if (ctx.n(T)>1)
149 qsort(array, ctx.n(T), sizeof(T *), compar);
150 }
151 else
152 {
153 array = NULL;
154 }
155
156 return(array);
157 }
158
159
160
161 /****************************************************************************/
162
163 #ifdef SLL_WithOrigOrder
164
165 /*
166 sort array of items into order of their New(T) command
167 execution. the counter-component T.n is used for doing
168 this.
169 */
170
171 static int sort_OrigOrder(T) (const void *e1, const void *e2)
172 {
173 T *item1 = *((T **)e1);
174 T *item2 = *((T **)e2);
175
176 if (item1->sll_n < item2->sll_n) return(-1);
177 if (item1->sll_n > item2->sll_n) return(1);
178 return(0);
179 }
180
181
182 void OrigOrder(T) (DDD::DDDContext& context, T **array, int n)
183 {
184 qsort(array, n, sizeof(T *), sort_OrigOrder(T));
185 }
186
187 #endif
188
189
190
191 /****************************************************************************/
192
193
194 /*
195 unify array of items. the array is compressed, the
196 resulting number of valid items is returned.
197 compar() is a comparison function which returns
198 whether two items are equal or not.
199
200 compar(a,b) should return
201 FALSE if a should be skipped and eventually b could be chosen
202 TRUE if a must be taken.
203
204 the array of items must be sorted in order to
205 allow compar() to decide correctly.
206 */
207
208 int Unify(T) (const DDD::DDDContext& context, T **array, int (*compar) (const DDD::DDDContext&, T **, T **))
209 {
210 const auto& ctx = context.xferContext();
211 int i, cntValid;
212
213 for(i=0, cntValid=0; i<ctx.n(T)-1; i++)
214 {
215 /* test if unique */
216 if (compar(context, &array[i],&array[i+1]))
217 {
218 /* choose item */
219 array[cntValid] = array[i];
220 cntValid++;
221 }
222 /* else: skip item */
223 }
224
225 /* always choose last item */
226 if (ctx.n(T)>0)
227 {
228 array[cntValid] = array[ctx.n(T)-1];
229 cntValid++;
230 }
231
232 return(cntValid);
233 }
234
235
236
237 /****************************************************************************/
238
239
240 /*
241 init linked list
242 */
243 void Init(T) (DDD::DDDContext& context)
244 {
245 auto& ctx = context.xferContext();
246
247 ctx.list(T) = nullptr;
248 ctx.n(T) = 0;
249
250 ctx.segms(T) = nullptr;
251
252 /*
253 free(T) = NULL;
254 */
255 }
256
257
258
259 /*
260 free all items
261 */
262 void FreeAll(T) (DDD::DDDContext& context)
263 {
264 auto& ctx = context.xferContext();
265
266 ctx.list(T) = nullptr;
267 ctx.n(T) = 0;
268
269 FreeSegms(T) (context);
270 }
271
272
273 /*
274 get quantitative resource usage
275 */
276 void GetSizes(T) (const DDD::DDDContext& context, int *nSegms, int *nItems, size_t *alloc_mem, size_t *used_mem)
277 {
278 const auto& ctx = context.xferContext();
279 size_t allocated=0, used=0;
280 int ns=0, ni=0;
281 Segm(T) *segm;
282
283 for (segm=reinterpret_cast<Segm(T)*>(ctx.segms(T)); segm!=NULL; segm=segm->next)
284 {
285 /* count number of segments and number of items */
286 ns++;
287 ni+=segm->nItems;
288
289 /* compute memory usage */
290 allocated += sizeof(Segm(T));
291 used += (sizeof(Segm(T)) - (sizeof(T)*(SEGM_SIZE-segm->nItems)));
292 }
293
294 *nSegms = ns;
295 *nItems = ni;
296 *alloc_mem = allocated;
297 *used_mem = used;
298 }
299
300
301 /****************************************************************************/
302
303 #ifdef SLL_WithOrigOrder
304 #undef SLL_WithOrigOrder
305 #endif
306
307 /****************************************************************************/
308