src/libpspp/llx.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 (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_equal (const struct llx *r0, const struct llx *r1,
 190                             const void *target,
 191                             llx_compare_func *, void *aux);
 192 struct llx *llx_find_if (const struct llx *r0, const struct llx *r1,
 193                          llx_predicate_func *, void *aux);
 194 struct llx *llx_find_adjacent_equal (const struct llx *r0,
 195                                      const struct llx *r1,
 196                                      llx_compare_func *, void *aux);
 197 size_t llx_count_range (const struct llx *r0, const struct llx *r1);
 198 size_t llx_count_equal (const struct llx *r0, const struct llx *r1,
 199                         const void *target,
 200                         llx_compare_func *, void *aux);
 201 size_t llx_count_if (const struct llx *r0, const struct llx *r1,
 202                      llx_predicate_func *, void *aux);
 203 struct llx *llx_max (const struct llx *r0, const struct llx *r1,
 204                      llx_compare_func *, void *aux);
 205 struct llx *llx_min (const struct llx *r0, const struct llx *r1,
 206                      llx_compare_func *, void *aux);
 207 int llx_lexicographical_compare_3way (const struct llx *a0,
 208                                       const struct llx *a1,
 209                                       const struct llx *b0,
 210                                       const struct llx *b1,
 211                                       llx_compare_func *, void *aux);
 212
 213 /* Mutating algorithms. */
 214 void llx_apply (struct llx *r0, struct llx *r1, llx_action_func *, void *aux);
 215 void llx_reverse (struct llx *r0, struct llx *r1);
 216 bool llx_next_permutation (struct llx *r0, struct llx *r1,
 217                            llx_compare_func *, void *aux);
 218 bool llx_prev_permutation (struct llx *r0, struct llx *r1,
 219                            llx_compare_func *, void *aux);
 220
 221 /* Sorted list functions. */
 222 void llx_sort (struct llx *r0, struct llx *r1, llx_compare_func *, void *aux);
 223 struct llx *llx_find_run (const struct llx *r0, const struct llx *r1,
 224                           llx_compare_func *, void *aux);
 225 bool llx_is_sorted (const struct llx *r0, const struct llx *r1,
 226                     llx_compare_func *, void *aux);
 227 struct llx *llx_merge (struct llx *a0, struct llx *a1,
 228                        struct llx *b0, struct llx *b1,
 229                        llx_compare_func *, void *aux);
 230 size_t llx_unique (struct llx *r0, struct llx *r1, struct llx *dups,
 231                    llx_compare_func *, void *aux,
 232                    const struct llx_manager *);
 233 void llx_sort_unique (struct llx *r0, struct llx *r1, struct llx *dups,
 234                       llx_compare_func *, void *aux,
 235                       const struct llx_manager *);
 236 struct llx *llx_insert_ordered (struct llx *r0, struct llx *r1, void *data,
 237                                 llx_compare_func *, void *aux,
 238                                 const struct llx_manager *);
 239 struct llx *llx_partition (struct llx *r0, struct llx *r1,
 240                            llx_predicate_func *, void *aux);
 241 struct llx *llx_find_partition (const struct llx *r0, const struct llx *r1,
 242                                 llx_predicate_func *, void *aux);
 243
 244 /* Returns the llx within which LL is embedded. */
 245 static struct llx *
 246 llx_from_ll (struct ll *ll)
 247 {
 248   return ll_data (ll, struct llx, ll);
 249 }
 250
 251 /* Initializes LIST as an empty list. */
 252 static inline void
 253 llx_init (struct llx_list *list)
 254 {
 255   ll_init (&list->ll_list);
 256 }
 257
 258 /* Returns true if LIST is empty (contains just the null node),
 259    false if LIST is not empty (has at least one other node).
 260    Executes in O(1) time. */
 261 static inline bool
 262 llx_is_empty (const struct llx_list *list)
 263 {
 264   return ll_is_empty (&list->ll_list);
 265 }
 266
 267 /* Returns the first node in LIST,
 268    or the null node if LIST is empty. */
 269 static inline struct llx *
 270 llx_head (const struct llx_list *list)
 271 {
 272   return llx_from_ll (ll_head (&list->ll_list));
 273 }
 274
 275 /* Returns the last node in LIST,
 276    or the null node if LIST is empty. */
 277 static inline struct llx *
 278 llx_tail (const struct llx_list *list)
 279 {
 280   return llx_from_ll (ll_tail (&list->ll_list));
 281 }
 282
 283 /* Returns LIST's null node. */
 284 static inline struct llx *
 285 llx_null (const struct llx_list *list)
 286 {
 287   return llx_from_ll (ll_null (&list->ll_list));
 288 }
 289
 290 /* Returns the node following LLX in its list,
 291    or the null node if LLX is at the end of its list.
 292    (In an empty list, the null node follows itself.) */
 293 static inline struct llx *
 294 llx_next (const struct llx *llx)
 295 {
 296   return llx_from_ll (ll_next (&llx->ll));
 297 }
 298
 299 /* Returns the node preceding LLX in its list,
 300    or the null node if LLX is the first node in its list.
 301    (In an empty list, the null node precedes itself.) */
 302 static inline struct llx *
 303 llx_prev (const struct llx *llx)
 304 {
 305   return llx_from_ll (ll_prev (&llx->ll));
 306 }
 307
 308 /* Returns the data in node LLX. */
 309 static inline void *
 310 llx_data (const struct llx *llx)
 311 {
 312   return llx->data;
 313 }
 314
 315 #endif /* llx.h */