lib/gl_sublist.c

   1 /* Sequential list data type backed by another list.
   2    Copyright (C) 2006-2024 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2006.
   4
   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.
   9
  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.
  14
  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/>.  */
  17
  18 #include <config.h>
  19
  20 /* Specification.  */
  21 #include "gl_sublist.h"
  22
  23 #include <stdint.h>
  24 #include <stdlib.h>
  25
  26 /* -------------------------- gl_list_t Data Type -------------------------- */
  27
  28 /* Concrete gl_list_impl type, valid for this file only.  */
  29 struct gl_list_impl
  30 {
  31   struct gl_list_impl_base base;
  32   /* Reference to the whole list.  */
  33   gl_list_t whole;
  34   /* Limits of the index range.  */
  35   size_t start;
  36   size_t end;
  37 };
  38
  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)
  45
  46 static gl_list_t
  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)
  52 {
  53   /* Shouldn't be called.  */
  54   abort ();
  55 }
  56
  57 static gl_list_t
  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)
  64 {
  65   /* Shouldn't be called.  */
  66   abort ();
  67 }
  68
  69 static size_t
  70 gl_sublist_size (gl_list_t list)
  71 {
  72   return list->end - list->start;
  73 }
  74
  75 static const void *
  76 gl_sublist_node_value (gl_list_t list, gl_list_node_t node)
  77 {
  78   uintptr_t index = NODE_TO_INDEX (node);
  79   if (!(index < list->end - list->start))
  80     /* Invalid argument.  */
  81     abort ();
  82   return gl_list_get_at (list->whole, list->start + index);
  83 }
  84
  85 static int
  86 gl_sublist_node_nx_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
  87 {
  88   uintptr_t index = NODE_TO_INDEX (node);
  89   if (!(index < list->end - list->start))
  90     /* Invalid argument.  */
  91     abort ();
  92   if (gl_list_nx_set_at (list->whole, list->start + index, elt) == NULL)
  93     return -1;
  94   return 0;
  95 }
  96
  97 static gl_list_node_t
  98 gl_sublist_next_node (gl_list_t list, gl_list_node_t node)
  99 {
 100   uintptr_t index = NODE_TO_INDEX (node);
 101   size_t count = list->end - list->start;
 102   if (!(index < count))
 103     /* Invalid argument.  */
 104     abort ();
 105   index++;
 106   if (index < count)
 107     return INDEX_TO_NODE (index);
 108   else
 109     return NULL;
 110 }
 111
 112 static gl_list_node_t
 113 gl_sublist_previous_node (gl_list_t list, gl_list_node_t node)
 114 {
 115   uintptr_t index = NODE_TO_INDEX (node);
 116   if (!(index < list->end - list->start))
 117     /* Invalid argument.  */
 118     abort ();
 119   if (index > 0)
 120     return INDEX_TO_NODE (index - 1);
 121   else
 122     return NULL;
 123 }
 124
 125 static gl_list_node_t
 126 gl_sublist_first_node (gl_list_t list)
 127 {
 128   if (list->end > list->start)
 129     return INDEX_TO_NODE (0);
 130   else
 131     return NULL;
 132 }
 133
 134 static gl_list_node_t
 135 gl_sublist_last_node (gl_list_t list)
 136 {
 137   size_t count = list->end - list->start;
 138   if (count > 0)
 139     return INDEX_TO_NODE (count - 1);
 140   else
 141     return NULL;
 142 }
 143
 144 static const void *
 145 gl_sublist_get_at (gl_list_t list, size_t position)
 146 {
 147   if (!(position < list->end - list->start))
 148     /* Invalid argument.  */
 149     abort ();
 150   return gl_list_get_at (list->whole, list->start + position);
 151 }
 152
 153 static gl_list_node_t
 154 gl_sublist_nx_set_at (gl_list_t list, size_t position, const void *elt)
 155 {
 156   if (!(position < list->end - list->start))
 157     /* Invalid argument.  */
 158     abort ();
 159   if (gl_list_nx_set_at (list->whole, list->start + position, elt) == NULL)
 160     return NULL;
 161   return INDEX_TO_NODE (position);
 162 }
 163
 164 static gl_list_node_t
 165 gl_sublist_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
 166                            const void *elt)
 167 {
 168   if (!(start_index <= end_index && end_index <= list->end - list->start))
 169     /* Invalid arguments.  */
 170     abort ();
 171   {
 172     size_t index =
 173       gl_list_indexof_from_to (list->whole,
 174                                list->start + start_index,
 175                                list->start + end_index,
 176                                elt);
 177     if (index != (size_t)(-1))
 178       return INDEX_TO_NODE (index - list->start);
 179     else
 180       return NULL;
 181   }
 182 }
 183
 184 static size_t
 185 gl_sublist_indexof_from_to (gl_list_t list,
 186                             size_t start_index, size_t end_index,
 187                             const void *elt)
 188 {
 189   if (!(start_index <= end_index && end_index <= list->end - list->start))
 190     /* Invalid arguments.  */
 191     abort ();
 192   {
 193     size_t index =
 194       gl_list_indexof_from_to (list->whole,
 195                                list->start + start_index,
 196                                list->start + end_index,
 197                                elt);
 198     if (index != (size_t)(-1))
 199       index -= list->start;
 200     return index;
 201   }
 202 }
 203
 204 static gl_list_node_t
 205 gl_sublist_nx_add_first (gl_list_t list, const void *elt)
 206 {
 207   if (gl_list_nx_add_at (list->whole, list->start, elt) == NULL)
 208     return NULL;
 209   list->end++;
 210   return INDEX_TO_NODE (0);
 211 }
 212
 213 static gl_list_node_t
 214 gl_sublist_nx_add_last (gl_list_t list, const void *elt)
 215 {
 216   if (gl_list_nx_add_at (list->whole, list->end, elt) == NULL)
 217     return NULL;
 218   list->end++;
 219   return INDEX_TO_NODE (list->end - list->start - 1);
 220 }
 221
 222 static gl_list_node_t
 223 gl_sublist_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 224 {
 225   size_t position = NODE_TO_INDEX (node);
 226   if (!(position < list->end - list->start))
 227     /* Invalid argument.  */
 228     abort ();
 229   if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL)
 230     return NULL;
 231   list->end++;
 232   return INDEX_TO_NODE (position);
 233 }
 234
 235 static gl_list_node_t
 236 gl_sublist_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 237 {
 238   size_t position = NODE_TO_INDEX (node);
 239   if (!(position < list->end - list->start))
 240     /* Invalid argument.  */
 241     abort ();
 242   position++;
 243   if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL)
 244     return NULL;
 245   list->end++;
 246   return INDEX_TO_NODE (position);
 247 }
 248
 249 static gl_list_node_t
 250 gl_sublist_nx_add_at (gl_list_t list, size_t position, const void *elt)
 251 {
 252   if (!(position <= list->end - list->start))
 253     /* Invalid argument.  */
 254     abort ();
 255   if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL)
 256     return NULL;
 257   list->end++;
 258   return INDEX_TO_NODE (position);
 259 }
 260
 261 static bool
 262 gl_sublist_remove_node (gl_list_t list, gl_list_node_t node)
 263 {
 264   uintptr_t index = NODE_TO_INDEX (node);
 265   if (!(index < list->end - list->start))
 266     /* Invalid argument.  */
 267     abort ();
 268   return gl_list_remove_at (list->whole, list->start + index);
 269 }
 270
 271 static bool
 272 gl_sublist_remove_at (gl_list_t list, size_t position)
 273 {
 274   if (!(position < list->end - list->start))
 275     /* Invalid argument.  */
 276     abort ();
 277   return gl_list_remove_at (list->whole, list->start + position);
 278 }
 279
 280 static bool
 281 gl_sublist_remove (gl_list_t list, const void *elt)
 282 {
 283   size_t position =
 284     gl_list_indexof_from_to (list->whole, list->start, list->end, elt);
 285   if (position == (size_t)(-1))
 286     return false;
 287   else
 288     return gl_list_remove_at (list->whole, position);
 289 }
 290
 291 static void
 292 gl_sublist_list_free (gl_list_t list)
 293 {
 294   free (list);
 295 }
 296
 297 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 298
 299 static gl_list_iterator_t
 300 gl_sublist_iterator (gl_list_t list)
 301 {
 302   return gl_list_iterator_from_to (list->whole, list->start, list->end);
 303 }
 304
 305 static gl_list_iterator_t
 306 gl_sublist_iterator_from_to (gl_list_t list,
 307                              size_t start_index, size_t end_index)
 308 {
 309   if (!(start_index <= end_index && end_index <= list->end - list->start))
 310     /* Invalid arguments.  */
 311     abort ();
 312   return gl_list_iterator_from_to (list->whole,
 313                                    list->start + start_index,
 314                                    list->start + end_index);
 315 }
 316
 317 static bool
 318 gl_sublist_iterator_next (gl_list_iterator_t *iterator,
 319                           const void **eltp, gl_list_node_t *nodep)
 320 {
 321   /* Shouldn't be called.  */
 322   abort ();
 323 }
 324
 325 static void
 326 gl_sublist_iterator_free (gl_list_iterator_t *iterator)
 327 {
 328   /* Shouldn't be called.  */
 329   abort ();
 330 }
 331
 332 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 333
 334 static gl_list_node_t
 335 gl_sublist_sortedlist_search (gl_list_t list,
 336                               gl_listelement_compar_fn compar,
 337                               const void *elt)
 338 {
 339   size_t index =
 340     gl_sortedlist_indexof_from_to (list->whole, compar,
 341                                    list->start, list->end, elt);
 342   if (index != (size_t)(-1))
 343     return INDEX_TO_NODE (index - list->start);
 344   else
 345     return NULL;
 346 }
 347
 348 static gl_list_node_t
 349 gl_sublist_sortedlist_search_from_to (gl_list_t list,
 350                                       gl_listelement_compar_fn compar,
 351                                       size_t low, size_t high,
 352                                       const void *elt)
 353 {
 354   size_t index;
 355
 356   if (!(low <= high && high <= list->end - list->start))
 357     /* Invalid arguments.  */
 358     abort ();
 359
 360   index =
 361     gl_sortedlist_indexof_from_to (list->whole, compar,
 362                                    list->start + low, list->start + high, elt);
 363   if (index != (size_t)(-1))
 364     return INDEX_TO_NODE (index - list->start);
 365   else
 366     return NULL;
 367 }
 368
 369 static size_t
 370 gl_sublist_sortedlist_indexof (gl_list_t list,
 371                                gl_listelement_compar_fn compar,
 372                                const void *elt)
 373 {
 374   size_t index =
 375     gl_sortedlist_indexof_from_to (list->whole, compar, list->start, list->end,
 376                                    elt);
 377   if (index != (size_t)(-1))
 378     index -= list->start;
 379   return index;
 380 }
 381
 382 static size_t
 383 gl_sublist_sortedlist_indexof_from_to (gl_list_t list,
 384                                        gl_listelement_compar_fn compar,
 385                                        size_t low, size_t high,
 386                                        const void *elt)
 387 {
 388   size_t index;
 389
 390   if (!(low <= high && high <= list->end - list->start))
 391     /* Invalid arguments.  */
 392     abort ();
 393
 394   index = gl_sortedlist_indexof_from_to (list->whole, compar,
 395                                          list->start + low, list->start + high,
 396                                          elt);
 397   if (index != (size_t)(-1))
 398     index -= list->start;
 399   return index;
 400 }
 401
 402 static gl_list_node_t
 403 gl_sublist_sortedlist_nx_add (gl_list_t list,
 404                               gl_listelement_compar_fn compar,
 405                               const void *elt)
 406 {
 407   /* It's impossible to implement this method without risking to put the
 408      whole list into unsorted order (namely, when the given ELT is smaller
 409      or larger than all elements of the sublist).  */
 410   abort ();
 411 }
 412
 413 static bool
 414 gl_sublist_sortedlist_remove (gl_list_t list,
 415                               gl_listelement_compar_fn compar,
 416                               const void *elt)
 417 {
 418   size_t index = gl_sublist_sortedlist_indexof (list, compar, elt);
 419   if (index == (size_t)(-1))
 420     return false;
 421   else
 422     return gl_sublist_remove_at (list, index);
 423 }
 424
 425
 426 static const struct gl_list_implementation gl_sublist_list_implementation =
 427   {
 428     gl_sublist_nx_create_empty,
 429     gl_sublist_nx_create_fill,
 430     gl_sublist_size,
 431     gl_sublist_node_value,
 432     gl_sublist_node_nx_set_value,
 433     gl_sublist_next_node,
 434     gl_sublist_previous_node,
 435     gl_sublist_first_node,
 436     gl_sublist_last_node,
 437     gl_sublist_get_at,
 438     gl_sublist_nx_set_at,
 439     gl_sublist_search_from_to,
 440     gl_sublist_indexof_from_to,
 441     gl_sublist_nx_add_first,
 442     gl_sublist_nx_add_last,
 443     gl_sublist_nx_add_before,
 444     gl_sublist_nx_add_after,
 445     gl_sublist_nx_add_at,
 446     gl_sublist_remove_node,
 447     gl_sublist_remove_at,
 448     gl_sublist_remove,
 449     gl_sublist_list_free,
 450     gl_sublist_iterator,
 451     gl_sublist_iterator_from_to,
 452     gl_sublist_iterator_next,
 453     gl_sublist_iterator_free,
 454     gl_sublist_sortedlist_search,
 455     gl_sublist_sortedlist_search_from_to,
 456     gl_sublist_sortedlist_indexof,
 457     gl_sublist_sortedlist_indexof_from_to,
 458     gl_sublist_sortedlist_nx_add,
 459     gl_sublist_sortedlist_remove
 460   };
 461
 462 gl_list_t
 463 gl_sublist_nx_create (gl_list_t whole_list, size_t start_index, size_t end_index)
 464 {
 465   if (!(start_index <= end_index && end_index <= gl_list_size (whole_list)))
 466     /* Invalid arguments.  */
 467     abort ();
 468   {
 469     struct gl_list_impl *list =
 470       (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
 471
 472     if (list == NULL)
 473       return NULL;
 474
 475     list->base.vtable = &gl_sublist_list_implementation;
 476     list->base.equals_fn = whole_list->base.equals_fn; /* actually unused */
 477     list->base.hashcode_fn = whole_list->base.hashcode_fn; /* actually unused */
 478     list->base.dispose_fn = whole_list->base.dispose_fn; /* actually unused */
 479     list->base.allow_duplicates = whole_list->base.allow_duplicates; /* unused */
 480     if (whole_list->base.vtable == &gl_sublist_list_implementation)
 481       {
 482         /* Optimization of a sublist of a sublist: Collapse the two
 483            indirections into a single indirection.  */
 484         list->whole = whole_list->whole;
 485         list->start = whole_list->start + start_index;
 486         list->end = whole_list->start + end_index;
 487       }
 488     else
 489       {
 490         list->whole = whole_list;
 491         list->start = start_index;
 492         list->end = end_index;
 493       }
 494
 495     return list;
 496   }
 497 }