lib/gl_sublist.c

   1 /* Sequential list data type backed by another list.
   2    Copyright (C) 2006-2020 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 const void *
 126 gl_sublist_get_at (gl_list_t list, size_t position)
 127 {
 128   if (!(position < list->end - list->start))
 129     /* Invalid argument.  */
 130     abort ();
 131   return gl_list_get_at (list->whole, list->start + position);
 132 }
 133
 134 static gl_list_node_t
 135 gl_sublist_nx_set_at (gl_list_t list, size_t position, const void *elt)
 136 {
 137   if (!(position < list->end - list->start))
 138     /* Invalid argument.  */
 139     abort ();
 140   if (gl_list_nx_set_at (list->whole, list->start + position, elt) == NULL)
 141     return NULL;
 142   return INDEX_TO_NODE (position);
 143 }
 144
 145 static gl_list_node_t
 146 gl_sublist_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
 147                            const void *elt)
 148 {
 149   if (!(start_index <= end_index && end_index <= list->end - list->start))
 150     /* Invalid arguments.  */
 151     abort ();
 152   {
 153     size_t index =
 154       gl_list_indexof_from_to (list->whole,
 155                                list->start + start_index,
 156                                list->start + end_index,
 157                                elt);
 158     if (index != (size_t)(-1))
 159       return INDEX_TO_NODE (index - list->start);
 160     else
 161       return NULL;
 162   }
 163 }
 164
 165 static size_t
 166 gl_sublist_indexof_from_to (gl_list_t list,
 167                             size_t start_index, size_t end_index,
 168                             const void *elt)
 169 {
 170   if (!(start_index <= end_index && end_index <= list->end - list->start))
 171     /* Invalid arguments.  */
 172     abort ();
 173   {
 174     size_t index =
 175       gl_list_indexof_from_to (list->whole,
 176                                list->start + start_index,
 177                                list->start + end_index,
 178                                elt);
 179     if (index != (size_t)(-1))
 180       index -= list->start;
 181     return index;
 182   }
 183 }
 184
 185 static gl_list_node_t
 186 gl_sublist_nx_add_first (gl_list_t list, const void *elt)
 187 {
 188   if (gl_list_nx_add_at (list->whole, list->start, elt) == NULL)
 189     return NULL;
 190   list->end++;
 191   return INDEX_TO_NODE (0);
 192 }
 193
 194 static gl_list_node_t
 195 gl_sublist_nx_add_last (gl_list_t list, const void *elt)
 196 {
 197   if (gl_list_nx_add_at (list->whole, list->end, elt) == NULL)
 198     return NULL;
 199   list->end++;
 200   return INDEX_TO_NODE (list->end - list->start - 1);
 201 }
 202
 203 static gl_list_node_t
 204 gl_sublist_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 205 {
 206   size_t position = NODE_TO_INDEX (node);
 207   if (!(position < list->end - list->start))
 208     /* Invalid argument.  */
 209     abort ();
 210   if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL)
 211     return NULL;
 212   list->end++;
 213   return INDEX_TO_NODE (position);
 214 }
 215
 216 static gl_list_node_t
 217 gl_sublist_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 218 {
 219   size_t position = NODE_TO_INDEX (node);
 220   if (!(position < list->end - list->start))
 221     /* Invalid argument.  */
 222     abort ();
 223   position++;
 224   if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL)
 225     return NULL;
 226   list->end++;
 227   return INDEX_TO_NODE (position);
 228 }
 229
 230 static gl_list_node_t
 231 gl_sublist_nx_add_at (gl_list_t list, size_t position, const void *elt)
 232 {
 233   if (!(position <= list->end - list->start))
 234     /* Invalid argument.  */
 235     abort ();
 236   if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL)
 237     return NULL;
 238   list->end++;
 239   return INDEX_TO_NODE (position);
 240 }
 241
 242 static bool
 243 gl_sublist_remove_node (gl_list_t list, gl_list_node_t node)
 244 {
 245   uintptr_t index = NODE_TO_INDEX (node);
 246   if (!(index < list->end - list->start))
 247     /* Invalid argument.  */
 248     abort ();
 249   return gl_list_remove_at (list->whole, list->start + index);
 250 }
 251
 252 static bool
 253 gl_sublist_remove_at (gl_list_t list, size_t position)
 254 {
 255   if (!(position < list->end - list->start))
 256     /* Invalid argument.  */
 257     abort ();
 258   return gl_list_remove_at (list->whole, list->start + position);
 259 }
 260
 261 static bool
 262 gl_sublist_remove (gl_list_t list, const void *elt)
 263 {
 264   size_t position =
 265     gl_list_indexof_from_to (list->whole, list->start, list->end, elt);
 266   if (position == (size_t)(-1))
 267     return false;
 268   else
 269     return gl_list_remove_at (list->whole, position);
 270 }
 271
 272 static void
 273 gl_sublist_list_free (gl_list_t list)
 274 {
 275   free (list);
 276 }
 277
 278 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 279
 280 static gl_list_iterator_t
 281 gl_sublist_iterator (gl_list_t list)
 282 {
 283   return gl_list_iterator_from_to (list->whole, list->start, list->end);
 284 }
 285
 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)
 289 {
 290   if (!(start_index <= end_index && end_index <= list->end - list->start))
 291     /* Invalid arguments.  */
 292     abort ();
 293   return gl_list_iterator_from_to (list->whole,
 294                                    list->start + start_index,
 295                                    list->start + end_index);
 296 }
 297
 298 static bool
 299 gl_sublist_iterator_next (gl_list_iterator_t *iterator,
 300                           const void **eltp, gl_list_node_t *nodep)
 301 {
 302   /* Shouldn't be called.  */
 303   abort ();
 304 }
 305
 306 static void
 307 gl_sublist_iterator_free (gl_list_iterator_t *iterator)
 308 {
 309   /* Shouldn't be called.  */
 310   abort ();
 311 }
 312
 313 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 314
 315 static gl_list_node_t
 316 gl_sublist_sortedlist_search (gl_list_t list,
 317                               gl_listelement_compar_fn compar,
 318                               const void *elt)
 319 {
 320   size_t index =
 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);
 325   else
 326     return NULL;
 327 }
 328
 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,
 333                                       const void *elt)
 334 {
 335   size_t index;
 336
 337   if (!(low <= high && high <= list->end - list->start))
 338     /* Invalid arguments.  */
 339     abort ();
 340
 341   index =
 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);
 346   else
 347     return NULL;
 348 }
 349
 350 static size_t
 351 gl_sublist_sortedlist_indexof (gl_list_t list,
 352                                gl_listelement_compar_fn compar,
 353                                const void *elt)
 354 {
 355   size_t index =
 356     gl_sortedlist_indexof_from_to (list->whole, compar, list->start, list->end,
 357                                    elt);
 358   if (index != (size_t)(-1))
 359     index -= list->start;
 360   return index;
 361 }
 362
 363 static size_t
 364 gl_sublist_sortedlist_indexof_from_to (gl_list_t list,
 365                                        gl_listelement_compar_fn compar,
 366                                        size_t low, size_t high,
 367                                        const void *elt)
 368 {
 369   size_t index;
 370
 371   if (!(low <= high && high <= list->end - list->start))
 372     /* Invalid arguments.  */
 373     abort ();
 374
 375   index = gl_sortedlist_indexof_from_to (list->whole, compar,
 376                                          list->start + low, list->start + high,
 377                                          elt);
 378   if (index != (size_t)(-1))
 379     index -= list->start;
 380   return index;
 381 }
 382
 383 static gl_list_node_t
 384 gl_sublist_sortedlist_nx_add (gl_list_t list,
 385                               gl_listelement_compar_fn compar,
 386                               const void *elt)
 387 {
 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).  */
 391   abort ();
 392 }
 393
 394 static bool
 395 gl_sublist_sortedlist_remove (gl_list_t list,
 396                               gl_listelement_compar_fn compar,
 397                               const void *elt)
 398 {
 399   size_t index = gl_sublist_sortedlist_indexof (list, compar, elt);
 400   if (index == (size_t)(-1))
 401     return false;
 402   else
 403     return gl_sublist_remove_at (list, index);
 404 }
 405
 406
 407 static const struct gl_list_implementation gl_sublist_list_implementation =
 408   {
 409     gl_sublist_nx_create_empty,
 410     gl_sublist_nx_create_fill,
 411     gl_sublist_size,
 412     gl_sublist_node_value,
 413     gl_sublist_node_nx_set_value,
 414     gl_sublist_next_node,
 415     gl_sublist_previous_node,
 416     gl_sublist_get_at,
 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,
 427     gl_sublist_remove,
 428     gl_sublist_list_free,
 429     gl_sublist_iterator,
 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
 439   };
 440
 441 gl_list_t
 442 gl_sublist_nx_create (gl_list_t whole_list, size_t start_index, size_t end_index)
 443 {
 444   if (!(start_index <= end_index && end_index <= gl_list_size (whole_list)))
 445     /* Invalid arguments.  */
 446     abort ();
 447   {
 448     struct gl_list_impl *list =
 449       (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
 450
 451     if (list == NULL)
 452       return NULL;
 453
 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)
 460       {
 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;
 466       }
 467     else
 468       {
 469         list->whole = whole_list;
 470         list->start = start_index;
 471         list->end = end_index;
 472       }
 473
 474     return list;
 475   }
 476 }