Change license from GPLv2+ to GPLv3+.
[pspp-builds.git] / src / libpspp / range-map.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 #ifndef LIBPSPP_RANGE_MAP_H
18 #define LIBPSPP_RANGE_MAP_H
19
20 /* Range map data structure, implemented as a balanced binary
21    tree.
22
23    This is a dictionary data structure that maps from contiguous
24    ranges of "unsigned long int" keys to arbitrary data
25    values.
26
27    The implementation is not robust against ranges that include
28    ULONG_MAX in their ranges.  Such ranges are difficult to deal
29    with in C anyhow, because a range that includes 0 through
30    ULONG_MAX inclusive has a width of ULONG_MAX + 1, which equals
31    0. */
32
33 #include <stdbool.h>
34
35 #include <libpspp/bt.h>
36
37 /* Returns the data structure corresponding to the given NODE,
38    assuming that NODE is embedded as the given MEMBER name in
39    data type STRUCT. */
40 #define range_map_data(NODE, STRUCT, MEMBER)                            \
41         ((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
42
43 /* A range map node, to be embedded in the data value. */
44 struct range_map_node
45   {
46     struct bt_node bt_node;     /* Balanced tree node. */
47     unsigned long int start;    /* Start of range. */
48     unsigned long int end;      /* End of range, plus one. */
49   };
50
51 /* Returns the start of the range in the given NODE. */
52 static inline unsigned long int
53 range_map_node_get_start (const struct range_map_node *node)
54 {
55   return node->start;
56 }
57
58 /* Returns the end of the range in the given NODE, plus one. */
59 static inline unsigned long int
60 range_map_node_get_end (const struct range_map_node *node)
61 {
62   return node->end;
63 }
64
65 /* Returns the width of the range in the given NODE. */
66 static inline unsigned long int
67 range_map_node_get_width (const struct range_map_node *node)
68 {
69   return node->end - node->start;
70 }
71 \f
72 /* Range map. */
73 struct range_map
74   {
75     struct bt bt;
76   };
77
78 void range_map_init (struct range_map *);
79
80 bool range_map_is_empty (const struct range_map *);
81
82 void range_map_insert (struct range_map *,
83                        unsigned long int start, unsigned long int width,
84                        struct range_map_node *new);
85 void range_map_delete (struct range_map *, struct range_map_node *);
86
87 struct range_map_node *range_map_lookup (const struct range_map *,
88                                          unsigned long int position);
89 struct range_map_node *range_map_first (const struct range_map *);
90 struct range_map_node *range_map_next (const struct range_map *,
91                                        const struct range_map_node *);
92
93 #endif /* libpspp/range-map.h */