This source file includes following definitions.
- gl_sublist_nx_create_empty
- gl_sublist_nx_create_fill
- gl_sublist_size
- gl_sublist_node_value
- gl_sublist_node_nx_set_value
- gl_sublist_next_node
- gl_sublist_previous_node
- gl_sublist_first_node
- gl_sublist_last_node
- gl_sublist_get_at
- gl_sublist_nx_set_at
- gl_sublist_search_from_to
- gl_sublist_indexof_from_to
- gl_sublist_nx_add_first
- gl_sublist_nx_add_last
- gl_sublist_nx_add_before
- gl_sublist_nx_add_after
- gl_sublist_nx_add_at
- gl_sublist_remove_node
- gl_sublist_remove_at
- gl_sublist_remove
- gl_sublist_list_free
- gl_sublist_iterator
- gl_sublist_iterator_from_to
- gl_sublist_iterator_next
- gl_sublist_iterator_free
- gl_sublist_sortedlist_search
- gl_sublist_sortedlist_search_from_to
- gl_sublist_sortedlist_indexof
- gl_sublist_sortedlist_indexof_from_to
- gl_sublist_sortedlist_nx_add
- gl_sublist_sortedlist_remove
- gl_sublist_nx_create
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 #include <config.h>
19
20
21 #include "gl_sublist.h"
22
23 #include <stdint.h>
24 #include <stdlib.h>
25
26
27
28
29 struct gl_list_impl
30 {
31 struct gl_list_impl_base base;
32
33 gl_list_t whole;
34
35 size_t start;
36 size_t end;
37 };
38
39
40
41
42
43 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1)
44 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
45
46 static gl_list_t
47 gl_sublist_nx_create_empty (gl_list_implementation_t implementation,
48 gl_listelement_equals_fn equals_fn,
49 gl_listelement_hashcode_fn hashcode_fn,
50 gl_listelement_dispose_fn dispose_fn,
51 bool allow_duplicates)
52 {
53
54 abort ();
55 }
56
57 static gl_list_t
58 gl_sublist_nx_create_fill (gl_list_implementation_t implementation,
59 gl_listelement_equals_fn equals_fn,
60 gl_listelement_hashcode_fn hashcode_fn,
61 gl_listelement_dispose_fn dispose_fn,
62 bool allow_duplicates,
63 size_t count, const void **contents)
64 {
65
66 abort ();
67 }
68
69 static size_t
70 gl_sublist_size (gl_list_t list)
71 {
72 return list->end - list->start;
73 }
74
75 static const void *
76 gl_sublist_node_value (gl_list_t list, gl_list_node_t node)
77 {
78 uintptr_t index = NODE_TO_INDEX (node);
79 if (!(index < list->end - list->start))
80
81 abort ();
82 return gl_list_get_at (list->whole, list->start + index);
83 }
84
85 static int
86 gl_sublist_node_nx_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
87 {
88 uintptr_t index = NODE_TO_INDEX (node);
89 if (!(index < list->end - list->start))
90
91 abort ();
92 if (gl_list_nx_set_at (list->whole, list->start + index, elt) == NULL)
93 return -1;
94 return 0;
95 }
96
97 static gl_list_node_t
98 gl_sublist_next_node (gl_list_t list, gl_list_node_t node)
99 {
100 uintptr_t index = NODE_TO_INDEX (node);
101 size_t count = list->end - list->start;
102 if (!(index < count))
103
104 abort ();
105 index++;
106 if (index < count)
107 return INDEX_TO_NODE (index);
108 else
109 return NULL;
110 }
111
112 static gl_list_node_t
113 gl_sublist_previous_node (gl_list_t list, gl_list_node_t node)
114 {
115 uintptr_t index = NODE_TO_INDEX (node);
116 if (!(index < list->end - list->start))
117
118 abort ();
119 if (index > 0)
120 return INDEX_TO_NODE (index - 1);
121 else
122 return NULL;
123 }
124
125 static gl_list_node_t
126 gl_sublist_first_node (gl_list_t list)
127 {
128 if (list->end > list->start)
129 return INDEX_TO_NODE (0);
130 else
131 return NULL;
132 }
133
134 static gl_list_node_t
135 gl_sublist_last_node (gl_list_t list)
136 {
137 size_t count = list->end - list->start;
138 if (count > 0)
139 return INDEX_TO_NODE (count - 1);
140 else
141 return NULL;
142 }
143
144 static const void *
145 gl_sublist_get_at (gl_list_t list, size_t position)
146 {
147 if (!(position < list->end - list->start))
148
149 abort ();
150 return gl_list_get_at (list->whole, list->start + position);
151 }
152
153 static gl_list_node_t
154 gl_sublist_nx_set_at (gl_list_t list, size_t position, const void *elt)
155 {
156 if (!(position < list->end - list->start))
157
158 abort ();
159 if (gl_list_nx_set_at (list->whole, list->start + position, elt) == NULL)
160 return NULL;
161 return INDEX_TO_NODE (position);
162 }
163
164 static gl_list_node_t
165 gl_sublist_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
166 const void *elt)
167 {
168 if (!(start_index <= end_index && end_index <= list->end - list->start))
169
170 abort ();
171 {
172 size_t index =
173 gl_list_indexof_from_to (list->whole,
174 list->start + start_index,
175 list->start + end_index,
176 elt);
177 if (index != (size_t)(-1))
178 return INDEX_TO_NODE (index - list->start);
179 else
180 return NULL;
181 }
182 }
183
184 static size_t
185 gl_sublist_indexof_from_to (gl_list_t list,
186 size_t start_index, size_t end_index,
187 const void *elt)
188 {
189 if (!(start_index <= end_index && end_index <= list->end - list->start))
190
191 abort ();
192 {
193 size_t index =
194 gl_list_indexof_from_to (list->whole,
195 list->start + start_index,
196 list->start + end_index,
197 elt);
198 if (index != (size_t)(-1))
199 index -= list->start;
200 return index;
201 }
202 }
203
204 static gl_list_node_t
205 gl_sublist_nx_add_first (gl_list_t list, const void *elt)
206 {
207 if (gl_list_nx_add_at (list->whole, list->start, elt) == NULL)
208 return NULL;
209 list->end++;
210 return INDEX_TO_NODE (0);
211 }
212
213 static gl_list_node_t
214 gl_sublist_nx_add_last (gl_list_t list, const void *elt)
215 {
216 if (gl_list_nx_add_at (list->whole, list->end, elt) == NULL)
217 return NULL;
218 list->end++;
219 return INDEX_TO_NODE (list->end - list->start - 1);
220 }
221
222 static gl_list_node_t
223 gl_sublist_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
224 {
225 size_t position = NODE_TO_INDEX (node);
226 if (!(position < list->end - list->start))
227
228 abort ();
229 if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL)
230 return NULL;
231 list->end++;
232 return INDEX_TO_NODE (position);
233 }
234
235 static gl_list_node_t
236 gl_sublist_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
237 {
238 size_t position = NODE_TO_INDEX (node);
239 if (!(position < list->end - list->start))
240
241 abort ();
242 position++;
243 if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL)
244 return NULL;
245 list->end++;
246 return INDEX_TO_NODE (position);
247 }
248
249 static gl_list_node_t
250 gl_sublist_nx_add_at (gl_list_t list, size_t position, const void *elt)
251 {
252 if (!(position <= list->end - list->start))
253
254 abort ();
255 if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL)
256 return NULL;
257 list->end++;
258 return INDEX_TO_NODE (position);
259 }
260
261 static bool
262 gl_sublist_remove_node (gl_list_t list, gl_list_node_t node)
263 {
264 uintptr_t index = NODE_TO_INDEX (node);
265 if (!(index < list->end - list->start))
266
267 abort ();
268 return gl_list_remove_at (list->whole, list->start + index);
269 }
270
271 static bool
272 gl_sublist_remove_at (gl_list_t list, size_t position)
273 {
274 if (!(position < list->end - list->start))
275
276 abort ();
277 return gl_list_remove_at (list->whole, list->start + position);
278 }
279
280 static bool
281 gl_sublist_remove (gl_list_t list, const void *elt)
282 {
283 size_t position =
284 gl_list_indexof_from_to (list->whole, list->start, list->end, elt);
285 if (position == (size_t)(-1))
286 return false;
287 else
288 return gl_list_remove_at (list->whole, position);
289 }
290
291 static void
292 gl_sublist_list_free (gl_list_t list)
293 {
294 free (list);
295 }
296
297
298
299 static gl_list_iterator_t
300 gl_sublist_iterator (gl_list_t list)
301 {
302 return gl_list_iterator_from_to (list->whole, list->start, list->end);
303 }
304
305 static gl_list_iterator_t
306 gl_sublist_iterator_from_to (gl_list_t list,
307 size_t start_index, size_t end_index)
308 {
309 if (!(start_index <= end_index && end_index <= list->end - list->start))
310
311 abort ();
312 return gl_list_iterator_from_to (list->whole,
313 list->start + start_index,
314 list->start + end_index);
315 }
316
317 static bool
318 gl_sublist_iterator_next (gl_list_iterator_t *iterator,
319 const void **eltp, gl_list_node_t *nodep)
320 {
321
322 abort ();
323 }
324
325 static void
326 gl_sublist_iterator_free (gl_list_iterator_t *iterator)
327 {
328
329 abort ();
330 }
331
332
333
334 static gl_list_node_t
335 gl_sublist_sortedlist_search (gl_list_t list,
336 gl_listelement_compar_fn compar,
337 const void *elt)
338 {
339 size_t index =
340 gl_sortedlist_indexof_from_to (list->whole, compar,
341 list->start, list->end, elt);
342 if (index != (size_t)(-1))
343 return INDEX_TO_NODE (index - list->start);
344 else
345 return NULL;
346 }
347
348 static gl_list_node_t
349 gl_sublist_sortedlist_search_from_to (gl_list_t list,
350 gl_listelement_compar_fn compar,
351 size_t low, size_t high,
352 const void *elt)
353 {
354 size_t index;
355
356 if (!(low <= high && high <= list->end - list->start))
357
358 abort ();
359
360 index =
361 gl_sortedlist_indexof_from_to (list->whole, compar,
362 list->start + low, list->start + high, elt);
363 if (index != (size_t)(-1))
364 return INDEX_TO_NODE (index - list->start);
365 else
366 return NULL;
367 }
368
369 static size_t
370 gl_sublist_sortedlist_indexof (gl_list_t list,
371 gl_listelement_compar_fn compar,
372 const void *elt)
373 {
374 size_t index =
375 gl_sortedlist_indexof_from_to (list->whole, compar, list->start, list->end,
376 elt);
377 if (index != (size_t)(-1))
378 index -= list->start;
379 return index;
380 }
381
382 static size_t
383 gl_sublist_sortedlist_indexof_from_to (gl_list_t list,
384 gl_listelement_compar_fn compar,
385 size_t low, size_t high,
386 const void *elt)
387 {
388 size_t index;
389
390 if (!(low <= high && high <= list->end - list->start))
391
392 abort ();
393
394 index = gl_sortedlist_indexof_from_to (list->whole, compar,
395 list->start + low, list->start + high,
396 elt);
397 if (index != (size_t)(-1))
398 index -= list->start;
399 return index;
400 }
401
402 static gl_list_node_t
403 gl_sublist_sortedlist_nx_add (gl_list_t list,
404 gl_listelement_compar_fn compar,
405 const void *elt)
406 {
407
408
409
410 abort ();
411 }
412
413 static bool
414 gl_sublist_sortedlist_remove (gl_list_t list,
415 gl_listelement_compar_fn compar,
416 const void *elt)
417 {
418 size_t index = gl_sublist_sortedlist_indexof (list, compar, elt);
419 if (index == (size_t)(-1))
420 return false;
421 else
422 return gl_sublist_remove_at (list, index);
423 }
424
425
426 static const struct gl_list_implementation gl_sublist_list_implementation =
427 {
428 gl_sublist_nx_create_empty,
429 gl_sublist_nx_create_fill,
430 gl_sublist_size,
431 gl_sublist_node_value,
432 gl_sublist_node_nx_set_value,
433 gl_sublist_next_node,
434 gl_sublist_previous_node,
435 gl_sublist_first_node,
436 gl_sublist_last_node,
437 gl_sublist_get_at,
438 gl_sublist_nx_set_at,
439 gl_sublist_search_from_to,
440 gl_sublist_indexof_from_to,
441 gl_sublist_nx_add_first,
442 gl_sublist_nx_add_last,
443 gl_sublist_nx_add_before,
444 gl_sublist_nx_add_after,
445 gl_sublist_nx_add_at,
446 gl_sublist_remove_node,
447 gl_sublist_remove_at,
448 gl_sublist_remove,
449 gl_sublist_list_free,
450 gl_sublist_iterator,
451 gl_sublist_iterator_from_to,
452 gl_sublist_iterator_next,
453 gl_sublist_iterator_free,
454 gl_sublist_sortedlist_search,
455 gl_sublist_sortedlist_search_from_to,
456 gl_sublist_sortedlist_indexof,
457 gl_sublist_sortedlist_indexof_from_to,
458 gl_sublist_sortedlist_nx_add,
459 gl_sublist_sortedlist_remove
460 };
461
462 gl_list_t
463 gl_sublist_nx_create (gl_list_t whole_list, size_t start_index, size_t end_index)
464 {
465 if (!(start_index <= end_index && end_index <= gl_list_size (whole_list)))
466
467 abort ();
468 {
469 struct gl_list_impl *list =
470 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
471
472 if (list == NULL)
473 return NULL;
474
475 list->base.vtable = &gl_sublist_list_implementation;
476 list->base.equals_fn = whole_list->base.equals_fn;
477 list->base.hashcode_fn = whole_list->base.hashcode_fn;
478 list->base.dispose_fn = whole_list->base.dispose_fn;
479 list->base.allow_duplicates = whole_list->base.allow_duplicates;
480 if (whole_list->base.vtable == &gl_sublist_list_implementation)
481 {
482
483
484 list->whole = whole_list->whole;
485 list->start = whole_list->start + start_index;
486 list->end = whole_list->start + end_index;
487 }
488 else
489 {
490 list->whole = whole_list;
491 list->start = start_index;
492 list->end = end_index;
493 }
494
495 return list;
496 }
497 }