src/libpspp/ll.h

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