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