src/libpspp/ll.h

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