lib/gl_sublist.c

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