1 /* Sequential list data type backed by another list.
2 Copyright (C) 2006-2019 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 <https://www.gnu.org/licenses/>. */
21 #include "gl_sublist.h"
26 /* -------------------------- gl_list_t Data Type -------------------------- */
28 /* Concrete gl_list_impl type, valid for this file only. */
31 struct gl_list_impl_base base
;
32 /* Reference to the whole list. */
34 /* Limits of the index range. */
39 /* struct gl_list_node_impl doesn't exist here. The pointers are actually
40 indices + 1. (We don't use the whole list's gl_list_node_t implementation,
41 because gl_sublist_next_node and gl_sublist_previous_node would not be easy
42 to implement with this choice.) */
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)
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
)
53 /* Shouldn't be called. */
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
)
65 /* Shouldn't be called. */
70 gl_sublist_size (gl_list_t list
)
72 return list
->end
- list
->start
;
76 gl_sublist_node_value (gl_list_t list
, gl_list_node_t node
)
78 uintptr_t index
= NODE_TO_INDEX (node
);
79 if (!(index
< list
->end
- list
->start
))
80 /* Invalid argument. */
82 return gl_list_get_at (list
->whole
, list
->start
+ index
);
86 gl_sublist_node_nx_set_value (gl_list_t list
, gl_list_node_t node
, const void *elt
)
88 uintptr_t index
= NODE_TO_INDEX (node
);
89 if (!(index
< list
->end
- list
->start
))
90 /* Invalid argument. */
92 if (gl_list_nx_set_at (list
->whole
, list
->start
+ index
, elt
) == NULL
)
98 gl_sublist_next_node (gl_list_t list
, gl_list_node_t node
)
100 uintptr_t index
= NODE_TO_INDEX (node
);
101 size_t count
= list
->end
- list
->start
;
102 if (!(index
< count
))
103 /* Invalid argument. */
107 return INDEX_TO_NODE (index
);
112 static gl_list_node_t
113 gl_sublist_previous_node (gl_list_t list
, gl_list_node_t node
)
115 uintptr_t index
= NODE_TO_INDEX (node
);
116 if (!(index
< list
->end
- list
->start
))
117 /* Invalid argument. */
120 return INDEX_TO_NODE (index
- 1);
126 gl_sublist_get_at (gl_list_t list
, size_t position
)
128 if (!(position
< list
->end
- list
->start
))
129 /* Invalid argument. */
131 return gl_list_get_at (list
->whole
, list
->start
+ position
);
134 static gl_list_node_t
135 gl_sublist_nx_set_at (gl_list_t list
, size_t position
, const void *elt
)
137 if (!(position
< list
->end
- list
->start
))
138 /* Invalid argument. */
140 if (gl_list_nx_set_at (list
->whole
, list
->start
+ position
, elt
) == NULL
)
142 return INDEX_TO_NODE (position
);
145 static gl_list_node_t
146 gl_sublist_search_from_to (gl_list_t list
, size_t start_index
, size_t end_index
,
149 if (!(start_index
<= end_index
&& end_index
<= list
->end
- list
->start
))
150 /* Invalid arguments. */
154 gl_list_indexof_from_to (list
->whole
,
155 list
->start
+ start_index
,
156 list
->start
+ end_index
,
158 if (index
!= (size_t)(-1))
159 return INDEX_TO_NODE (index
- list
->start
);
166 gl_sublist_indexof_from_to (gl_list_t list
,
167 size_t start_index
, size_t end_index
,
170 if (!(start_index
<= end_index
&& end_index
<= list
->end
- list
->start
))
171 /* Invalid arguments. */
175 gl_list_indexof_from_to (list
->whole
,
176 list
->start
+ start_index
,
177 list
->start
+ end_index
,
179 if (index
!= (size_t)(-1))
180 index
-= list
->start
;
185 static gl_list_node_t
186 gl_sublist_nx_add_first (gl_list_t list
, const void *elt
)
188 if (gl_list_nx_add_at (list
->whole
, list
->start
, elt
) == NULL
)
191 return INDEX_TO_NODE (0);
194 static gl_list_node_t
195 gl_sublist_nx_add_last (gl_list_t list
, const void *elt
)
197 if (gl_list_nx_add_at (list
->whole
, list
->end
, elt
) == NULL
)
200 return INDEX_TO_NODE (list
->end
- list
->start
- 1);
203 static gl_list_node_t
204 gl_sublist_nx_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 if (gl_list_nx_add_at (list
->whole
, list
->start
+ position
, elt
) == NULL
)
213 return INDEX_TO_NODE (position
);
216 static gl_list_node_t
217 gl_sublist_nx_add_after (gl_list_t list
, gl_list_node_t node
, const void *elt
)
219 size_t position
= NODE_TO_INDEX (node
);
220 if (!(position
< list
->end
- list
->start
))
221 /* Invalid argument. */
224 if (gl_list_nx_add_at (list
->whole
, list
->start
+ position
, elt
) == NULL
)
227 return INDEX_TO_NODE (position
);
230 static gl_list_node_t
231 gl_sublist_nx_add_at (gl_list_t list
, size_t position
, const void *elt
)
233 if (!(position
<= list
->end
- list
->start
))
234 /* Invalid argument. */
236 if (gl_list_nx_add_at (list
->whole
, list
->start
+ position
, elt
) == NULL
)
239 return INDEX_TO_NODE (position
);
243 gl_sublist_remove_node (gl_list_t list
, gl_list_node_t node
)
245 uintptr_t index
= NODE_TO_INDEX (node
);
246 if (!(index
< list
->end
- list
->start
))
247 /* Invalid argument. */
249 return gl_list_remove_at (list
->whole
, list
->start
+ index
);
253 gl_sublist_remove_at (gl_list_t list
, size_t position
)
255 if (!(position
< list
->end
- list
->start
))
256 /* Invalid argument. */
258 return gl_list_remove_at (list
->whole
, list
->start
+ position
);
262 gl_sublist_remove (gl_list_t list
, const void *elt
)
265 gl_list_indexof_from_to (list
->whole
, list
->start
, list
->end
, elt
);
266 if (position
== (size_t)(-1))
269 return gl_list_remove_at (list
->whole
, position
);
273 gl_sublist_list_free (gl_list_t list
)
278 /* --------------------- gl_list_iterator_t Data Type --------------------- */
280 static gl_list_iterator_t
281 gl_sublist_iterator (gl_list_t list
)
283 return gl_list_iterator_from_to (list
->whole
, list
->start
, list
->end
);
286 static gl_list_iterator_t
287 gl_sublist_iterator_from_to (gl_list_t list
,
288 size_t start_index
, size_t end_index
)
290 if (!(start_index
<= end_index
&& end_index
<= list
->end
- list
->start
))
291 /* Invalid arguments. */
293 return gl_list_iterator_from_to (list
->whole
,
294 list
->start
+ start_index
,
295 list
->start
+ end_index
);
299 gl_sublist_iterator_next (gl_list_iterator_t
*iterator
,
300 const void **eltp
, gl_list_node_t
*nodep
)
302 /* Shouldn't be called. */
307 gl_sublist_iterator_free (gl_list_iterator_t
*iterator
)
309 /* Shouldn't be called. */
313 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
315 static gl_list_node_t
316 gl_sublist_sortedlist_search (gl_list_t list
,
317 gl_listelement_compar_fn compar
,
321 gl_sortedlist_indexof_from_to (list
->whole
, compar
,
322 list
->start
, list
->end
, elt
);
323 if (index
!= (size_t)(-1))
324 return INDEX_TO_NODE (index
- list
->start
);
329 static gl_list_node_t
330 gl_sublist_sortedlist_search_from_to (gl_list_t list
,
331 gl_listelement_compar_fn compar
,
332 size_t low
, size_t high
,
337 if (!(low
<= high
&& high
<= list
->end
- list
->start
))
338 /* Invalid arguments. */
342 gl_sortedlist_indexof_from_to (list
->whole
, compar
,
343 list
->start
+ low
, list
->start
+ high
, elt
);
344 if (index
!= (size_t)(-1))
345 return INDEX_TO_NODE (index
- list
->start
);
351 gl_sublist_sortedlist_indexof (gl_list_t list
,
352 gl_listelement_compar_fn compar
,
356 gl_sortedlist_indexof_from_to (list
->whole
, compar
, list
->start
, list
->end
,
358 if (index
!= (size_t)(-1))
359 index
-= list
->start
;
364 gl_sublist_sortedlist_indexof_from_to (gl_list_t list
,
365 gl_listelement_compar_fn compar
,
366 size_t low
, size_t high
,
371 if (!(low
<= high
&& high
<= list
->end
- list
->start
))
372 /* Invalid arguments. */
375 index
= gl_sortedlist_indexof_from_to (list
->whole
, compar
,
376 list
->start
+ low
, list
->start
+ high
,
378 if (index
!= (size_t)(-1))
379 index
-= list
->start
;
383 static gl_list_node_t
384 gl_sublist_sortedlist_nx_add (gl_list_t list
,
385 gl_listelement_compar_fn compar
,
388 /* It's impossible to implement this method without risking to put the
389 whole list into unsorted order (namely, when the given ELT is smaller
390 or larger than all elements of the sublist). */
395 gl_sublist_sortedlist_remove (gl_list_t list
,
396 gl_listelement_compar_fn compar
,
399 size_t index
= gl_sublist_sortedlist_indexof (list
, compar
, elt
);
400 if (index
== (size_t)(-1))
403 return gl_sublist_remove_at (list
, index
);
407 static const struct gl_list_implementation gl_sublist_list_implementation
=
409 gl_sublist_nx_create_empty
,
410 gl_sublist_nx_create_fill
,
412 gl_sublist_node_value
,
413 gl_sublist_node_nx_set_value
,
414 gl_sublist_next_node
,
415 gl_sublist_previous_node
,
417 gl_sublist_nx_set_at
,
418 gl_sublist_search_from_to
,
419 gl_sublist_indexof_from_to
,
420 gl_sublist_nx_add_first
,
421 gl_sublist_nx_add_last
,
422 gl_sublist_nx_add_before
,
423 gl_sublist_nx_add_after
,
424 gl_sublist_nx_add_at
,
425 gl_sublist_remove_node
,
426 gl_sublist_remove_at
,
428 gl_sublist_list_free
,
430 gl_sublist_iterator_from_to
,
431 gl_sublist_iterator_next
,
432 gl_sublist_iterator_free
,
433 gl_sublist_sortedlist_search
,
434 gl_sublist_sortedlist_search_from_to
,
435 gl_sublist_sortedlist_indexof
,
436 gl_sublist_sortedlist_indexof_from_to
,
437 gl_sublist_sortedlist_nx_add
,
438 gl_sublist_sortedlist_remove
442 gl_sublist_nx_create (gl_list_t whole_list
, size_t start_index
, size_t end_index
)
444 if (!(start_index
<= end_index
&& end_index
<= gl_list_size (whole_list
)))
445 /* Invalid arguments. */
448 struct gl_list_impl
*list
=
449 (struct gl_list_impl
*) malloc (sizeof (struct gl_list_impl
));
454 list
->base
.vtable
= &gl_sublist_list_implementation
;
455 list
->base
.equals_fn
= whole_list
->base
.equals_fn
; /* actually unused */
456 list
->base
.hashcode_fn
= whole_list
->base
.hashcode_fn
; /* actually unused */
457 list
->base
.dispose_fn
= whole_list
->base
.dispose_fn
; /* actually unused */
458 list
->base
.allow_duplicates
= whole_list
->base
.allow_duplicates
; /* unused */
459 if (whole_list
->base
.vtable
== &gl_sublist_list_implementation
)
461 /* Optimization of a sublist of a sublist: Collapse the two
462 indirections into a single indirection. */
463 list
->whole
= whole_list
->whole
;
464 list
->start
= whole_list
->start
+ start_index
;
465 list
->end
= whole_list
->start
+ end_index
;
469 list
->whole
= whole_list
;
470 list
->start
= start_index
;
471 list
->end
= end_index
;