src/libpspp/llx.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 (llx.h) supplies "external" circular doubly linked
  23    lists.  Its companion header (ll.h) supplies "embedded"
  24    circular doubly linked lists.  The two variants are described
  25    briefly here.  The external 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 LLX_H
  51 #define LLX_H 1
  52
  53 #include <stdbool.h>
  54 #include <stddef.h>
  55 #include <libpspp/ll.h>
  56
  57 /* External, 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 external linked list is represented as `struct llx_list'.
  65    Each node in the list consists of a `struct llx' that contains
  66    a `void *' pointer to the node's data.  Use the llx_data()
  67    function to extract the data pointer from a node.
  68
  69    Many list functions take ranges of nodes as arguments.  Ranges
  70    are "half-open"; that is, R0...R1 includes R0 but not R1.  A
  71    range whose endpoints are the same (e.g. R0...R0) contains no
  72    nodes at all.
  73
  74    Consider the following declarations:
  75
  76      struct llx_list list;
  77
  78      struct foo
  79        {
  80          int x;                   // Data member.
  81        };
  82
  83    Here's an example of iteration from head to tail:
  84
  85      struct llx *llx;
  86      for (llx = llx_head (&list); llx != llx_null (&list);
  87           llx = llx_next (llx))
  88        {
  89          struct foo *foo = llx_data (llx);
  90          ...do something with foo->x...
  91        }
  92
  93    Here's another way to do it:
  94
  95      struct llx *llx = llx_null (&list);
  96      while ((llx = llx_next (llx)) != llx_null (&list))
  97        {
  98          struct foo *foo = llx_data (llx);
  99          ...do something with foo->x...
 100        }
 101 */
 102
 103 /* External linked list node. */
 104 struct llx
 105   {
 106     struct ll ll;               /* Node. */
 107     void *data;                 /* Member data. */
 108   };
 109
 110 /* Linked list. */
 111 struct llx_list
 112   {
 113     struct ll_list ll_list;     /* The list. */
 114   };
 115
 116 /* Memory manager. */
 117 struct llx_manager
 118   {
 119     /* Allocates and returns memory for a new struct llx.
 120        If space is unavailable, returns a null pointer. */
 121     struct llx *(*allocate) (void *aux);
 122
 123     /* Releases a previously allocated struct llx. */
 124     void (*release) (struct llx *, void *aux);
 125
 126     /* Auxiliary data passed to allocate and release
 127        functions. */
 128     void *aux;
 129   };
 130
 131 /* Manager that uses the standard malloc and free routines. */
 132 extern const struct llx_manager llx_malloc_mgr;
 133
 134 /* Returns negative if A < B, zero if A == B, positive if A > B. */
 135 typedef int llx_compare_func (const void *a, const void *b, void *aux);
 136
 137 /* Returns true or false depending on properties of DATA. */
 138 typedef bool llx_predicate_func (const void *data, void *aux);
 139
 140 /* Takes some action on DATA. */
 141 typedef void llx_action_func (void *data, void *aux);
 142
 143 /* Basics. */
 144 static inline void llx_init (struct llx_list *);
 145 void llx_destroy (struct llx_list *, llx_action_func *destructor, void *aux,
 146                   const struct llx_manager *manager);
 147 static inline bool llx_is_empty (const struct llx_list *);
 148 size_t llx_count (const struct llx_list *);
 149
 150 /* Iteration. */
 151 static inline struct llx *llx_head (const struct llx_list *);
 152 static inline struct llx *llx_tail (const struct llx_list *);
 153 static inline struct llx *llx_null (const struct llx_list *);
 154 static inline struct llx *llx_next (const struct llx *);
 155 static inline struct llx *llx_prev (const struct llx *);
 156 static inline void *llx_data (const struct llx *);
 157
 158 /* Stack- and queue-like behavior. */
 159 struct llx *llx_push_head (struct llx_list *, void *,
 160                            const struct llx_manager *);
 161 struct llx *llx_push_tail (struct llx_list *, void *,
 162                            const struct llx_manager *);
 163 void *llx_pop_head (struct llx_list *, const struct llx_manager *);
 164 void *llx_pop_tail (struct llx_list *, const struct llx_manager *);
 165
 166 /* Insertion. */
 167 struct llx *llx_insert (struct llx *before, void *,
 168                         const struct llx_manager *);
 169 void llx_splice (struct llx *before, struct llx *r0, struct llx *r1);
 170 void llx_swap (struct llx *a, struct llx *b);
 171 void llx_swap_range (struct llx *a0, struct llx *a1,
 172                      struct llx *b0, struct llx *b1);
 173
 174 /* Removal. */
 175 struct llx *llx_remove (struct llx *, const struct llx_manager *);
 176 void llx_remove_range (struct llx *r0, struct llx *r1,
 177                        const struct llx_manager *);
 178 size_t llx_remove_equal (struct llx *r0, struct llx *r1, const void *target,
 179                          llx_compare_func *, void *aux,
 180                          const struct llx_manager *);
 181 size_t llx_remove_if (struct llx *r0, struct llx *r1,
 182                       llx_predicate_func *, void *aux,
 183                       const struct llx_manager *);
 184
 185 /* Non-mutating algorithms. */
 186 struct llx *llx_find_equal (const struct llx *r0, const struct llx *r1,
 187                             const void *target,
 188                             llx_compare_func *, void *aux);
 189 struct llx *llx_find_if (const struct llx *r0, const struct llx *r1,
 190                          llx_predicate_func *, void *aux);
 191 struct llx *llx_find_adjacent_equal (const struct llx *r0,
 192                                      const struct llx *r1,
 193                                      llx_compare_func *, void *aux);
 194 size_t llx_count_range (const struct llx *r0, const struct llx *r1);
 195 size_t llx_count_equal (const struct llx *r0, const struct llx *r1,
 196                         const void *target,
 197                         llx_compare_func *, void *aux);
 198 size_t llx_count_if (const struct llx *r0, const struct llx *r1,
 199                      llx_predicate_func *, void *aux);
 200 struct llx *llx_max (const struct llx *r0, const struct llx *r1,
 201                      llx_compare_func *, void *aux);
 202 struct llx *llx_min (const struct llx *r0, const struct llx *r1,
 203                      llx_compare_func *, void *aux);
 204 int llx_lexicographical_compare_3way (const struct llx *a0,
 205                                       const struct llx *a1,
 206                                       const struct llx *b0,
 207                                       const struct llx *b1,
 208                                       llx_compare_func *, void *aux);
 209
 210 /* Mutating algorithms. */
 211 void llx_apply (struct llx *r0, struct llx *r1, llx_action_func *, void *aux);
 212 void llx_reverse (struct llx *r0, struct llx *r1);
 213 bool llx_next_permutation (struct llx *r0, struct llx *r1,
 214                            llx_compare_func *, void *aux);
 215 bool llx_prev_permutation (struct llx *r0, struct llx *r1,
 216                            llx_compare_func *, void *aux);
 217
 218 /* Sorted list functions. */
 219 void llx_sort (struct llx *r0, struct llx *r1, llx_compare_func *, void *aux);
 220 struct llx *llx_find_run (const struct llx *r0, const struct llx *r1,
 221                           llx_compare_func *, void *aux);
 222 bool llx_is_sorted (const struct llx *r0, const struct llx *r1,
 223                     llx_compare_func *, void *aux);
 224 struct llx *llx_merge (struct llx *a0, struct llx *a1,
 225                        struct llx *b0, struct llx *b1,
 226                        llx_compare_func *, void *aux);
 227 size_t llx_unique (struct llx *r0, struct llx *r1, struct llx *dups,
 228                    llx_compare_func *, void *aux,
 229                    const struct llx_manager *);
 230 void llx_sort_unique (struct llx *r0, struct llx *r1, struct llx *dups,
 231                       llx_compare_func *, void *aux,
 232                       const struct llx_manager *);
 233 struct llx *llx_insert_ordered (struct llx *r0, struct llx *r1, void *data,
 234                                 llx_compare_func *, void *aux,
 235                                 const struct llx_manager *);
 236 struct llx *llx_partition (struct llx *r0, struct llx *r1,
 237                            llx_predicate_func *, void *aux);
 238 struct llx *llx_find_partition (const struct llx *r0, const struct llx *r1,
 239                                 llx_predicate_func *, void *aux);
 240
 241 /* Returns the llx within which LL is embedded. */
 242 static struct llx *
 243 llx_from_ll (struct ll *ll)
 244 {
 245   return ll_data (ll, struct llx, ll);
 246 }
 247
 248 /* Initializes LIST as an empty list. */
 249 static inline void
 250 llx_init (struct llx_list *list)
 251 {
 252   ll_init (&list->ll_list);
 253 }
 254
 255 /* Returns true if LIST is empty (contains just the null node),
 256    false if LIST is not empty (has at least one other node).
 257    Executes in O(1) time. */
 258 static inline bool
 259 llx_is_empty (const struct llx_list *list)
 260 {
 261   return ll_is_empty (&list->ll_list);
 262 }
 263
 264 /* Returns the first node in LIST,
 265    or the null node if LIST is empty. */
 266 static inline struct llx *
 267 llx_head (const struct llx_list *list)
 268 {
 269   return llx_from_ll (ll_head (&list->ll_list));
 270 }
 271
 272 /* Returns the last node in LIST,
 273    or the null node if LIST is empty. */
 274 static inline struct llx *
 275 llx_tail (const struct llx_list *list)
 276 {
 277   return llx_from_ll (ll_tail (&list->ll_list));
 278 }
 279
 280 /* Returns LIST's null node. */
 281 static inline struct llx *
 282 llx_null (const struct llx_list *list)
 283 {
 284   return llx_from_ll (ll_null (&list->ll_list));
 285 }
 286
 287 /* Returns the node following LLX in its list,
 288    or the null node if LLX is at the end of its list.
 289    (In an empty list, the null node follows itself.) */
 290 static inline struct llx *
 291 llx_next (const struct llx *llx)
 292 {
 293   return llx_from_ll (ll_next (&llx->ll));
 294 }
 295
 296 /* Returns the node preceding LLX in its list,
 297    or the null node if LLX is the first node in its list.
 298    (In an empty list, the null node precedes itself.) */
 299 static inline struct llx *
 300 llx_prev (const struct llx *llx)
 301 {
 302   return llx_from_ll (ll_prev (&llx->ll));
 303 }
 304
 305 /* Returns the data in node LLX. */
 306 static inline void *
 307 llx_data (const struct llx *llx)
 308 {
 309   return llx->data;
 310 }
 311
 312 #endif /* llx.h */