src/libpspp/llx.h

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