lib/gl_sublist.c

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