Replace safe_strcmp with g_strcmp0.
[pspp-builds.git] / src / libpspp / tower.h
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2007 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 /* "Tower" data structure, implemented as an augmented binary
18    tree.
19
20    Imagine a tall stack of books on a table; actually, call it a
21    "tower" of books because "stack" is already taken.  If you're
22    careful enough and strong enough, you can pull individual
23    books out of the stack, as well as insert new books between
24    existing ones or at the bottom or top of the stack.
25
26    At any given time, you can refer to a book in the tower by
27    measuring the book's height above the tower in some unit,
28    e.g. mm.  This isn't necessarily equivalent to the number of
29    books in the tower below the book in question, like an array
30    index, because the books in the stack aren't necessarily all
31    the same thickness: some might be as thin as K&R and others as
32    thick as _Introduction to Algorithms_.
33
34    This is the analogy behind this data structure.  Each node in
35    the data structure has a "thickness", which is actually called
36    the node's "size" because "thickness" is just too awkward a
37    name.  The primary way to look up nodes is by a height from
38    the bottom of the tower; any height within a node retrieves
39    that node, not just the distance to the bottom of the node.
40    You can insert a new node between any two existing nodes, or
41    at either end, which shifts up the height of all the nodes
42    above it.  You can also delete any node, which shifts down the
43    height of all the nodes above it.
44
45    The tower data structure also implements efficient access to
46    nodes by index, i.e. by 0-based count of nodes from the bottom
47    of the tower. */
48
49 #ifndef LIBPSPP_TOWER_H
50 #define LIBPSPP_TOWER_H
51
52 #include <stdbool.h>
53 #include <libpspp/abt.h>
54
55 /* Returns the data structure corresponding to the given NODE,
56    assuming that NODE is embedded as the given MEMBER name in
57    data type STRUCT. */
58 #define tower_data(NODE, STRUCT, MEMBER)                            \
59         ((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
60
61 /* A node within a tower. */
62 struct tower_node
63   {
64     struct abt_node abt_node;         /* ABT node. */
65     unsigned long int subtree_size;   /* Node size plus descendants' sizes. */
66     unsigned long int size;           /* Size. */
67     unsigned long int subtree_count;  /* Number of descendants, plus 1. */
68   };
69
70 /* Returns the size of a tower node. */
71 static inline unsigned long
72 tower_node_get_size (const struct tower_node *node)
73 {
74   return node->size;
75 }
76
77 unsigned long int tower_node_get_level (const struct tower_node *);
78 unsigned long int tower_node_get_index (const struct tower_node *);
79
80 /* A tower. */
81 struct tower
82   {
83     struct abt abt;                   /* Tree. */
84     struct tower_node *cache;         /* Cache node. */
85     unsigned long int cache_bottom;   /* Height of cache's bottom. */
86   };
87
88 void tower_init (struct tower *);
89
90 bool tower_is_empty (const struct tower *);
91 unsigned long int tower_count (const struct tower *);
92 unsigned long int tower_height (const struct tower *);
93
94 void tower_insert (struct tower *, unsigned long int size,
95                    struct tower_node *new, struct tower_node *under);
96 struct tower_node *tower_delete (struct tower *, struct tower_node *);
97 void tower_resize (struct tower *, struct tower_node *,
98                    unsigned long int new_size);
99 void tower_splice (struct tower *dst, struct tower_node *under,
100                    struct tower *src,
101                    struct tower_node *first, struct tower_node *last);
102
103 struct tower_node *tower_lookup (const struct tower *,
104                                  unsigned long int level,
105                                  unsigned long int *node_start);
106 struct tower_node *tower_get (const struct tower *, unsigned long int index);
107 struct tower_node *tower_first (const struct tower *);
108 struct tower_node *tower_last (const struct tower *);
109 struct tower_node *tower_next (const struct tower *,
110                                const struct tower_node *);
111 struct tower_node *tower_prev (const struct tower *,
112                                const struct tower_node *);
113
114 #endif /* libpspp/tower.h */