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 2, or (at your option)
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, write to the Free Software Foundation,
17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
22 #include "gl_sublist.h"
29 # define uintptr_t unsigned long
32 /* -------------------------- gl_list_t Data Type -------------------------- */
34 /* Concrete gl_list_impl type, valid for this file only. */
37 struct gl_list_impl_base base;
38 /* Reference to the whole list. */
40 /* Limits of the index range. */
45 /* struct gl_list_node_impl doesn't exist here. The pointers are actually
46 indices + 1. (We don't use the whole list's gl_list_node_t implementation,
47 because gl_sublist_next_node and gl_sublist_previous_node would not be easy
48 to implement with this choice.) */
49 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1)
50 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
53 gl_sublist_create_empty (gl_list_implementation_t implementation,
54 gl_listelement_equals_fn equals_fn,
55 gl_listelement_hashcode_fn hashcode_fn,
56 gl_listelement_dispose_fn dispose_fn,
57 bool allow_duplicates)
59 /* Shouldn't be called. */
64 gl_sublist_create_fill (gl_list_implementation_t implementation,
65 gl_listelement_equals_fn equals_fn,
66 gl_listelement_hashcode_fn hashcode_fn,
67 gl_listelement_dispose_fn dispose_fn,
68 bool allow_duplicates,
69 size_t count, const void **contents)
71 /* Shouldn't be called. */
76 gl_sublist_size (gl_list_t list)
78 return list->end - list->start;
82 gl_sublist_node_value (gl_list_t list, gl_list_node_t node)
84 uintptr_t index = NODE_TO_INDEX (node);
85 if (!(index < list->end - list->start))
86 /* Invalid argument. */
88 return gl_list_get_at (list->whole, list->start + index);
92 gl_sublist_next_node (gl_list_t list, gl_list_node_t node)
94 uintptr_t index = NODE_TO_INDEX (node);
95 size_t count = list->end - list->start;
97 /* Invalid argument. */
101 return INDEX_TO_NODE (index);
106 static gl_list_node_t
107 gl_sublist_previous_node (gl_list_t list, gl_list_node_t node)
109 uintptr_t index = NODE_TO_INDEX (node);
110 if (!(index < list->end - list->start))
111 /* Invalid argument. */
114 return INDEX_TO_NODE (index - 1);
120 gl_sublist_get_at (gl_list_t list, size_t position)
122 if (!(position < list->end - list->start))
123 /* Invalid argument. */
125 return gl_list_get_at (list->whole, list->start + position);
128 static gl_list_node_t
129 gl_sublist_set_at (gl_list_t list, size_t position, const void *elt)
131 if (!(position < list->end - list->start))
132 /* Invalid argument. */
134 gl_list_set_at (list->whole, list->start + position, elt);
135 return INDEX_TO_NODE (position);
138 static gl_list_node_t
139 gl_sublist_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
142 if (!(start_index <= end_index && end_index <= list->end - list->start))
143 /* Invalid arguments. */
147 gl_list_indexof_from_to (list->whole,
148 list->start + start_index,
149 list->start + end_index,
151 if (index != (size_t)(-1))
152 return INDEX_TO_NODE (index - list->start);
159 gl_sublist_indexof_from_to (gl_list_t list,
160 size_t start_index, size_t end_index,
163 if (!(start_index <= end_index && end_index <= list->end - list->start))
164 /* Invalid arguments. */
168 gl_list_indexof_from_to (list->whole,
169 list->start + start_index,
170 list->start + end_index,
172 if (index != (size_t)(-1))
173 index -= list->start;
178 static gl_list_node_t
179 gl_sublist_add_first (gl_list_t list, const void *elt)
181 gl_list_add_at (list->whole, list->start, elt);
183 return INDEX_TO_NODE (0);
186 static gl_list_node_t
187 gl_sublist_add_last (gl_list_t list, const void *elt)
189 gl_list_add_at (list->whole, list->end, elt);
191 return INDEX_TO_NODE (list->end - list->start - 1);
194 static gl_list_node_t
195 gl_sublist_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
197 size_t position = NODE_TO_INDEX (node);
198 if (!(position < list->end - list->start))
199 /* Invalid argument. */
201 gl_list_add_at (list->whole, list->start + position, elt);
203 return INDEX_TO_NODE (position);
206 static gl_list_node_t
207 gl_sublist_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
209 size_t position = NODE_TO_INDEX (node);
210 if (!(position < list->end - list->start))
211 /* Invalid argument. */
214 gl_list_add_at (list->whole, list->start + position, elt);
216 return INDEX_TO_NODE (position);
219 static gl_list_node_t
220 gl_sublist_add_at (gl_list_t list, size_t position, const void *elt)
222 if (!(position <= list->end - list->start))
223 /* Invalid argument. */
225 gl_list_add_at (list->whole, list->start + position, elt);
227 return INDEX_TO_NODE (position);
231 gl_sublist_remove_node (gl_list_t list, gl_list_node_t node)
233 uintptr_t index = NODE_TO_INDEX (node);
234 if (!(index < list->end - list->start))
235 /* Invalid argument. */
237 return gl_list_remove_at (list->whole, list->start + index);
241 gl_sublist_remove_at (gl_list_t list, size_t position)
243 if (!(position < list->end - list->start))
244 /* Invalid argument. */
246 return gl_list_remove_at (list->whole, list->start + position);
250 gl_sublist_remove (gl_list_t list, const void *elt)
253 gl_list_indexof_from_to (list->whole, list->start, list->end, elt);
254 if (position == (size_t)(-1))
257 return gl_list_remove_at (list->whole, position);
261 gl_sublist_list_free (gl_list_t list)
266 /* --------------------- gl_list_iterator_t Data Type --------------------- */
268 static gl_list_iterator_t
269 gl_sublist_iterator (gl_list_t list)
271 return gl_list_iterator_from_to (list->whole, list->start, list->end);
274 static gl_list_iterator_t
275 gl_sublist_iterator_from_to (gl_list_t list,
276 size_t start_index, size_t end_index)
278 if (!(start_index <= end_index && end_index <= list->end - list->start))
279 /* Invalid arguments. */
281 return gl_list_iterator_from_to (list->whole,
282 list->start + start_index,
283 list->start + end_index);
287 gl_sublist_iterator_next (gl_list_iterator_t *iterator,
288 const void **eltp, gl_list_node_t *nodep)
290 /* Shouldn't be called. */
295 gl_sublist_iterator_free (gl_list_iterator_t *iterator)
297 /* Shouldn't be called. */
301 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
303 static gl_list_node_t
304 gl_sublist_sortedlist_search (gl_list_t list,
305 gl_listelement_compar_fn compar,
309 gl_sortedlist_indexof_from_to (list->whole, compar,
310 list->start, list->end, elt);
311 if (index != (size_t)(-1))
312 return INDEX_TO_NODE (index - list->start);
317 static gl_list_node_t
318 gl_sublist_sortedlist_search_from_to (gl_list_t list,
319 gl_listelement_compar_fn compar,
320 size_t low, size_t high,
325 if (!(low <= high && high <= list->end - list->start))
326 /* Invalid arguments. */
330 gl_sortedlist_indexof_from_to (list->whole, compar,
331 list->start + low, list->start + high, elt);
332 if (index != (size_t)(-1))
333 return INDEX_TO_NODE (index - list->start);
339 gl_sublist_sortedlist_indexof (gl_list_t list,
340 gl_listelement_compar_fn compar,
344 gl_sortedlist_indexof_from_to (list->whole, compar, list->start, list->end,
346 if (index != (size_t)(-1))
347 index -= list->start;
352 gl_sublist_sortedlist_indexof_from_to (gl_list_t list,
353 gl_listelement_compar_fn compar,
354 size_t low, size_t high,
359 if (!(low <= high && high <= list->end - list->start))
360 /* Invalid arguments. */
363 index = gl_sortedlist_indexof_from_to (list->whole, compar,
364 list->start + low, list->start + high,
366 if (index != (size_t)(-1))
367 index -= list->start;
371 static gl_list_node_t
372 gl_sublist_sortedlist_add (gl_list_t list,
373 gl_listelement_compar_fn compar,
376 /* It's impossible to implement this method without risking to put the
377 whole list into unsorted order (namely, when the given ELT is smaller
378 or larger than all elements of the sublist). */
383 gl_sublist_sortedlist_remove (gl_list_t list,
384 gl_listelement_compar_fn compar,
387 size_t index = gl_sublist_sortedlist_indexof (list, compar, elt);
388 if (index == (size_t)(-1))
391 return gl_sublist_remove_at (list, index);
395 static const struct gl_list_implementation gl_sublist_list_implementation =
397 gl_sublist_create_empty,
398 gl_sublist_create_fill,
400 gl_sublist_node_value,
401 gl_sublist_next_node,
402 gl_sublist_previous_node,
405 gl_sublist_search_from_to,
406 gl_sublist_indexof_from_to,
407 gl_sublist_add_first,
409 gl_sublist_add_before,
410 gl_sublist_add_after,
412 gl_sublist_remove_node,
413 gl_sublist_remove_at,
415 gl_sublist_list_free,
417 gl_sublist_iterator_from_to,
418 gl_sublist_iterator_next,
419 gl_sublist_iterator_free,
420 gl_sublist_sortedlist_search,
421 gl_sublist_sortedlist_search_from_to,
422 gl_sublist_sortedlist_indexof,
423 gl_sublist_sortedlist_indexof_from_to,
424 gl_sublist_sortedlist_add,
425 gl_sublist_sortedlist_remove
429 gl_sublist_create (gl_list_t whole_list, size_t start_index, size_t end_index)
431 if (!(start_index <= end_index && end_index <= gl_list_size (whole_list)))
432 /* Invalid arguments. */
435 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
437 list->base.vtable = &gl_sublist_list_implementation;
438 list->base.equals_fn = whole_list->base.equals_fn; /* actually unused */
439 list->base.hashcode_fn = whole_list->base.hashcode_fn; /* actually unused */
440 list->base.dispose_fn = whole_list->base.dispose_fn; /* actually unused */
441 list->base.allow_duplicates = whole_list->base.allow_duplicates; /* unused */
442 if (whole_list->base.vtable == &gl_sublist_list_implementation)
444 /* Optimization of a sublist of a sublist: Collapse the two
445 indirections into a single indirection. */
446 list->whole = whole_list->whole;
447 list->start = whole_list->start + start_index;
448 list->end = whole_list->start + end_index;
452 list->whole = whole_list;
453 list->start = start_index;
454 list->end = end_index;