lib/gl_sublist.c

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