New Slovenian localisation from http://translationproject.org
[pspp] / src / libpspp / range-tower.h
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2007, 2009, 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 /* Bitmap, implemented as an augmented binary tree.
18
19    Beyond the usual features of a bitmap, a range tower can efficiently
20    implement a "splice" operation that shifts ranges of bits left or right.
21    This feature does cost memory and time, so use a range tower only if this
22    feature is actually needed.  Otherwise, use a range set (see range-set.h),
23    which can do everything that a range tower can do except the "splice"
24    operation.
25
26    Each operation has O(lg N) cost, where N is the number of contiguous regions
27    of 1-bits in the bitmap.  Also, a cache reduces the second and subsequent
28    containment tests within a single contiguous region to O(1).  */
29
30 #ifndef LIBPSPP_RANGE_TOWER_H
31 #define LIBPSPP_RANGE_TOWER_H
32
33 #include <limits.h>
34 #include <stdbool.h>
35 #include "libpspp/abt.h"
36 #include "libpspp/cast.h"
37
38 /* A tower of ranges. */
39 struct range_tower
40   {
41     struct pool *pool;          /* Pool for freeing range_tower. */
42     struct abt abt;             /* Tree of range_tower_nodes. */
43
44     /* Cache. */
45     unsigned long int cache_start; /* Start of region. */
46     unsigned long int cache_end;   /* One past end of region. */
47     bool cache_value;              /* Is the region in the tower? */
48   };
49
50 /* A node in the range tower. */
51 struct range_tower_node
52   {
53     struct abt_node abt_node;        /* Augmented binary tree node. */
54     unsigned long int n_zeros;       /* Number of leading zeros. */
55     unsigned long int n_ones;        /* Number of ones following the zeros. */
56     unsigned long int subtree_width; /* n_zeros + n_ones + sum of descendants. */
57   };
58
59 struct range_tower *range_tower_create (void);
60 struct range_tower *range_tower_create_pool (struct pool *);
61 struct range_tower *range_tower_clone (const struct range_tower *,
62                                        struct pool *);
63 void range_tower_destroy (struct range_tower *);
64
65 void range_tower_splice (struct range_tower *,
66                          unsigned long int start,
67                          unsigned long int old_width,
68                          unsigned long int new_width);
69
70 void range_tower_set1 (struct range_tower *,
71                        unsigned long int start, unsigned long int width);
72 void range_tower_set0 (struct range_tower *,
73                        unsigned long int start, unsigned long int width);
74
75 void range_tower_insert1 (struct range_tower *,
76                           unsigned long int start, unsigned long int width);
77 void range_tower_insert0 (struct range_tower *,
78                           unsigned long int start, unsigned long int width);
79
80 void range_tower_delete (struct range_tower *,
81                          unsigned long int start, unsigned long int width);
82
83 void range_tower_move (struct range_tower *,
84                        unsigned long int old_start,
85                        unsigned long int new_start,
86                        unsigned long int width);
87
88 bool range_tower_contains (const struct range_tower *,
89                            unsigned long int position);
90 unsigned long int range_tower_scan (const struct range_tower *,
91                                     unsigned long int start);
92
93 static inline bool range_tower_is_empty (const struct range_tower *);
94
95 #define RANGE_TOWER_FOR_EACH(NODE, START, RANGE_TOWER)                  \
96         for ((NODE) = range_tower_first (RANGE_TOWER), (START) = 0;     \
97              (NODE) && ((START) += (NODE)->n_zeros, true);              \
98              (START) += (NODE)->n_ones,                                 \
99                (NODE) = range_tower_next (RANGE_TOWER, NODE))
100
101 static inline const struct range_tower_node *range_tower_first (
102   const struct range_tower *);
103 static inline const struct range_tower_node *range_tower_next (
104   const struct range_tower *, const struct range_tower_node *);
105 static inline const struct range_tower_node *range_tower_last (
106   const struct range_tower *);
107 static inline const struct range_tower_node *range_tower_prev (
108   const struct range_tower *, const struct range_tower_node *);
109 unsigned long int range_tower_node_get_start (const struct range_tower_node *);
110 unsigned long int range_tower_node_get_end (const struct range_tower_node *);
111 static inline unsigned long int range_tower_node_get_width (
112   const struct range_tower_node *);
113 \f
114 /* Inline functions. */
115
116 static inline struct range_tower_node *range_tower_node_from_abt__ (
117   const struct abt_node *);
118 static inline struct range_tower_node *range_tower_next__ (
119   const struct range_tower *, const struct range_tower_node *);
120 static inline struct range_tower_node *range_tower_first__ (
121   const struct range_tower *);
122 static inline struct range_tower_node *range_tower_prev__ (
123   const struct range_tower *, const struct range_tower_node *);
124 static inline struct range_tower_node *range_tower_last__ (
125   const struct range_tower *);
126
127 /* Returns true if RS contains no 1-bits, false otherwise. */
128 static inline bool
129 range_tower_is_empty (const struct range_tower *rs)
130 {
131   const struct range_tower_node *node =
132     abt_data (rs->abt.root, struct range_tower_node, abt_node);
133
134   return node->n_zeros == ULONG_MAX;
135 }
136
137 /* Returns the node representing the first contiguous region of
138    1-bits in RS, or a null pointer if RS is empty.
139    Any call to range_tower_set1, range_tower_set0, or
140    range_tower_allocate invalidates the returned node. */
141 static inline const struct range_tower_node *
142 range_tower_first (const struct range_tower *rs)
143 {
144   const struct range_tower_node *node = range_tower_first__ (rs);
145   return node->n_ones ? node : NULL;
146 }
147
148 /* If NODE is nonnull, returns the node representing the next
149    contiguous region of 1-bits in RS following NODE, or a null
150    pointer if NODE is the last region in RS.
151    If NODE is null, returns the first region in RS, as for
152    range_tower_first.
153    Any call to range_tower_set1, range_tower_set0, or
154    range_tower_allocate invalidates the returned node. */
155 static inline const struct range_tower_node *
156 range_tower_next (const struct range_tower *rs,
157                   const struct range_tower_node *node)
158 {
159   if (node != NULL)
160     {
161       const struct range_tower_node *next = range_tower_next__ (rs, node);
162       return next != NULL && next->n_ones ? next : NULL;
163     }
164   else
165     return range_tower_first (rs);
166 }
167
168 /* Returns the node representing the last contiguous region of
169    1-bits in RS, or a null pointer if RS is empty.
170    Any call to range_tower_set1, range_tower_set0, or
171    range_tower_allocate invalidates the returned node. */
172 static inline const struct range_tower_node *
173 range_tower_last (const struct range_tower *rs)
174 {
175   const struct range_tower_node *node = range_tower_last__ (rs);
176   return node->n_ones ? node : range_tower_prev__(rs, node);
177 }
178
179 /* If NODE is nonnull, returns the node representing the previous
180    contiguous region of 1-bits in RS following NODE, or a null
181    pointer if NODE is the first region in RS.
182    If NODE is null, returns the last region in RS, as for
183    range_tower_last.
184    Any call to range_tower_set1, range_tower_set0, or
185    range_tower_allocate invalidates the returned node. */
186 static inline const struct range_tower_node *
187 range_tower_prev (const struct range_tower *rs,
188                   const struct range_tower_node *node)
189 {
190   return node != NULL ? range_tower_prev__ (rs, node) : range_tower_last (rs);
191 }
192
193 /* Returns the number of contiguous 1-bits in NODE. */
194 static inline unsigned long int
195 range_tower_node_get_width (const struct range_tower_node *node)
196 {
197   return node->n_ones;
198 }
199 \f
200 /* Internal helper functions. */
201
202 /* Returns the range_tower_node corresponding to the given
203    ABT_NODE.  Returns a null pointer if ABT_NODE is null. */
204 static inline struct range_tower_node *
205 range_tower_node_from_abt__ (const struct abt_node *abt_node)
206 {
207   return (abt_node
208           ? abt_data (abt_node, struct range_tower_node, abt_node)
209           : NULL);
210 }
211
212 /* Returns the next range_tower_node in RS after NODE,
213    or a null pointer if NODE is the last node in RS. */
214 static inline struct range_tower_node *
215 range_tower_next__ (const struct range_tower *rs,
216                     const struct range_tower_node *node)
217 {
218   return range_tower_node_from_abt__ (abt_next (&rs->abt, &node->abt_node));
219 }
220
221 /* Returns the first range_tower_node in RS,
222    or a null pointer if RS is empty. */
223 static inline struct range_tower_node *
224 range_tower_first__ (const struct range_tower *rs)
225 {
226   return range_tower_node_from_abt__ (abt_first (&rs->abt));
227 }
228
229 /* Returns the previous range_tower_node in RS after NODE,
230    or a null pointer if NODE is the first node in RS. */
231 static inline struct range_tower_node *
232 range_tower_prev__ (const struct range_tower *rs,
233                     const struct range_tower_node *node)
234 {
235   return range_tower_node_from_abt__ (abt_prev (&rs->abt, &node->abt_node));
236 }
237
238 /* Returns the last range_tower_node in RS,
239    or a null pointer if RS is empty. */
240 static inline struct range_tower_node *
241 range_tower_last__ (const struct range_tower *rs)
242 {
243   return range_tower_node_from_abt__ (abt_last (&rs->abt));
244 }
245
246 struct range_tower_node *range_tower_lookup (
247   const struct range_tower *, unsigned long int position,
248   unsigned long int *node_start);
249
250 #endif /* libpspp/range-tower.h */