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