1 /* Sequential list data type backed by another list.
2 Copyright (C) 2006-2018 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 # define uintptr_t unsigned long
29 /* -------------------------- gl_list_t Data Type -------------------------- */
31 /* Concrete gl_list_impl type, valid for this file only. */
34 struct gl_list_impl_base base
;
35 /* Reference to the whole list. */
37 /* Limits of the index range. */
42 /* struct gl_list_node_impl doesn't exist here. The pointers are actually
43 indices + 1. (We don't use the whole list's gl_list_node_t implementation,
44 because gl_sublist_next_node and gl_sublist_previous_node would not be easy
45 to implement with this choice.) */
46 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1)
47 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
50 gl_sublist_nx_create_empty (gl_list_implementation_t implementation
,
51 gl_listelement_equals_fn equals_fn
,
52 gl_listelement_hashcode_fn hashcode_fn
,
53 gl_listelement_dispose_fn dispose_fn
,
54 bool allow_duplicates
)
56 /* Shouldn't be called. */
61 gl_sublist_nx_create_fill (gl_list_implementation_t implementation
,
62 gl_listelement_equals_fn equals_fn
,
63 gl_listelement_hashcode_fn hashcode_fn
,
64 gl_listelement_dispose_fn dispose_fn
,
65 bool allow_duplicates
,
66 size_t count
, const void **contents
)
68 /* Shouldn't be called. */
73 gl_sublist_size (gl_list_t list
)
75 return list
->end
- list
->start
;
79 gl_sublist_node_value (gl_list_t list
, gl_list_node_t node
)
81 uintptr_t index
= NODE_TO_INDEX (node
);
82 if (!(index
< list
->end
- list
->start
))
83 /* Invalid argument. */
85 return gl_list_get_at (list
->whole
, list
->start
+ index
);
89 gl_sublist_node_nx_set_value (gl_list_t list
, gl_list_node_t node
, const void *elt
)
91 uintptr_t index
= NODE_TO_INDEX (node
);
92 if (!(index
< list
->end
- list
->start
))
93 /* Invalid argument. */
95 if (gl_list_nx_set_at (list
->whole
, list
->start
+ index
, elt
) == NULL
)
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_nx_set_at (gl_list_t list
, size_t position
, const void *elt
)
140 if (!(position
< list
->end
- list
->start
))
141 /* Invalid argument. */
143 if (gl_list_nx_set_at (list
->whole
, list
->start
+ position
, elt
) == NULL
)
145 return INDEX_TO_NODE (position
);
148 static gl_list_node_t
149 gl_sublist_search_from_to (gl_list_t list
, size_t start_index
, size_t end_index
,
152 if (!(start_index
<= end_index
&& end_index
<= list
->end
- list
->start
))
153 /* Invalid arguments. */
157 gl_list_indexof_from_to (list
->whole
,
158 list
->start
+ start_index
,
159 list
->start
+ end_index
,
161 if (index
!= (size_t)(-1))
162 return INDEX_TO_NODE (index
- list
->start
);
169 gl_sublist_indexof_from_to (gl_list_t list
,
170 size_t start_index
, size_t end_index
,
173 if (!(start_index
<= end_index
&& end_index
<= list
->end
- list
->start
))
174 /* Invalid arguments. */
178 gl_list_indexof_from_to (list
->whole
,
179 list
->start
+ start_index
,
180 list
->start
+ end_index
,
182 if (index
!= (size_t)(-1))
183 index
-= list
->start
;
188 static gl_list_node_t
189 gl_sublist_nx_add_first (gl_list_t list
, const void *elt
)
191 if (gl_list_nx_add_at (list
->whole
, list
->start
, elt
) == NULL
)
194 return INDEX_TO_NODE (0);
197 static gl_list_node_t
198 gl_sublist_nx_add_last (gl_list_t list
, const void *elt
)
200 if (gl_list_nx_add_at (list
->whole
, list
->end
, elt
) == NULL
)
203 return INDEX_TO_NODE (list
->end
- list
->start
- 1);
206 static gl_list_node_t
207 gl_sublist_nx_add_before (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. */
213 if (gl_list_nx_add_at (list
->whole
, list
->start
+ position
, elt
) == NULL
)
216 return INDEX_TO_NODE (position
);
219 static gl_list_node_t
220 gl_sublist_nx_add_after (gl_list_t list
, gl_list_node_t node
, const void *elt
)
222 size_t position
= NODE_TO_INDEX (node
);
223 if (!(position
< list
->end
- list
->start
))
224 /* Invalid argument. */
227 if (gl_list_nx_add_at (list
->whole
, list
->start
+ position
, elt
) == NULL
)
230 return INDEX_TO_NODE (position
);
233 static gl_list_node_t
234 gl_sublist_nx_add_at (gl_list_t list
, size_t position
, const void *elt
)
236 if (!(position
<= list
->end
- list
->start
))
237 /* Invalid argument. */
239 if (gl_list_nx_add_at (list
->whole
, list
->start
+ position
, elt
) == NULL
)
242 return INDEX_TO_NODE (position
);
246 gl_sublist_remove_node (gl_list_t list
, gl_list_node_t node
)
248 uintptr_t index
= NODE_TO_INDEX (node
);
249 if (!(index
< list
->end
- list
->start
))
250 /* Invalid argument. */
252 return gl_list_remove_at (list
->whole
, list
->start
+ index
);
256 gl_sublist_remove_at (gl_list_t list
, size_t position
)
258 if (!(position
< list
->end
- list
->start
))
259 /* Invalid argument. */
261 return gl_list_remove_at (list
->whole
, list
->start
+ position
);
265 gl_sublist_remove (gl_list_t list
, const void *elt
)
268 gl_list_indexof_from_to (list
->whole
, list
->start
, list
->end
, elt
);
269 if (position
== (size_t)(-1))
272 return gl_list_remove_at (list
->whole
, position
);
276 gl_sublist_list_free (gl_list_t list
)
281 /* --------------------- gl_list_iterator_t Data Type --------------------- */
283 static gl_list_iterator_t
284 gl_sublist_iterator (gl_list_t list
)
286 return gl_list_iterator_from_to (list
->whole
, list
->start
, list
->end
);
289 static gl_list_iterator_t
290 gl_sublist_iterator_from_to (gl_list_t list
,
291 size_t start_index
, size_t end_index
)
293 if (!(start_index
<= end_index
&& end_index
<= list
->end
- list
->start
))
294 /* Invalid arguments. */
296 return gl_list_iterator_from_to (list
->whole
,
297 list
->start
+ start_index
,
298 list
->start
+ end_index
);
302 gl_sublist_iterator_next (gl_list_iterator_t
*iterator
,
303 const void **eltp
, gl_list_node_t
*nodep
)
305 /* Shouldn't be called. */
310 gl_sublist_iterator_free (gl_list_iterator_t
*iterator
)
312 /* Shouldn't be called. */
316 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
318 static gl_list_node_t
319 gl_sublist_sortedlist_search (gl_list_t list
,
320 gl_listelement_compar_fn compar
,
324 gl_sortedlist_indexof_from_to (list
->whole
, compar
,
325 list
->start
, list
->end
, elt
);
326 if (index
!= (size_t)(-1))
327 return INDEX_TO_NODE (index
- list
->start
);
332 static gl_list_node_t
333 gl_sublist_sortedlist_search_from_to (gl_list_t list
,
334 gl_listelement_compar_fn compar
,
335 size_t low
, size_t high
,
340 if (!(low
<= high
&& high
<= list
->end
- list
->start
))
341 /* Invalid arguments. */
345 gl_sortedlist_indexof_from_to (list
->whole
, compar
,
346 list
->start
+ low
, list
->start
+ high
, elt
);
347 if (index
!= (size_t)(-1))
348 return INDEX_TO_NODE (index
- list
->start
);
354 gl_sublist_sortedlist_indexof (gl_list_t list
,
355 gl_listelement_compar_fn compar
,
359 gl_sortedlist_indexof_from_to (list
->whole
, compar
, list
->start
, list
->end
,
361 if (index
!= (size_t)(-1))
362 index
-= list
->start
;
367 gl_sublist_sortedlist_indexof_from_to (gl_list_t list
,
368 gl_listelement_compar_fn compar
,
369 size_t low
, size_t high
,
374 if (!(low
<= high
&& high
<= list
->end
- list
->start
))
375 /* Invalid arguments. */
378 index
= gl_sortedlist_indexof_from_to (list
->whole
, compar
,
379 list
->start
+ low
, list
->start
+ high
,
381 if (index
!= (size_t)(-1))
382 index
-= list
->start
;
386 static gl_list_node_t
387 gl_sublist_sortedlist_nx_add (gl_list_t list
,
388 gl_listelement_compar_fn compar
,
391 /* It's impossible to implement this method without risking to put the
392 whole list into unsorted order (namely, when the given ELT is smaller
393 or larger than all elements of the sublist). */
398 gl_sublist_sortedlist_remove (gl_list_t list
,
399 gl_listelement_compar_fn compar
,
402 size_t index
= gl_sublist_sortedlist_indexof (list
, compar
, elt
);
403 if (index
== (size_t)(-1))
406 return gl_sublist_remove_at (list
, index
);
410 static const struct gl_list_implementation gl_sublist_list_implementation
=
412 gl_sublist_nx_create_empty
,
413 gl_sublist_nx_create_fill
,
415 gl_sublist_node_value
,
416 gl_sublist_node_nx_set_value
,
417 gl_sublist_next_node
,
418 gl_sublist_previous_node
,
420 gl_sublist_nx_set_at
,
421 gl_sublist_search_from_to
,
422 gl_sublist_indexof_from_to
,
423 gl_sublist_nx_add_first
,
424 gl_sublist_nx_add_last
,
425 gl_sublist_nx_add_before
,
426 gl_sublist_nx_add_after
,
427 gl_sublist_nx_add_at
,
428 gl_sublist_remove_node
,
429 gl_sublist_remove_at
,
431 gl_sublist_list_free
,
433 gl_sublist_iterator_from_to
,
434 gl_sublist_iterator_next
,
435 gl_sublist_iterator_free
,
436 gl_sublist_sortedlist_search
,
437 gl_sublist_sortedlist_search_from_to
,
438 gl_sublist_sortedlist_indexof
,
439 gl_sublist_sortedlist_indexof_from_to
,
440 gl_sublist_sortedlist_nx_add
,
441 gl_sublist_sortedlist_remove
445 gl_sublist_nx_create (gl_list_t whole_list
, size_t start_index
, size_t end_index
)
447 if (!(start_index
<= end_index
&& end_index
<= gl_list_size (whole_list
)))
448 /* Invalid arguments. */
451 struct gl_list_impl
*list
=
452 (struct gl_list_impl
*) malloc (sizeof (struct gl_list_impl
));
457 list
->base
.vtable
= &gl_sublist_list_implementation
;
458 list
->base
.equals_fn
= whole_list
->base
.equals_fn
; /* actually unused */
459 list
->base
.hashcode_fn
= whole_list
->base
.hashcode_fn
; /* actually unused */
460 list
->base
.dispose_fn
= whole_list
->base
.dispose_fn
; /* actually unused */
461 list
->base
.allow_duplicates
= whole_list
->base
.allow_duplicates
; /* unused */
462 if (whole_list
->base
.vtable
== &gl_sublist_list_implementation
)
464 /* Optimization of a sublist of a sublist: Collapse the two
465 indirections into a single indirection. */
466 list
->whole
= whole_list
->whole
;
467 list
->start
= whole_list
->start
+ start_index
;
468 list
->end
= whole_list
->start
+ end_index
;
472 list
->whole
= whole_list
;
473 list
->start
= start_index
;
474 list
->end
= end_index
;