src/libpspp/ll.h

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