lib/gl_sublist.c

   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.
   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 <stdlib.h>
  24
  25 #ifndef uintptr_t
  26 # define uintptr_t unsigned long
  27 #endif
  28
  29 /* -------------------------- gl_list_t Data Type -------------------------- */
  30
  31 /* Concrete gl_list_impl type, valid for this file only.  */
  32 struct gl_list_impl
  33 {
  34   struct gl_list_impl_base base;
  35   /* Reference to the whole list.  */
  36   gl_list_t whole;
  37   /* Limits of the index range.  */
  38   size_t start;
  39   size_t end;
  40 };
  41
  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)
  48
  49 static gl_list_t
  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)
  55 {
  56   /* Shouldn't be called.  */
  57   abort ();
  58 }
  59
  60 static gl_list_t
  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)
  67 {
  68   /* Shouldn't be called.  */
  69   abort ();
  70 }
  71
  72 static size_t
  73 gl_sublist_size (gl_list_t list)
  74 {
  75   return list->end - list->start;
  76 }
  77
  78 static const void *
  79 gl_sublist_node_value (gl_list_t list, gl_list_node_t node)
  80 {
  81   uintptr_t index = NODE_TO_INDEX (node);
  82   if (!(index < list->end - list->start))
  83     /* Invalid argument.  */
  84     abort ();
  85   return gl_list_get_at (list->whole, list->start + index);
  86 }
  87
  88 static int
  89 gl_sublist_node_nx_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
  90 {
  91   uintptr_t index = NODE_TO_INDEX (node);
  92   if (!(index < list->end - list->start))
  93     /* Invalid argument.  */
  94     abort ();
  95   if (gl_list_nx_set_at (list->whole, list->start + index, elt) == NULL)
  96     return -1;
  97   return 0;
  98 }
  99
 100 static gl_list_node_t
 101 gl_sublist_next_node (gl_list_t list, gl_list_node_t node)
 102 {
 103   uintptr_t index = NODE_TO_INDEX (node);
 104   size_t count = list->end - list->start;
 105   if (!(index < count))
 106     /* Invalid argument.  */
 107     abort ();
 108   index++;
 109   if (index < count)
 110     return INDEX_TO_NODE (index);
 111   else
 112     return NULL;
 113 }
 114
 115 static gl_list_node_t
 116 gl_sublist_previous_node (gl_list_t list, gl_list_node_t node)
 117 {
 118   uintptr_t index = NODE_TO_INDEX (node);
 119   if (!(index < list->end - list->start))
 120     /* Invalid argument.  */
 121     abort ();
 122   if (index > 0)
 123     return INDEX_TO_NODE (index - 1);
 124   else
 125     return NULL;
 126 }
 127
 128 static const void *
 129 gl_sublist_get_at (gl_list_t list, size_t position)
 130 {
 131   if (!(position < list->end - list->start))
 132     /* Invalid argument.  */
 133     abort ();
 134   return gl_list_get_at (list->whole, list->start + position);
 135 }
 136
 137 static gl_list_node_t
 138 gl_sublist_nx_set_at (gl_list_t list, size_t position, const void *elt)
 139 {
 140   if (!(position < list->end - list->start))
 141     /* Invalid argument.  */
 142     abort ();
 143   if (gl_list_nx_set_at (list->whole, list->start + position, elt) == NULL)
 144     return NULL;
 145   return INDEX_TO_NODE (position);
 146 }
 147
 148 static gl_list_node_t
 149 gl_sublist_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
 150                            const void *elt)
 151 {
 152   if (!(start_index <= end_index && end_index <= list->end - list->start))
 153     /* Invalid arguments.  */
 154     abort ();
 155   {
 156     size_t index =
 157       gl_list_indexof_from_to (list->whole,
 158                                list->start + start_index,
 159                                list->start + end_index,
 160                                elt);
 161     if (index != (size_t)(-1))
 162       return INDEX_TO_NODE (index - list->start);
 163     else
 164       return NULL;
 165   }
 166 }
 167
 168 static size_t
 169 gl_sublist_indexof_from_to (gl_list_t list,
 170                             size_t start_index, size_t end_index,
 171                             const void *elt)
 172 {
 173   if (!(start_index <= end_index && end_index <= list->end - list->start))
 174     /* Invalid arguments.  */
 175     abort ();
 176   {
 177     size_t index =
 178       gl_list_indexof_from_to (list->whole,
 179                                list->start + start_index,
 180                                list->start + end_index,
 181                                elt);
 182     if (index != (size_t)(-1))
 183       index -= list->start;
 184     return index;
 185   }
 186 }
 187
 188 static gl_list_node_t
 189 gl_sublist_nx_add_first (gl_list_t list, const void *elt)
 190 {
 191   if (gl_list_nx_add_at (list->whole, list->start, elt) == NULL)
 192     return NULL;
 193   list->end++;
 194   return INDEX_TO_NODE (0);
 195 }
 196
 197 static gl_list_node_t
 198 gl_sublist_nx_add_last (gl_list_t list, const void *elt)
 199 {
 200   if (gl_list_nx_add_at (list->whole, list->end, elt) == NULL)
 201     return NULL;
 202   list->end++;
 203   return INDEX_TO_NODE (list->end - list->start - 1);
 204 }
 205
 206 static gl_list_node_t
 207 gl_sublist_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 208 {
 209   size_t position = NODE_TO_INDEX (node);
 210   if (!(position < list->end - list->start))
 211     /* Invalid argument.  */
 212     abort ();
 213   if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL)
 214     return NULL;
 215   list->end++;
 216   return INDEX_TO_NODE (position);
 217 }
 218
 219 static gl_list_node_t
 220 gl_sublist_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 221 {
 222   size_t position = NODE_TO_INDEX (node);
 223   if (!(position < list->end - list->start))
 224     /* Invalid argument.  */
 225     abort ();
 226   position++;
 227   if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL)
 228     return NULL;
 229   list->end++;
 230   return INDEX_TO_NODE (position);
 231 }
 232
 233 static gl_list_node_t
 234 gl_sublist_nx_add_at (gl_list_t list, size_t position, const void *elt)
 235 {
 236   if (!(position <= list->end - list->start))
 237     /* Invalid argument.  */
 238     abort ();
 239   if (gl_list_nx_add_at (list->whole, list->start + position, elt) == NULL)
 240     return NULL;
 241   list->end++;
 242   return INDEX_TO_NODE (position);
 243 }
 244
 245 static bool
 246 gl_sublist_remove_node (gl_list_t list, gl_list_node_t node)
 247 {
 248   uintptr_t index = NODE_TO_INDEX (node);
 249   if (!(index < list->end - list->start))
 250     /* Invalid argument.  */
 251     abort ();
 252   return gl_list_remove_at (list->whole, list->start + index);
 253 }
 254
 255 static bool
 256 gl_sublist_remove_at (gl_list_t list, size_t position)
 257 {
 258   if (!(position < list->end - list->start))
 259     /* Invalid argument.  */
 260     abort ();
 261   return gl_list_remove_at (list->whole, list->start + position);
 262 }
 263
 264 static bool
 265 gl_sublist_remove (gl_list_t list, const void *elt)
 266 {
 267   size_t position =
 268     gl_list_indexof_from_to (list->whole, list->start, list->end, elt);
 269   if (position == (size_t)(-1))
 270     return false;
 271   else
 272     return gl_list_remove_at (list->whole, position);
 273 }
 274
 275 static void
 276 gl_sublist_list_free (gl_list_t list)
 277 {
 278   free (list);
 279 }
 280
 281 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 282
 283 static gl_list_iterator_t
 284 gl_sublist_iterator (gl_list_t list)
 285 {
 286   return gl_list_iterator_from_to (list->whole, list->start, list->end);
 287 }
 288
 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)
 292 {
 293   if (!(start_index <= end_index && end_index <= list->end - list->start))
 294     /* Invalid arguments.  */
 295     abort ();
 296   return gl_list_iterator_from_to (list->whole,
 297                                    list->start + start_index,
 298                                    list->start + end_index);
 299 }
 300
 301 static bool
 302 gl_sublist_iterator_next (gl_list_iterator_t *iterator,
 303                           const void **eltp, gl_list_node_t *nodep)
 304 {
 305   /* Shouldn't be called.  */
 306   abort ();
 307 }
 308
 309 static void
 310 gl_sublist_iterator_free (gl_list_iterator_t *iterator)
 311 {
 312   /* Shouldn't be called.  */
 313   abort ();
 314 }
 315
 316 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 317
 318 static gl_list_node_t
 319 gl_sublist_sortedlist_search (gl_list_t list,
 320                               gl_listelement_compar_fn compar,
 321                               const void *elt)
 322 {
 323   size_t index =
 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);
 328   else
 329     return NULL;
 330 }
 331
 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,
 336                                       const void *elt)
 337 {
 338   size_t index;
 339
 340   if (!(low <= high && high <= list->end - list->start))
 341     /* Invalid arguments.  */
 342     abort ();
 343
 344   index =
 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);
 349   else
 350     return NULL;
 351 }
 352
 353 static size_t
 354 gl_sublist_sortedlist_indexof (gl_list_t list,
 355                                gl_listelement_compar_fn compar,
 356                                const void *elt)
 357 {
 358   size_t index =
 359     gl_sortedlist_indexof_from_to (list->whole, compar, list->start, list->end,
 360                                    elt);
 361   if (index != (size_t)(-1))
 362     index -= list->start;
 363   return index;
 364 }
 365
 366 static size_t
 367 gl_sublist_sortedlist_indexof_from_to (gl_list_t list,
 368                                        gl_listelement_compar_fn compar,
 369                                        size_t low, size_t high,
 370                                        const void *elt)
 371 {
 372   size_t index;
 373
 374   if (!(low <= high && high <= list->end - list->start))
 375     /* Invalid arguments.  */
 376     abort ();
 377
 378   index = gl_sortedlist_indexof_from_to (list->whole, compar,
 379                                          list->start + low, list->start + high,
 380                                          elt);
 381   if (index != (size_t)(-1))
 382     index -= list->start;
 383   return index;
 384 }
 385
 386 static gl_list_node_t
 387 gl_sublist_sortedlist_nx_add (gl_list_t list,
 388                               gl_listelement_compar_fn compar,
 389                               const void *elt)
 390 {
 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).  */
 394   abort ();
 395 }
 396
 397 static bool
 398 gl_sublist_sortedlist_remove (gl_list_t list,
 399                               gl_listelement_compar_fn compar,
 400                               const void *elt)
 401 {
 402   size_t index = gl_sublist_sortedlist_indexof (list, compar, elt);
 403   if (index == (size_t)(-1))
 404     return false;
 405   else
 406     return gl_sublist_remove_at (list, index);
 407 }
 408
 409
 410 static const struct gl_list_implementation gl_sublist_list_implementation =
 411   {
 412     gl_sublist_nx_create_empty,
 413     gl_sublist_nx_create_fill,
 414     gl_sublist_size,
 415     gl_sublist_node_value,
 416     gl_sublist_node_nx_set_value,
 417     gl_sublist_next_node,
 418     gl_sublist_previous_node,
 419     gl_sublist_get_at,
 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,
 430     gl_sublist_remove,
 431     gl_sublist_list_free,
 432     gl_sublist_iterator,
 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
 442   };
 443
 444 gl_list_t
 445 gl_sublist_nx_create (gl_list_t whole_list, size_t start_index, size_t end_index)
 446 {
 447   if (!(start_index <= end_index && end_index <= gl_list_size (whole_list)))
 448     /* Invalid arguments.  */
 449     abort ();
 450   {
 451     struct gl_list_impl *list =
 452       (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
 453
 454     if (list == NULL)
 455       return NULL;
 456
 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)
 463       {
 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;
 469       }
 470     else
 471       {
 472         list->whole = whole_list;
 473         list->start = start_index;
 474         list->end = end_index;
 475       }
 476
 477     return list;
 478   }
 479 }