pintos-os.org Git - pspp/blob - 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 /* Memory manager. */
 114 struct llx_manager
 115   {
 116     /* Allocates and returns memory for a new struct llx.
 117        If space is unavailable, returns a null pointer. */
 118     struct llx *(*allocate) (void *aux);
 119
 120     /* Releases a previously allocated struct llx. */
 121     void (*release) (struct llx *, void *aux);
 122
 123     /* Auxiliary data passed to allocate and release
 124        functions. */
 125     void *aux;
 126   };
 127
 128 /* Manager that uses the standard malloc and free routines. */
 129 extern const struct llx_manager llx_malloc_mgr;
 130
 131 /* Returns negative if A < B, zero if A == B, positive if A > B. */
 132 typedef int llx_compare_func (const void *a, const void *b, void *aux);
 133
 134 /* Returns true or false depending on properties of DATA. */
 135 typedef bool llx_predicate_func (const void *data, void *aux);
 136
 137 /* Takes some action on DATA. */
 138 typedef void llx_action_func (void *data, void *aux);
 139
 140 /* Basics. */
 141 static inline void llx_init (struct llx_list *);
 142 void llx_destroy (struct llx_list *, llx_action_func *destructor, void *aux,
 143                   const struct llx_manager *manager);
 144 static inline bool llx_is_empty (const struct llx_list *);
 145 size_t llx_count (const struct llx_list *);
 146
 147 /* Iteration. */
 148 static inline struct llx *llx_head (const struct llx_list *);
 149 static inline struct llx *llx_tail (const struct llx_list *);
 150 static inline struct llx *llx_null (const struct llx_list *);
 151 static inline struct llx *llx_next (const struct llx *);
 152 static inline struct llx *llx_prev (const struct llx *);
 153 static inline void *llx_data (const struct llx *);
 154
 155 /* Stack- and queue-like behavior. */
 156 struct llx *llx_push_head (struct llx_list *, void *,
 157                            const struct llx_manager *);
 158 struct llx *llx_push_tail (struct llx_list *, void *,
 159                            const struct llx_manager *);
 160 void *llx_pop_head (struct llx_list *, const struct llx_manager *);
 161 void *llx_pop_tail (struct llx_list *, const struct llx_manager *);
 162
 163 /* Insertion. */
 164 struct llx *llx_insert (struct llx *before, void *,
 165                         const struct llx_manager *);
 166 void llx_splice (struct llx *before, struct llx *r0, struct llx *r1);
 167 void llx_swap (struct llx *a, struct llx *b);
 168 void llx_swap_range (struct llx *a0, struct llx *a1,
 169                      struct llx *b0, struct llx *b1);
 170
 171 /* Removal. */
 172 struct llx *llx_remove (struct llx *, const struct llx_manager *);
 173 void llx_remove_range (struct llx *r0, struct llx *r1,
 174                        const struct llx_manager *);
 175 size_t llx_remove_equal (struct llx *r0, struct llx *r1, const void *target,
 176                          llx_compare_func *, void *aux,
 177                          const struct llx_manager *);
 178 size_t llx_remove_if (struct llx *r0, struct llx *r1,
 179                       llx_predicate_func *, void *aux,
 180                       const struct llx_manager *);
 181
 182 /* Non-mutating algorithms. */
 183 struct llx *llx_find_equal (const struct llx *r0, const struct llx *r1,
 184                             const void *target,
 185                             llx_compare_func *, void *aux);
 186 struct llx *llx_find_if (const struct llx *r0, const struct llx *r1,
 187                          llx_predicate_func *, void *aux);
 188 struct llx *llx_find_adjacent_equal (const struct llx *r0,
 189                                      const struct llx *r1,
 190                                      llx_compare_func *, void *aux);
 191 size_t llx_count_range (const struct llx *r0, const struct llx *r1);
 192 size_t llx_count_equal (const struct llx *r0, const struct llx *r1,
 193                         const void *target,
 194                         llx_compare_func *, void *aux);
 195 size_t llx_count_if (const struct llx *r0, const struct llx *r1,
 196                      llx_predicate_func *, void *aux);
 197 struct llx *llx_max (const struct llx *r0, const struct llx *r1,
 198                      llx_compare_func *, void *aux);
 199 struct llx *llx_min (const struct llx *r0, const struct llx *r1,
 200                      llx_compare_func *, void *aux);
 201 int llx_lexicographical_compare_3way (const struct llx *a0,
 202                                       const struct llx *a1,
 203                                       const struct llx *b0,
 204                                       const struct llx *b1,
 205                                       llx_compare_func *, void *aux);
 206
 207 /* Mutating algorithms. */
 208 void llx_apply (struct llx *r0, struct llx *r1, llx_action_func *, void *aux);
 209 void llx_reverse (struct llx *r0, struct llx *r1);
 210 bool llx_next_permutation (struct llx *r0, struct llx *r1,
 211                            llx_compare_func *, void *aux);
 212 bool llx_prev_permutation (struct llx *r0, struct llx *r1,
 213                            llx_compare_func *, void *aux);
 214
 215 /* Sorted list functions. */
 216 void llx_sort (struct llx *r0, struct llx *r1, llx_compare_func *, void *aux);
 217 struct llx *llx_find_run (const struct llx *r0, const struct llx *r1,
 218                           llx_compare_func *, void *aux);
 219 bool llx_is_sorted (const struct llx *r0, const struct llx *r1,
 220                     llx_compare_func *, void *aux);
 221 struct llx *llx_merge (struct llx *a0, struct llx *a1,
 222                        struct llx *b0, struct llx *b1,
 223                        llx_compare_func *, void *aux);
 224 size_t llx_unique (struct llx *r0, struct llx *r1, struct llx *dups,
 225                    llx_compare_func *, void *aux,
 226                    const struct llx_manager *);
 227 void llx_sort_unique (struct llx *r0, struct llx *r1, struct llx *dups,
 228                       llx_compare_func *, void *aux,
 229                       const struct llx_manager *);
 230 struct llx *llx_insert_ordered (struct llx *r0, struct llx *r1, void *data,
 231                                 llx_compare_func *, void *aux,
 232                                 const struct llx_manager *);
 233 struct llx *llx_partition (struct llx *r0, struct llx *r1,
 234                            llx_predicate_func *, void *aux);
 235 struct llx *llx_find_partition (const struct llx *r0, const struct llx *r1,
 236                                 llx_predicate_func *, void *aux);
 237
 238 /* Returns the llx within which LL is embedded. */
 239 static struct llx *
 240 llx_from_ll (struct ll *ll)
 241 {
 242   return ll_data (ll, struct llx, ll);
 243 }
 244
 245 /* Initializes LIST as an empty list. */
 246 static inline void
 247 llx_init (struct llx_list *list)
 248 {
 249   ll_init (&list->ll_list);
 250 }
 251
 252 /* Returns true if LIST is empty (contains just the null node),
 253    false if LIST is not empty (has at least one other node).
 254    Executes in O(1) time. */
 255 static inline bool
 256 llx_is_empty (const struct llx_list *list)
 257 {
 258   return ll_is_empty (&list->ll_list);
 259 }
 260
 261 /* Returns the first node in LIST,
 262    or the null node if LIST is empty. */
 263 static inline struct llx *
 264 llx_head (const struct llx_list *list)
 265 {
 266   return llx_from_ll (ll_head (&list->ll_list));
 267 }
 268
 269 /* Returns the last node in LIST,
 270    or the null node if LIST is empty. */
 271 static inline struct llx *
 272 llx_tail (const struct llx_list *list)
 273 {
 274   return llx_from_ll (ll_tail (&list->ll_list));
 275 }
 276
 277 /* Returns LIST's null node. */
 278 static inline struct llx *
 279 llx_null (const struct llx_list *list)
 280 {
 281   return llx_from_ll (ll_null (&list->ll_list));
 282 }
 283
 284 /* Returns the node following LLX in its list,
 285    or the null node if LLX is at the end of its list.
 286    (In an empty list, the null node follows itself.) */
 287 static inline struct llx *
 288 llx_next (const struct llx *llx)
 289 {
 290   return llx_from_ll (ll_next (&llx->ll));
 291 }
 292
 293 /* Returns the node preceding LLX in its list,
 294    or the null node if LLX is the first node in its list.
 295    (In an empty list, the null node precedes itself.) */
 296 static inline struct llx *
 297 llx_prev (const struct llx *llx)
 298 {
 299   return llx_from_ll (ll_prev (&llx->ll));
 300 }
 301
 302 /* Returns the data in node LLX. */
 303 static inline void *
 304 llx_data (const struct llx *llx)
 305 {
 306   return llx->data;
 307 }
 308
 309 #endif /* llx.h */