1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 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 #include <config.h>
18
19 #include "libpspp/range-map.h"
20
21 #include "libpspp/assertion.h"
22 #include "libpspp/compiler.h"
23
24 static struct range_map_node *bt_to_range_map_node (const struct bt_node *);
25 static int compare_range_map_nodes (const struct bt_node *,
26 const struct bt_node *,
27 const void *aux);
28 static struct range_map_node *first_node (const struct range_map *);
29 static struct range_map_node *next_node (const struct range_map *,
30 const struct range_map_node *);
31 static struct range_map_node *prev_node (const struct range_map *,
32 const struct range_map_node *) UNUSED;
33
34 /* Initializes RM as an empty range map. */
35 void
range_map_init(struct range_map * rm)36 range_map_init (struct range_map *rm)
37 {
38 bt_init (&rm->bt, compare_range_map_nodes, NULL);
39 }
40
41 /* Returns true if RM contains no mappings,
42 false if it contains at least one. */
43 bool
range_map_is_empty(const struct range_map * rm)44 range_map_is_empty (const struct range_map *rm)
45 {
46 return bt_count (&rm->bt) == 0;
47 }
48
49 /* Inserts node NEW into RM, covering the range beginning at
50 START and ending at START + WIDTH (exclusive). WIDTH must be
51 at least 1. The new range must not overlap any existing range
52 already in RM. */
53 void
range_map_insert(struct range_map * rm,unsigned long int start,unsigned long int width,struct range_map_node * new)54 range_map_insert (struct range_map *rm,
55 unsigned long int start, unsigned long int width,
56 struct range_map_node *new)
57 {
58 unsigned long int end = start + width;
59 struct range_map_node *dup;
60
61 assert (width > 0);
62 assert (end - 1 >= start);
63
64 new->start = start;
65 new->end = end;
66 dup = bt_to_range_map_node (bt_insert (&rm->bt, &new->bt_node));
67
68 /* Make sure NEW doesn't overlap any other node. */
69 assert (dup == NULL);
70 assert (prev_node (rm, new) == NULL || start >= prev_node (rm, new)->end);
71 assert (next_node (rm, new) == NULL || next_node (rm, new)->start >= end);
72 }
73
74 /* Deletes NODE from RM. */
75 void
range_map_delete(struct range_map * rm,struct range_map_node * node)76 range_map_delete (struct range_map *rm, struct range_map_node *node)
77 {
78 bt_delete (&rm->bt, &node->bt_node);
79 }
80
81 /* Returns the node in RM that contains the given POSITION, or a
82 null pointer if no node contains POSITION. */
83 struct range_map_node *
range_map_lookup(const struct range_map * rm,unsigned long int position)84 range_map_lookup (const struct range_map *rm,
85 unsigned long int position)
86 {
87 struct range_map_node tmp, *node;
88
89 tmp.start = position;
90 node = bt_to_range_map_node (bt_find_le (&rm->bt, &tmp.bt_node));
91 return node != NULL && position < node->end ? node : NULL;
92 }
93
94 /* Returns the first node in RM, or a null pointer if RM is
95 empty. */
96 struct range_map_node *
range_map_first(const struct range_map * rm)97 range_map_first (const struct range_map *rm)
98 {
99 return first_node (rm);
100 }
101
102 /* If NODE is nonnull, returns the node in RM following NODE, or
103 a null pointer if NODE is the last node in RM.
104 If NODE is null, behaves like range_map_first. */
105 struct range_map_node *
range_map_next(const struct range_map * rm,const struct range_map_node * node)106 range_map_next (const struct range_map *rm,
107 const struct range_map_node *node)
108 {
109 return node != NULL ? next_node (rm, node) : first_node (rm);
110 }
111
112 /* Returns the range_map_node containing BT_NODE. */
113 static struct range_map_node *
bt_to_range_map_node(const struct bt_node * bt_node)114 bt_to_range_map_node (const struct bt_node *bt_node)
115 {
116 return (bt_node != NULL
117 ? BT_DATA (bt_node, struct range_map_node, bt_node)
118 : NULL);
119 }
120
121 /* Compares range map nodes A and B and returns a strcmp()-type
122 result. */
123 static int
compare_range_map_nodes(const struct bt_node * a_,const struct bt_node * b_,const void * aux UNUSED)124 compare_range_map_nodes (const struct bt_node *a_,
125 const struct bt_node *b_,
126 const void *aux UNUSED)
127 {
128 const struct range_map_node *a = bt_to_range_map_node (a_);
129 const struct range_map_node *b = bt_to_range_map_node (b_);
130 return a->start < b->start ? -1 : a->start > b->start;
131 }
132
133 /* Returns the first range map node in RM, or a null pointer if
134 RM is empty. */
135 static struct range_map_node *
first_node(const struct range_map * rm)136 first_node (const struct range_map *rm)
137 {
138 return bt_to_range_map_node (bt_first (&rm->bt));
139 }
140
141 /* Returns the next range map node in RM following NODE, or a
142 null pointer if NODE is the last node in RM. */
143 static struct range_map_node *
next_node(const struct range_map * rm,const struct range_map_node * node)144 next_node (const struct range_map *rm, const struct range_map_node *node)
145 {
146 return bt_to_range_map_node (bt_next (&rm->bt, &node->bt_node));
147 }
148
149 /* Returns the previous range map node in RM preceding NODE, or a
150 null pointer if NODE is the first node in RM. */
151 static struct range_map_node *
prev_node(const struct range_map * rm,const struct range_map_node * node)152 prev_node (const struct range_map *rm, const struct range_map_node *node)
153 {
154 return bt_to_range_map_node (bt_prev (&rm->bt, &node->bt_node));
155 }
156
157