1 /* Sequential list data type backed by another list.
2 Copyright (C) 2006-2008 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3 of the License, or
8 (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
21 #include "gl_sublist.h"
28 # define uintptr_t unsigned long
31 /* -------------------------- gl_list_t Data Type -------------------------- */
33 /* Concrete gl_list_impl type, valid for this file only. */
36 struct gl_list_impl_base base;
37 /* Reference to the whole list. */
39 /* Limits of the index range. */
44 /* struct gl_list_node_impl doesn't exist here. The pointers are actually
45 indices + 1. (We don't use the whole list's gl_list_node_t implementation,
46 because gl_sublist_next_node and gl_sublist_previous_node would not be easy
47 to implement with this choice.) */
48 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1)
49 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
52 gl_sublist_create_empty (gl_list_implementation_t implementation,
53 gl_listelement_equals_fn equals_fn,
54 gl_listelement_hashcode_fn hashcode_fn,
55 gl_listelement_dispose_fn dispose_fn,
56 bool allow_duplicates)
58 /* Shouldn't be called. */
63 gl_sublist_create_fill (gl_list_implementation_t implementation,
64 gl_listelement_equals_fn equals_fn,
65 gl_listelement_hashcode_fn hashcode_fn,
66 gl_listelement_dispose_fn dispose_fn,
67 bool allow_duplicates,
68 size_t count, const void **contents)
70 /* Shouldn't be called. */
75 gl_sublist_size (gl_list_t list)
77 return list->end - list->start;
81 gl_sublist_node_value (gl_list_t list, gl_list_node_t node)
83 uintptr_t index = NODE_TO_INDEX (node);
84 if (!(index < list->end - list->start))
85 /* Invalid argument. */
87 return gl_list_get_at (list->whole, list->start + index);
91 gl_sublist_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
93 uintptr_t index = NODE_TO_INDEX (node);
94 if (!(index < list->end - list->start))
95 /* Invalid argument. */
97 gl_list_set_at (list->whole, list->start + index, elt);
100 static gl_list_node_t
101 gl_sublist_next_node (gl_list_t list, gl_list_node_t node)
103 uintptr_t index = NODE_TO_INDEX (node);
104 size_t count = list->end - list->start;
105 if (!(index < count))
106 /* Invalid argument. */
110 return INDEX_TO_NODE (index);
115 static gl_list_node_t
116 gl_sublist_previous_node (gl_list_t list, gl_list_node_t node)
118 uintptr_t index = NODE_TO_INDEX (node);
119 if (!(index < list->end - list->start))
120 /* Invalid argument. */
123 return INDEX_TO_NODE (index - 1);
129 gl_sublist_get_at (gl_list_t list, size_t position)
131 if (!(position < list->end - list->start))
132 /* Invalid argument. */
134 return gl_list_get_at (list->whole, list->start + position);
137 static gl_list_node_t
138 gl_sublist_set_at (gl_list_t list, size_t position, const void *elt)
140 if (!(position < list->end - list->start))
141 /* Invalid argument. */
143 gl_list_set_at (list->whole, list->start + position, elt);
144 return INDEX_TO_NODE (position);
147 static gl_list_node_t
148 gl_sublist_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
151 if (!(start_index <= end_index && end_index <= list->end - list->start))
152 /* Invalid arguments. */
156 gl_list_indexof_from_to (list->whole,
157 list->start + start_index,
158 list->start + end_index,
160 if (index != (size_t)(-1))
161 return INDEX_TO_NODE (index - list->start);
168 gl_sublist_indexof_from_to (gl_list_t list,
169 size_t start_index, size_t end_index,
172 if (!(start_index <= end_index && end_index <= list->end - list->start))
173 /* Invalid arguments. */
177 gl_list_indexof_from_to (list->whole,
178 list->start + start_index,
179 list->start + end_index,
181 if (index != (size_t)(-1))
182 index -= list->start;
187 static gl_list_node_t
188 gl_sublist_add_first (gl_list_t list, const void *elt)
190 gl_list_add_at (list->whole, list->start, elt);
192 return INDEX_TO_NODE (0);
195 static gl_list_node_t
196 gl_sublist_add_last (gl_list_t list, const void *elt)
198 gl_list_add_at (list->whole, list->end, elt);
200 return INDEX_TO_NODE (list->end - list->start - 1);
203 static gl_list_node_t
204 gl_sublist_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
206 size_t position = NODE_TO_INDEX (node);
207 if (!(position < list->end - list->start))
208 /* Invalid argument. */
210 gl_list_add_at (list->whole, list->start + position, elt);
212 return INDEX_TO_NODE (position);
215 static gl_list_node_t
216 gl_sublist_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
218 size_t position = NODE_TO_INDEX (node);
219 if (!(position < list->end - list->start))
220 /* Invalid argument. */
223 gl_list_add_at (list->whole, list->start + position, elt);
225 return INDEX_TO_NODE (position);
228 static gl_list_node_t
229 gl_sublist_add_at (gl_list_t list, size_t position, const void *elt)
231 if (!(position <= list->end - list->start))
232 /* Invalid argument. */
234 gl_list_add_at (list->whole, list->start + position, elt);
236 return INDEX_TO_NODE (position);
240 gl_sublist_remove_node (gl_list_t list, gl_list_node_t node)
242 uintptr_t index = NODE_TO_INDEX (node);
243 if (!(index < list->end - list->start))
244 /* Invalid argument. */
246 return gl_list_remove_at (list->whole, list->start + index);
250 gl_sublist_remove_at (gl_list_t list, size_t position)
252 if (!(position < list->end - list->start))
253 /* Invalid argument. */
255 return gl_list_remove_at (list->whole, list->start + position);
259 gl_sublist_remove (gl_list_t list, const void *elt)
262 gl_list_indexof_from_to (list->whole, list->start, list->end, elt);
263 if (position == (size_t)(-1))
266 return gl_list_remove_at (list->whole, position);
270 gl_sublist_list_free (gl_list_t list)
275 /* --------------------- gl_list_iterator_t Data Type --------------------- */
277 static gl_list_iterator_t
278 gl_sublist_iterator (gl_list_t list)
280 return gl_list_iterator_from_to (list->whole, list->start, list->end);
283 static gl_list_iterator_t
284 gl_sublist_iterator_from_to (gl_list_t list,
285 size_t start_index, size_t end_index)
287 if (!(start_index <= end_index && end_index <= list->end - list->start))
288 /* Invalid arguments. */
290 return gl_list_iterator_from_to (list->whole,
291 list->start + start_index,
292 list->start + end_index);
296 gl_sublist_iterator_next (gl_list_iterator_t *iterator,
297 const void **eltp, gl_list_node_t *nodep)
299 /* Shouldn't be called. */
304 gl_sublist_iterator_free (gl_list_iterator_t *iterator)
306 /* Shouldn't be called. */
310 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
312 static gl_list_node_t
313 gl_sublist_sortedlist_search (gl_list_t list,
314 gl_listelement_compar_fn compar,
318 gl_sortedlist_indexof_from_to (list->whole, compar,
319 list->start, list->end, elt);
320 if (index != (size_t)(-1))
321 return INDEX_TO_NODE (index - list->start);
326 static gl_list_node_t
327 gl_sublist_sortedlist_search_from_to (gl_list_t list,
328 gl_listelement_compar_fn compar,
329 size_t low, size_t high,
334 if (!(low <= high && high <= list->end - list->start))
335 /* Invalid arguments. */
339 gl_sortedlist_indexof_from_to (list->whole, compar,
340 list->start + low, list->start + high, elt);
341 if (index != (size_t)(-1))
342 return INDEX_TO_NODE (index - list->start);
348 gl_sublist_sortedlist_indexof (gl_list_t list,
349 gl_listelement_compar_fn compar,
353 gl_sortedlist_indexof_from_to (list->whole, compar, list->start, list->end,
355 if (index != (size_t)(-1))
356 index -= list->start;
361 gl_sublist_sortedlist_indexof_from_to (gl_list_t list,
362 gl_listelement_compar_fn compar,
363 size_t low, size_t high,
368 if (!(low <= high && high <= list->end - list->start))
369 /* Invalid arguments. */
372 index = gl_sortedlist_indexof_from_to (list->whole, compar,
373 list->start + low, list->start + high,
375 if (index != (size_t)(-1))
376 index -= list->start;
380 static gl_list_node_t
381 gl_sublist_sortedlist_add (gl_list_t list,
382 gl_listelement_compar_fn compar,
385 /* It's impossible to implement this method without risking to put the
386 whole list into unsorted order (namely, when the given ELT is smaller
387 or larger than all elements of the sublist). */
392 gl_sublist_sortedlist_remove (gl_list_t list,
393 gl_listelement_compar_fn compar,
396 size_t index = gl_sublist_sortedlist_indexof (list, compar, elt);
397 if (index == (size_t)(-1))
400 return gl_sublist_remove_at (list, index);
404 static const struct gl_list_implementation gl_sublist_list_implementation =
406 gl_sublist_create_empty,
407 gl_sublist_create_fill,
409 gl_sublist_node_value,
410 gl_sublist_node_set_value,
411 gl_sublist_next_node,
412 gl_sublist_previous_node,
415 gl_sublist_search_from_to,
416 gl_sublist_indexof_from_to,
417 gl_sublist_add_first,
419 gl_sublist_add_before,
420 gl_sublist_add_after,
422 gl_sublist_remove_node,
423 gl_sublist_remove_at,
425 gl_sublist_list_free,
427 gl_sublist_iterator_from_to,
428 gl_sublist_iterator_next,
429 gl_sublist_iterator_free,
430 gl_sublist_sortedlist_search,
431 gl_sublist_sortedlist_search_from_to,
432 gl_sublist_sortedlist_indexof,
433 gl_sublist_sortedlist_indexof_from_to,
434 gl_sublist_sortedlist_add,
435 gl_sublist_sortedlist_remove
439 gl_sublist_create (gl_list_t whole_list, size_t start_index, size_t end_index)
441 if (!(start_index <= end_index && end_index <= gl_list_size (whole_list)))
442 /* Invalid arguments. */
445 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
447 list->base.vtable = &gl_sublist_list_implementation;
448 list->base.equals_fn = whole_list->base.equals_fn; /* actually unused */
449 list->base.hashcode_fn = whole_list->base.hashcode_fn; /* actually unused */
450 list->base.dispose_fn = whole_list->base.dispose_fn; /* actually unused */
451 list->base.allow_duplicates = whole_list->base.allow_duplicates; /* unused */
452 if (whole_list->base.vtable == &gl_sublist_list_implementation)
454 /* Optimization of a sublist of a sublist: Collapse the two
455 indirections into a single indirection. */
456 list->whole = whole_list->whole;
457 list->start = whole_list->start + start_index;
458 list->end = whole_list->start + end_index;
462 list->whole = whole_list;
463 list->start = start_index;
464 list->end = end_index;