src/libpspp/ll.h

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2006, 2009 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  16
  17 /* Circular doubly linked lists.
  18
  19    This header (ll.h) supplies "embedded" circular doubly linked
  20    lists.  Its companion header (llx.h) supplies "external"
  21    circular doubly linked lists.  The two variants are described
  22    briefly here.  The embedded variant, for which this is the
  23    header, is described in slightly more detail below.  Each
  24    function also has a detailed usage comment at its point of
  25    definition.
  26
  27    The "ll" embedded linked list implementation puts the linked
  28    list node within the data structure that the list contains.
  29    This makes allocation efficient, in space and time.  It also
  30    makes it easy to find the list node associated with a given
  31    object.  However, it's difficult to include a given object in
  32    an arbitrary number of lists, or to include a single object in
  33    a single list in multiple positions.
  34
  35    The "llx" external linked list implementation allocates linked
  36    list nodes separately from the objects in the list.  Adding
  37    and removing linked list nodes requires dynamic allocation, so
  38    it is normally slower and takes more memory than the embedded
  39    implementation.  It also requires searching the list to find
  40    the list node associated with a given object.  However, it's
  41    easy to include a given object in an arbitrary number of
  42    lists, or to include a single object more than once within a
  43    single list.  It's also possible to create an external linked
  44    list without adding a member to the data structure that the
  45    list contains. */
  46
  47 #ifndef LL_H
  48 #define LL_H
  49
  50 #include <assert.h>
  51 #include <stdbool.h>
  52 #include <stddef.h>
  53 #include <libpspp/cast.h>
  54
  55 #include <libpspp/cast.h>
  56
  57 /* Embedded, circular doubly linked list.
  58
  59    Each list contains a single "null" element that separates the
  60    head and the tail of the list.  The null element is both
  61    before the head and after the tail of the list.  An empty list
  62    contains just the null element.
  63
  64    An embedded linked list is represented as `struct ll_list'.
  65    Each node in the list, presumably a structure type, must
  66    include a `struct ll' member.
  67
  68    Many list functions take ranges of nodes as arguments.  Ranges
  69    are "half-open"; that is, R0...R1 includes R0 but not R1.  A
  70    range whose endpoints are the same (e.g. R0...R0) contains no
  71    nodes at all.
  72
  73    Here's an example of a structure type that includes a `struct
  74    ll':
  75
  76      struct ll_list list;
  77
  78      struct foo
  79        {
  80          struct ll ll;            // List member.
  81          int x;                   // Another member.
  82        };
  83
  84    Here's an example of iteration from head to tail:
  85
  86      struct ll *ll;
  87      for (ll = ll_head (&list); ll != ll_null (&list); ll = ll_next (ll))
  88        {
  89          struct foo *foo = ll_data (ll, struct foo, ll);
  90          ...do something with foo->x...
  91        }
  92
  93    Here's another way to do it:
  94
  95      struct ll *ll = ll_null (&list);
  96      while ((ll = ll_next (ll)) != ll_null (&list))
  97        {
  98          struct foo *foo = ll_data (ll, struct foo, ll);
  99          ...do something with foo->x...
 100        }
 101
 102    Here's a third way:
 103
 104      struct foo *foo;
 105      ll_for_each (foo, struct foo, ll, &list)
 106        {
 107          ...do something with foo->x...
 108        }
 109 */
 110
 111 /* Returns the data structure corresponding to the given node LL,
 112    assuming that LL is embedded as the given MEMBER name in data
 113    type STRUCT. */
 114 #define ll_data(LL, STRUCT, MEMBER)                     \
 115         (CHECK_POINTER_HAS_TYPE(LL, struct ll *),       \
 116          UP_CAST(LL, STRUCT, MEMBER))
 117
 118 /* Linked list node. */
 119 struct ll
 120   {
 121     struct ll *next;    /* Next node. */
 122     struct ll *prev;    /* Previous node. */
 123   };
 124
 125 /* Linked list. */
 126 struct ll_list
 127   {
 128     struct ll null;     /* Null node. */
 129   };
 130
 131 /* Returns negative if A < B, zero if A == B, positive if A > B. */
 132 typedef int ll_compare_func (const struct ll *a,
 133                              const struct ll *b, void *aux);
 134
 135 /* Returns true or false depending on properties of LL. */
 136 typedef bool ll_predicate_func (const struct ll *ll, void *aux);
 137
 138 /* Takes some action on LL. */
 139 typedef void ll_action_func (struct ll *ll, void *aux);
 140
 141 /* Suitable for use as the initializer for a `struct ll_list'
 142    named LIST.  Typical usage:
 143        struct ll_list list = LL_INITIALIZER (list);
 144    LL_INITIALIZER() is an alternative to ll_init(). */
 145 #define LL_INITIALIZER(LIST) { { &(LIST).null, &(LIST).null } }
 146
 147 /* Basics. */
 148 static inline void ll_init (struct ll_list *);
 149 static inline bool ll_is_empty (const struct ll_list *);
 150 size_t ll_count (const struct ll_list *);
 151
 152 /* Iteration. */
 153 static inline struct ll *ll_head (const struct ll_list *);
 154 static inline struct ll *ll_tail (const struct ll_list *);
 155 static inline struct ll *ll_null (const struct ll_list *);
 156 static inline struct ll *ll_next (const struct ll *);
 157 static inline struct ll *ll_prev (const struct ll *);
 158
 159 /* Stack- and queue-like behavior. */
 160 static inline void ll_push_head (struct ll_list *, struct ll *);
 161 static inline void ll_push_tail (struct ll_list *, struct ll *);
 162 static inline struct ll *ll_pop_head (struct ll_list *);
 163 static inline struct ll *ll_pop_tail (struct ll_list *);
 164
 165 /* Insertion. */
 166 static inline void ll_insert (struct ll *before, struct ll *new);
 167 void ll_splice (struct ll *before, struct ll *r0, struct ll *r1);
 168 void ll_swap (struct ll *a, struct ll *b);
 169 void ll_swap_range (struct ll *a0, struct ll *a1,
 170                     struct ll *b0, struct ll *b1);
 171
 172 /* Removal. */
 173 static inline struct ll *ll_remove (struct ll *);
 174 static inline void ll_remove_range (struct ll *r0, struct ll *r1);
 175 size_t ll_remove_equal (struct ll *r0, struct ll *r1, struct ll *target,
 176                         ll_compare_func *, void *aux);
 177 size_t ll_remove_if (struct ll *r0, struct ll *r1,
 178                      ll_predicate_func *, void *aux);
 179 static inline void ll_moved (struct ll *);
 180
 181 /* Non-mutating algorithms. */
 182 struct ll *ll_find_equal (const struct ll *r0, const struct ll *r1,
 183                           const struct ll *target,
 184                           ll_compare_func *, void *aux);
 185 struct ll *ll_find_if (const struct ll *r0, const struct ll *r1,
 186                        ll_predicate_func *, void *aux);
 187 struct ll *ll_find_adjacent_equal (const struct ll *r0, const struct ll *r1,
 188                                    ll_compare_func *, void *aux);
 189 size_t ll_count_range (const struct ll *r0, const struct ll *r1);
 190 size_t ll_count_equal (const struct ll *r0, const struct ll *r1,
 191                        const struct ll *target,
 192                        ll_compare_func *, void *aux);
 193 size_t ll_count_if (const struct ll *r0, const struct ll *r1,
 194                     ll_predicate_func *, void *aux);
 195 struct ll *ll_max (const struct ll *r0, const struct ll *r1,
 196                    ll_compare_func *, void *aux);
 197 struct ll *ll_min (const struct ll *r0, const struct ll *r1,
 198                    ll_compare_func *, void *aux);
 199 int ll_lexicographical_compare_3way (const struct ll *a0, const struct ll *a1,
 200                                      const struct ll *b0, const struct ll *b1,
 201                                      ll_compare_func *, void *aux);
 202
 203 /* Mutating algorithms. */
 204 void ll_apply (struct ll *r0, struct ll *r1, ll_action_func *, void *aux);
 205 void ll_reverse (struct ll *r0, struct ll *r1);
 206 bool ll_next_permutation (struct ll *r0, struct ll *r1,
 207                           ll_compare_func *, void *aux);
 208 bool ll_prev_permutation (struct ll *r0, struct ll *r1,
 209                           ll_compare_func *, void *aux);
 210
 211 /* Sorted list functions. */
 212 void ll_sort (struct ll *r0, struct ll *r1, ll_compare_func *, void *aux);
 213 struct ll *ll_find_run (const struct ll *r0, const struct ll *r1,
 214                         ll_compare_func *, void *aux);
 215 struct ll *ll_merge (struct ll *a0, struct ll *a1,
 216                      struct ll *b0, struct ll *b1,
 217                      ll_compare_func *, void *aux);
 218 bool ll_is_sorted (const struct ll *r0, const struct ll *r1,
 219                    ll_compare_func *, void *aux);
 220 size_t ll_unique (struct ll *r0, struct ll *r1, struct ll *dups,
 221                   ll_compare_func *, void *aux);
 222 void ll_sort_unique (struct ll *r0, struct ll *r1, struct ll *dups,
 223                      ll_compare_func *, void *aux);
 224 void ll_insert_ordered (struct ll *r0, struct ll *r1, struct ll *new_elem,
 225                         ll_compare_func *, void *aux);
 226 struct ll *ll_partition (struct ll *r0, struct ll *r1,
 227                          ll_predicate_func *, void *aux);
 228 struct ll *ll_find_partition (const struct ll *r0, const struct ll *r1,
 229                               ll_predicate_func *, void *aux);
 230 \f
 231 /* Iteration helper macros. */
 232
 233 /* Sets DATA to each object in LIST in turn, in forward or
 234    reverse order, assuming that each
 235    `struct ll' in LIST is embedded as the given MEMBER name in
 236    data type STRUCT.
 237
 238    Behavior is undefined if DATA is removed from the list between
 239    loop iterations. */
 240 #define ll_for_each(DATA, STRUCT, MEMBER, LIST)                 \
 241         for (DATA = ll_head__ (STRUCT, MEMBER, LIST);           \
 242              DATA != NULL;                                      \
 243              DATA = ll_next__ (DATA, STRUCT, MEMBER, LIST))
 244 #define ll_for_each_reverse(DATA, STRUCT, MEMBER, LIST)         \
 245         for (DATA = ll_tail__ (STRUCT, MEMBER, LIST);           \
 246              DATA != NULL;                                      \
 247              DATA = ll_prev__ (DATA, STRUCT, MEMBER, LIST))
 248
 249 /* Continues a iteration of LIST, starting from the object
 250    currently in DATA and continuing, in forward or reverse order,
 251    through the remainder of the list, assuming that each `struct
 252    ll' in LIST is embedded as the given MEMBER name in data type
 253    STRUCT.
 254
 255    Behavior is undefined if DATA is removed from the list between
 256    loop iterations. */
 257 #define ll_for_each_continue(DATA, STRUCT, MEMBER, LIST)        \
 258         for (;                                                  \
 259              DATA != NULL;                                      \
 260              DATA = ll_next__ (DATA, STRUCT, MEMBER, LIST))
 261 #define ll_for_each_reverse_continue(DATA, STRUCT, MEMBER, LIST)        \
 262         for (;                                                          \
 263              DATA != NULL;                                              \
 264              DATA = ll_prev__ (DATA, STRUCT, MEMBER, LIST))
 265
 266 /* Sets DATA to each object in LIST in turn, in forward or
 267    reverse order, assuming that each `struct ll' in LIST is
 268    embedded as the given MEMBER name in data type STRUCT.  NEXT
 269    (or PREV) must be another variable of the same type as DATA.
 270
 271    Behavior is well-defined even if DATA is removed from the list
 272    between iterations. */
 273 #define ll_for_each_safe(DATA, NEXT, STRUCT, MEMBER, LIST)              \
 274         for (DATA = ll_head__ (STRUCT, MEMBER, LIST);                   \
 275              (DATA != NULL                                              \
 276               ? (NEXT = ll_next__ (DATA, STRUCT, MEMBER, LIST), 1)      \
 277               : 0);                                                     \
 278              DATA = NEXT)
 279 #define ll_for_each_reverse_safe(DATA, PREV, STRUCT, MEMBER, LIST)      \
 280         for (DATA = ll_tail__ (STRUCT, MEMBER, LIST);                   \
 281              (DATA != NULL                                              \
 282               ? (PREV = ll_prev__ (DATA, STRUCT, MEMBER, LIST), 1)      \
 283               : 0);                                                     \
 284              DATA = PREV)
 285
 286 /* Continues a iteration of LIST, in forward or reverse order,
 287    starting from the object currently in DATA and continuing
 288    forward through the remainder of the list, assuming that each
 289    `struct ll' in LIST is embedded as the given MEMBER name in
 290    data type STRUCT.  NEXT (or PREV) must be another variable of
 291    the same type as DATA.
 292
 293    Behavior is well-defined even if DATA is removed from the list
 294    between iterations. */
 295 #define ll_for_each_safe_continue(DATA, NEXT, STRUCT, MEMBER, LIST)     \
 296         for (;                                                          \
 297              (DATA != NULL                                              \
 298               ? (NEXT = ll_next__ (DATA, STRUCT, MEMBER, LIST), 1)      \
 299               : 0);                                                     \
 300              DATA = NEXT)
 301 #define ll_for_each_safe_reverse_continue(DATA, PREV, STRUCT, MEMBER, LIST) \
 302         for (;                                                          \
 303              (DATA != NULL                                              \
 304               ? (PREV = ll_prev__ (DATA, STRUCT, MEMBER, LIST), 1)      \
 305               : 0);                                                     \
 306              DATA = PREV)
 307
 308 /* Sets DATA to each object in LIST in turn, in forward or
 309    reverse order, assuming that each `struct ll' in LIST is
 310    embedded as the given MEMBER name in data type STRUCT.
 311    Each object is removed from LIST before its loop iteration. */
 312 #define ll_for_each_preremove(DATA, STRUCT, MEMBER, LIST)                 \
 313         while (!ll_is_empty (LIST)                                        \
 314                ? (DATA = ll_data (ll_pop_head (LIST), STRUCT, MEMBER), 1) \
 315                : 0)
 316 #define ll_for_each_reverse_preremove(DATA, STRUCT, MEMBER, LIST)         \
 317         while (!ll_is_empty (LIST)                                        \
 318                ? (DATA = ll_data (ll_pop_tail (LIST), STRUCT, MEMBER), 1) \
 319                : 0)
 320
 321 /* Sets DATA to each object in LIST in turn, in forward or
 322    reverse order, assuming that each `struct ll' in LIST is
 323    embedded as the given MEMBER name in data type STRUCT.
 324    At the end of each loop iteration, DATA is removed from the
 325    list. */
 326 #define ll_for_each_postremove(DATA, STRUCT, MEMBER, LIST)      \
 327         for (;                                                  \
 328              (DATA = ll_head__ (STRUCT, MEMBER, LIST)) != NULL; \
 329              ll_remove (&DATA->MEMBER))
 330 #define ll_for_each_reverse_postremove(DATA, STRUCT, MEMBER, LIST)      \
 331         for (;                                                          \
 332              (DATA = ll_tail__ (STRUCT, MEMBER, LIST)) != NULL;         \
 333              ll_remove (&DATA->MEMBER))
 334
 335 /* Macros for internal use only. */
 336 #define ll_data__(LL, STRUCT, MEMBER, LIST)                             \
 337         ((LL) != ll_null (LIST) ? ll_data (LL, STRUCT, MEMBER) : NULL)
 338 #define ll_head__(STRUCT, MEMBER, LIST)                         \
 339         ll_data__ (ll_head (LIST), STRUCT, MEMBER, LIST)
 340 #define ll_tail__(STRUCT, MEMBER, LIST)                         \
 341         ll_data__ (ll_tail (LIST), STRUCT, MEMBER, LIST)
 342 #define ll_next__(DATA, STRUCT, MEMBER, LIST)                           \
 343         ll_data__ (ll_next (&(DATA)->MEMBER), STRUCT, MEMBER, LIST)
 344 #define ll_prev__(DATA, STRUCT, MEMBER, LIST)                           \
 345         ll_data__ (ll_prev (&(DATA)->MEMBER), STRUCT, MEMBER, LIST)
 346 \f
 347 /* Inline functions. */
 348
 349 /* Initializes LIST as an empty list. */
 350 static inline void
 351 ll_init (struct ll_list *list)
 352 {
 353   list->null.next = list->null.prev = &list->null;
 354 }
 355
 356 /* Returns true if LIST is empty (contains just the null node),
 357    false if LIST is not empty (has at least one other node).
 358    Executes in O(1) time. */
 359 static inline bool
 360 ll_is_empty (const struct ll_list *list)
 361 {
 362   return ll_head (list) == ll_null (list);
 363 }
 364
 365 /* Returns the first node in LIST,
 366    or the null node if LIST is empty. */
 367 static inline struct ll *
 368 ll_head (const struct ll_list *list)
 369 {
 370   return ll_next (ll_null (list));
 371 }
 372
 373 /* Returns the last node in LIST,
 374    or the null node if LIST is empty. */
 375 static inline struct ll *
 376 ll_tail (const struct ll_list *list)
 377 {
 378   return ll_prev (ll_null (list));
 379 }
 380
 381 /* Returns LIST's null node. */
 382 static inline struct ll *
 383 ll_null (const struct ll_list *list)
 384 {
 385   return CONST_CAST (struct ll *, &list->null);
 386 }
 387
 388 /* Returns the node following LL in its list,
 389    or the null node if LL is at the end of its list.
 390    (In an empty list, the null node follows itself.) */
 391 static inline struct ll *
 392 ll_next (const struct ll *ll)
 393 {
 394   return ll->next;
 395 }
 396
 397 /* Returns the node preceding LL in its list,
 398    or the null node if LL is the first node in its list.
 399    (In an empty list, the null node precedes itself.) */
 400 static inline struct ll *
 401 ll_prev (const struct ll *ll)
 402 {
 403   return ll->prev;
 404 }
 405
 406 /* Inserts LL at the head of LIST. */
 407 static inline void
 408 ll_push_head (struct ll_list *list, struct ll *ll)
 409 {
 410   ll_insert (ll_head (list), ll);
 411 }
 412
 413 /* Inserts LL at the tail of LIST. */
 414 static inline void
 415 ll_push_tail (struct ll_list *list, struct ll *ll)
 416 {
 417   ll_insert (ll_null (list), ll);
 418 }
 419
 420 /* Removes and returns the first node in LIST,
 421    which must not be empty. */
 422 static inline struct ll *
 423 ll_pop_head (struct ll_list *list)
 424 {
 425   struct ll *head;
 426   assert (!ll_is_empty (list));
 427   head = ll_head (list);
 428   ll_remove (head);
 429   return head;
 430 }
 431
 432 /* Removes and returns the last node in LIST,
 433    which must not be empty. */
 434 static inline struct ll *
 435 ll_pop_tail (struct ll_list *list)
 436 {
 437   struct ll *tail;
 438   assert (!ll_is_empty (list));
 439   tail = ll_tail (list);
 440   ll_remove (tail);
 441   return tail;
 442 }
 443
 444 /* Inserts NEW_ELEM just before BEFORE.
 445    (NEW_ELEM must not already be in a list.) */
 446 static inline void
 447 ll_insert (struct ll *before, struct ll *new_elem)
 448 {
 449   struct ll *before_prev = ll_prev (before);
 450   new_elem->next = before;
 451   new_elem->prev = before_prev;
 452   before_prev->next = before->prev = new_elem;
 453 }
 454
 455 /* Removes LL from its list
 456    and returns the node that formerly followed it. */
 457 static inline struct ll *
 458 ll_remove (struct ll *ll)
 459 {
 460   struct ll *next = ll_next (ll);
 461   ll->prev->next = next;
 462   ll->next->prev = ll->prev;
 463   return next;
 464 }
 465
 466 /* Removes R0...R1 from their list. */
 467 static inline void
 468 ll_remove_range (struct ll *r0, struct ll *r1)
 469 {
 470   if (r0 != r1)
 471     {
 472       r1 = r1->prev;
 473       r0->prev->next = r1->next;
 474       r1->next->prev = r0->prev;
 475     }
 476 }
 477
 478 /* Adjusts the nodes around LL to compensate for LL having
 479    changed address, e.g. due to LL being inside a block of memory
 480    that was realloc()'d.  Equivalent to calling ll_remove()
 481    before moving LL, then ll_insert() afterward, but more
 482    efficient. */
 483 static inline void
 484 ll_moved (struct ll *ll)
 485 {
 486   ll->prev->next = ll->next->prev = ll;
 487 }
 488
 489 #endif /* ll.h */