1 /* Sequential list data type backed by another list.
2 Copyright (C) 2006-2007 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_next_node (gl_list_t list, gl_list_node_t node)
93 uintptr_t index = NODE_TO_INDEX (node);
94 size_t count = list->end - list->start;
96 /* Invalid argument. */
100 return INDEX_TO_NODE (index);
105 static gl_list_node_t
106 gl_sublist_previous_node (gl_list_t list, gl_list_node_t node)
108 uintptr_t index = NODE_TO_INDEX (node);
109 if (!(index < list->end - list->start))
110 /* Invalid argument. */
113 return INDEX_TO_NODE (index - 1);
119 gl_sublist_get_at (gl_list_t list, size_t position)
121 if (!(position < list->end - list->start))
122 /* Invalid argument. */
124 return gl_list_get_at (list->whole, list->start + position);
127 static gl_list_node_t
128 gl_sublist_set_at (gl_list_t list, size_t position, const void *elt)
130 if (!(position < list->end - list->start))
131 /* Invalid argument. */
133 gl_list_set_at (list->whole, list->start + position, elt);
134 return INDEX_TO_NODE (position);
137 static gl_list_node_t
138 gl_sublist_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
141 if (!(start_index <= end_index && end_index <= list->end - list->start))
142 /* Invalid arguments. */
146 gl_list_indexof_from_to (list->whole,
147 list->start + start_index,
148 list->start + end_index,
150 if (index != (size_t)(-1))
151 return INDEX_TO_NODE (index - list->start);
158 gl_sublist_indexof_from_to (gl_list_t list,
159 size_t start_index, size_t end_index,
162 if (!(start_index <= end_index && end_index <= list->end - list->start))
163 /* Invalid arguments. */
167 gl_list_indexof_from_to (list->whole,
168 list->start + start_index,
169 list->start + end_index,
171 if (index != (size_t)(-1))
172 index -= list->start;
177 static gl_list_node_t
178 gl_sublist_add_first (gl_list_t list, const void *elt)
180 gl_list_add_at (list->whole, list->start, elt);
182 return INDEX_TO_NODE (0);
185 static gl_list_node_t
186 gl_sublist_add_last (gl_list_t list, const void *elt)
188 gl_list_add_at (list->whole, list->end, elt);
190 return INDEX_TO_NODE (list->end - list->start - 1);
193 static gl_list_node_t
194 gl_sublist_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
196 size_t position = NODE_TO_INDEX (node);
197 if (!(position < list->end - list->start))
198 /* Invalid argument. */
200 gl_list_add_at (list->whole, list->start + position, elt);
202 return INDEX_TO_NODE (position);
205 static gl_list_node_t
206 gl_sublist_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
208 size_t position = NODE_TO_INDEX (node);
209 if (!(position < list->end - list->start))
210 /* Invalid argument. */
213 gl_list_add_at (list->whole, list->start + position, elt);
215 return INDEX_TO_NODE (position);
218 static gl_list_node_t
219 gl_sublist_add_at (gl_list_t list, size_t position, const void *elt)
221 if (!(position <= list->end - list->start))
222 /* Invalid argument. */
224 gl_list_add_at (list->whole, list->start + position, elt);
226 return INDEX_TO_NODE (position);
230 gl_sublist_remove_node (gl_list_t list, gl_list_node_t node)
232 uintptr_t index = NODE_TO_INDEX (node);
233 if (!(index < list->end - list->start))
234 /* Invalid argument. */
236 return gl_list_remove_at (list->whole, list->start + index);
240 gl_sublist_remove_at (gl_list_t list, size_t position)
242 if (!(position < list->end - list->start))
243 /* Invalid argument. */
245 return gl_list_remove_at (list->whole, list->start + position);
249 gl_sublist_remove (gl_list_t list, const void *elt)
252 gl_list_indexof_from_to (list->whole, list->start, list->end, elt);
253 if (position == (size_t)(-1))
256 return gl_list_remove_at (list->whole, position);
260 gl_sublist_list_free (gl_list_t list)
265 /* --------------------- gl_list_iterator_t Data Type --------------------- */
267 static gl_list_iterator_t
268 gl_sublist_iterator (gl_list_t list)
270 return gl_list_iterator_from_to (list->whole, list->start, list->end);
273 static gl_list_iterator_t
274 gl_sublist_iterator_from_to (gl_list_t list,
275 size_t start_index, size_t end_index)
277 if (!(start_index <= end_index && end_index <= list->end - list->start))
278 /* Invalid arguments. */
280 return gl_list_iterator_from_to (list->whole,
281 list->start + start_index,
282 list->start + end_index);
286 gl_sublist_iterator_next (gl_list_iterator_t *iterator,
287 const void **eltp, gl_list_node_t *nodep)
289 /* Shouldn't be called. */
294 gl_sublist_iterator_free (gl_list_iterator_t *iterator)
296 /* Shouldn't be called. */
300 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
302 static gl_list_node_t
303 gl_sublist_sortedlist_search (gl_list_t list,
304 gl_listelement_compar_fn compar,
308 gl_sortedlist_indexof_from_to (list->whole, compar,
309 list->start, list->end, elt);
310 if (index != (size_t)(-1))
311 return INDEX_TO_NODE (index - list->start);
316 static gl_list_node_t
317 gl_sublist_sortedlist_search_from_to (gl_list_t list,
318 gl_listelement_compar_fn compar,
319 size_t low, size_t high,
324 if (!(low <= high && high <= list->end - list->start))
325 /* Invalid arguments. */
329 gl_sortedlist_indexof_from_to (list->whole, compar,
330 list->start + low, list->start + high, elt);
331 if (index != (size_t)(-1))
332 return INDEX_TO_NODE (index - list->start);
338 gl_sublist_sortedlist_indexof (gl_list_t list,
339 gl_listelement_compar_fn compar,
343 gl_sortedlist_indexof_from_to (list->whole, compar, list->start, list->end,
345 if (index != (size_t)(-1))
346 index -= list->start;
351 gl_sublist_sortedlist_indexof_from_to (gl_list_t list,
352 gl_listelement_compar_fn compar,
353 size_t low, size_t high,
358 if (!(low <= high && high <= list->end - list->start))
359 /* Invalid arguments. */
362 index = gl_sortedlist_indexof_from_to (list->whole, compar,
363 list->start + low, list->start + high,
365 if (index != (size_t)(-1))
366 index -= list->start;
370 static gl_list_node_t
371 gl_sublist_sortedlist_add (gl_list_t list,
372 gl_listelement_compar_fn compar,
375 /* It's impossible to implement this method without risking to put the
376 whole list into unsorted order (namely, when the given ELT is smaller
377 or larger than all elements of the sublist). */
382 gl_sublist_sortedlist_remove (gl_list_t list,
383 gl_listelement_compar_fn compar,
386 size_t index = gl_sublist_sortedlist_indexof (list, compar, elt);
387 if (index == (size_t)(-1))
390 return gl_sublist_remove_at (list, index);
394 static const struct gl_list_implementation gl_sublist_list_implementation =
396 gl_sublist_create_empty,
397 gl_sublist_create_fill,
399 gl_sublist_node_value,
400 gl_sublist_next_node,
401 gl_sublist_previous_node,
404 gl_sublist_search_from_to,
405 gl_sublist_indexof_from_to,
406 gl_sublist_add_first,
408 gl_sublist_add_before,
409 gl_sublist_add_after,
411 gl_sublist_remove_node,
412 gl_sublist_remove_at,
414 gl_sublist_list_free,
416 gl_sublist_iterator_from_to,
417 gl_sublist_iterator_next,
418 gl_sublist_iterator_free,
419 gl_sublist_sortedlist_search,
420 gl_sublist_sortedlist_search_from_to,
421 gl_sublist_sortedlist_indexof,
422 gl_sublist_sortedlist_indexof_from_to,
423 gl_sublist_sortedlist_add,
424 gl_sublist_sortedlist_remove
428 gl_sublist_create (gl_list_t whole_list, size_t start_index, size_t end_index)
430 if (!(start_index <= end_index && end_index <= gl_list_size (whole_list)))
431 /* Invalid arguments. */
434 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
436 list->base.vtable = &gl_sublist_list_implementation;
437 list->base.equals_fn = whole_list->base.equals_fn; /* actually unused */
438 list->base.hashcode_fn = whole_list->base.hashcode_fn; /* actually unused */
439 list->base.dispose_fn = whole_list->base.dispose_fn; /* actually unused */
440 list->base.allow_duplicates = whole_list->base.allow_duplicates; /* unused */
441 if (whole_list->base.vtable == &gl_sublist_list_implementation)
443 /* Optimization of a sublist of a sublist: Collapse the two
444 indirections into a single indirection. */
445 list->whole = whole_list->whole;
446 list->start = whole_list->start + start_index;
447 list->end = whole_list->start + end_index;
451 list->whole = whole_list;
452 list->start = start_index;
453 list->end = end_index;