1 /* Sequential list data type backed by another list.
2 Copyright (C) 2006 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 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 bool allow_duplicates,
67 size_t count, const void **contents)
69 /* Shouldn't be called. */
74 gl_sublist_size (gl_list_t list)
76 return list->end - list->start;
80 gl_sublist_node_value (gl_list_t list, gl_list_node_t node)
82 uintptr_t index = NODE_TO_INDEX (node);
83 if (!(index < list->end - list->start))
84 /* Invalid argument. */
86 return gl_list_get_at (list->whole, list->start + index);
90 gl_sublist_next_node (gl_list_t list, gl_list_node_t node)
92 uintptr_t index = NODE_TO_INDEX (node);
93 size_t count = list->end - list->start;
95 /* Invalid argument. */
99 return INDEX_TO_NODE (index);
104 static gl_list_node_t
105 gl_sublist_previous_node (gl_list_t list, gl_list_node_t node)
107 uintptr_t index = NODE_TO_INDEX (node);
108 if (!(index < list->end - list->start))
109 /* Invalid argument. */
112 return INDEX_TO_NODE (index - 1);
118 gl_sublist_get_at (gl_list_t list, size_t position)
120 if (!(position < list->end - list->start))
121 /* Invalid argument. */
123 return gl_list_get_at (list->whole, list->start + position);
126 static gl_list_node_t
127 gl_sublist_set_at (gl_list_t list, size_t position, const void *elt)
129 if (!(position < list->end - list->start))
130 /* Invalid argument. */
132 gl_list_set_at (list->whole, list->start + position, elt);
133 return INDEX_TO_NODE (position);
136 static gl_list_node_t
137 gl_sublist_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
140 if (!(start_index <= end_index && end_index <= list->end - list->start))
141 /* Invalid arguments. */
145 gl_list_indexof_from_to (list->whole,
146 list->start + start_index,
147 list->start + end_index,
149 if (index != (size_t)(-1))
150 return INDEX_TO_NODE (index - list->start);
157 gl_sublist_indexof_from_to (gl_list_t list,
158 size_t start_index, size_t end_index,
161 if (!(start_index <= end_index && end_index <= list->end - list->start))
162 /* Invalid arguments. */
166 gl_list_indexof_from_to (list->whole,
167 list->start + start_index,
168 list->start + end_index,
170 if (index != (size_t)(-1))
171 index -= list->start;
176 static gl_list_node_t
177 gl_sublist_add_first (gl_list_t list, const void *elt)
179 gl_list_add_at (list->whole, list->start, elt);
181 return INDEX_TO_NODE (0);
184 static gl_list_node_t
185 gl_sublist_add_last (gl_list_t list, const void *elt)
187 gl_list_add_at (list->whole, list->end, elt);
189 return INDEX_TO_NODE (list->end - list->start - 1);
192 static gl_list_node_t
193 gl_sublist_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
195 size_t position = NODE_TO_INDEX (node);
196 if (!(position < list->end - list->start))
197 /* Invalid argument. */
199 gl_list_add_at (list->whole, list->start + position, elt);
201 return INDEX_TO_NODE (position);
204 static gl_list_node_t
205 gl_sublist_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
207 size_t position = NODE_TO_INDEX (node);
208 if (!(position < list->end - list->start))
209 /* Invalid argument. */
212 gl_list_add_at (list->whole, list->start + position, elt);
214 return INDEX_TO_NODE (position);
217 static gl_list_node_t
218 gl_sublist_add_at (gl_list_t list, size_t position, const void *elt)
220 if (!(position <= list->end - list->start))
221 /* Invalid argument. */
223 gl_list_add_at (list->whole, list->start + position, elt);
225 return INDEX_TO_NODE (position);
229 gl_sublist_remove_node (gl_list_t list, gl_list_node_t node)
231 uintptr_t index = NODE_TO_INDEX (node);
232 if (!(index < list->end - list->start))
233 /* Invalid argument. */
235 return gl_list_remove_at (list->whole, list->start + index);
239 gl_sublist_remove_at (gl_list_t list, size_t position)
241 if (!(position < list->end - list->start))
242 /* Invalid argument. */
244 return gl_list_remove_at (list->whole, list->start + position);
248 gl_sublist_remove (gl_list_t list, const void *elt)
251 gl_list_indexof_from_to (list->whole, list->start, list->end, elt);
252 if (position == (size_t)(-1))
255 return gl_list_remove_at (list->whole, position);
259 gl_sublist_list_free (gl_list_t list)
264 /* --------------------- gl_list_iterator_t Data Type --------------------- */
266 static gl_list_iterator_t
267 gl_sublist_iterator (gl_list_t list)
269 return gl_list_iterator_from_to (list->whole, list->start, list->end);
272 static gl_list_iterator_t
273 gl_sublist_iterator_from_to (gl_list_t list,
274 size_t start_index, size_t end_index)
276 if (!(start_index <= end_index && end_index <= list->end - list->start))
277 /* Invalid arguments. */
279 return gl_list_iterator_from_to (list->whole,
280 list->start + start_index,
281 list->start + end_index);
285 gl_sublist_iterator_next (gl_list_iterator_t *iterator,
286 const void **eltp, gl_list_node_t *nodep)
288 /* Shouldn't be called. */
293 gl_sublist_iterator_free (gl_list_iterator_t *iterator)
295 /* Shouldn't be called. */
299 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
301 static gl_list_node_t
302 gl_sublist_sortedlist_search (gl_list_t list,
303 gl_listelement_compar_fn compar,
307 gl_sortedlist_indexof_from_to (list->whole, compar,
308 list->start, list->end, elt);
309 if (index != (size_t)(-1))
310 return INDEX_TO_NODE (index - list->start);
315 static gl_list_node_t
316 gl_sublist_sortedlist_search_from_to (gl_list_t list,
317 gl_listelement_compar_fn compar,
318 size_t low, size_t high,
323 if (!(low <= high && high <= list->end - list->start))
324 /* Invalid arguments. */
328 gl_sortedlist_indexof_from_to (list->whole, compar,
329 list->start + low, list->start + high, elt);
330 if (index != (size_t)(-1))
331 return INDEX_TO_NODE (index - list->start);
337 gl_sublist_sortedlist_indexof (gl_list_t list,
338 gl_listelement_compar_fn compar,
342 gl_sortedlist_indexof_from_to (list->whole, compar, list->start, list->end,
344 if (index != (size_t)(-1))
345 index -= list->start;
350 gl_sublist_sortedlist_indexof_from_to (gl_list_t list,
351 gl_listelement_compar_fn compar,
352 size_t low, size_t high,
357 if (!(low <= high && high <= list->end - list->start))
358 /* Invalid arguments. */
361 index = gl_sortedlist_indexof_from_to (list->whole, compar,
362 list->start + low, list->start + high,
364 if (index != (size_t)(-1))
365 index -= list->start;
369 static gl_list_node_t
370 gl_sublist_sortedlist_add (gl_list_t list,
371 gl_listelement_compar_fn compar,
374 /* It's impossible to implement this method without risking to put the
375 whole list into unsorted order (namely, when the given ELT is smaller
376 or larger than all elements of the sublist). */
381 gl_sublist_sortedlist_remove (gl_list_t list,
382 gl_listelement_compar_fn compar,
385 size_t index = gl_sublist_sortedlist_indexof (list, compar, elt);
386 if (index == (size_t)(-1))
389 return gl_sublist_remove_at (list, index);
393 static const struct gl_list_implementation gl_sublist_list_implementation =
395 gl_sublist_create_empty,
396 gl_sublist_create_fill,
398 gl_sublist_node_value,
399 gl_sublist_next_node,
400 gl_sublist_previous_node,
403 gl_sublist_search_from_to,
404 gl_sublist_indexof_from_to,
405 gl_sublist_add_first,
407 gl_sublist_add_before,
408 gl_sublist_add_after,
410 gl_sublist_remove_node,
411 gl_sublist_remove_at,
413 gl_sublist_list_free,
415 gl_sublist_iterator_from_to,
416 gl_sublist_iterator_next,
417 gl_sublist_iterator_free,
418 gl_sublist_sortedlist_search,
419 gl_sublist_sortedlist_search_from_to,
420 gl_sublist_sortedlist_indexof,
421 gl_sublist_sortedlist_indexof_from_to,
422 gl_sublist_sortedlist_add,
423 gl_sublist_sortedlist_remove
427 gl_sublist_create (gl_list_t whole_list, size_t start_index, size_t end_index)
429 if (!(start_index <= end_index && end_index <= gl_list_size (whole_list)))
430 /* Invalid arguments. */
433 struct gl_list_impl *list =
434 (struct gl_list_impl *) xmalloc (sizeof (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.allow_duplicates = whole_list->base.allow_duplicates; /* unused */
440 if (whole_list->base.vtable == &gl_sublist_list_implementation)
442 /* Optimization of a sublist of a sublist: Collapse the two
443 indirections into a single indirection. */
444 list->whole = whole_list->whole;
445 list->start = whole_list->start + start_index;
446 list->end = whole_list->start + end_index;
450 list->whole = whole_list;
451 list->start = start_index;
452 list->end = end_index;