1 /* PSPP - computes sample statistics.
2 Copyright (C) 2007 Free Software Foundation, Inc.
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License as
6 published by the Free Software Foundation; either version 2 of the
7 License, or (at your option) any later version.
9 This program is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21 #include <libpspp/range-map.h>
23 #include <libpspp/assertion.h>
24 #include <libpspp/compiler.h>
26 static struct range_map_node *bt_to_range_map_node (const struct bt_node *);
27 static int compare_range_map_nodes (const struct bt_node *,
28 const struct bt_node *,
30 static struct range_map_node *first_node (const struct range_map *);
31 static struct range_map_node *next_node (const struct range_map *,
32 const struct range_map_node *);
33 static struct range_map_node *prev_node (const struct range_map *,
34 const struct range_map_node *) UNUSED;
36 /* Initializes RM as an empty range map. */
38 range_map_init (struct range_map *rm)
40 bt_init (&rm->bt, compare_range_map_nodes, NULL);
43 /* Returns true if RM contains no mappings,
44 false if it contains at least one. */
46 range_map_is_empty (const struct range_map *rm)
48 return bt_count (&rm->bt) == 0;
51 /* Inserts node NEW into RM, covering the range beginning at
52 START and ending at START + WIDTH (exclusive). WIDTH must be
53 at least 1. The new range must not overlap any existing range
56 range_map_insert (struct range_map *rm,
57 unsigned long int start, unsigned long int width,
58 struct range_map_node *new)
60 unsigned long int end = start + width;
61 struct range_map_node *dup;
64 assert (end - 1 >= start);
68 dup = bt_to_range_map_node (bt_insert (&rm->bt, &new->bt_node));
70 /* Make sure NEW doesn't overlap any other node. */
72 assert (prev_node (rm, new) == NULL || start >= prev_node (rm, new)->end);
73 assert (next_node (rm, new) == NULL || next_node (rm, new)->start >= end);
76 /* Deletes NODE from RM. */
78 range_map_delete (struct range_map *rm, struct range_map_node *node)
80 bt_delete (&rm->bt, &node->bt_node);
83 /* Returns the node in RM that contains the given POSITION, or a
84 null pointer if no node contains POSITION. */
85 struct range_map_node *
86 range_map_lookup (const struct range_map *rm,
87 unsigned long int position)
89 struct range_map_node tmp, *node;
92 node = bt_to_range_map_node (bt_find_le (&rm->bt, &tmp.bt_node));
93 return node != NULL && position < node->end ? node : NULL;
96 /* Returns the first node in RM, or a null pointer if RM is
98 struct range_map_node *
99 range_map_first (const struct range_map *rm)
101 return first_node (rm);
104 /* If NODE is nonnull, returns the node in RM following NODE, or
105 a null pointer if NODE is the last node in RM.
106 If NODE is null, behaves like range_map_first. */
107 struct range_map_node *
108 range_map_next (const struct range_map *rm,
109 const struct range_map_node *node)
111 return node != NULL ? next_node (rm, node) : first_node (rm);
114 /* Returns the range_map_node containing BT_NODE. */
115 static struct range_map_node *
116 bt_to_range_map_node (const struct bt_node *bt_node)
118 return (bt_node != NULL
119 ? bt_data (bt_node, struct range_map_node, bt_node)
123 /* Compares range map nodes A and B and returns a strcmp()-type
126 compare_range_map_nodes (const struct bt_node *a_,
127 const struct bt_node *b_,
128 const void *aux UNUSED)
130 const struct range_map_node *a = bt_to_range_map_node (a_);
131 const struct range_map_node *b = bt_to_range_map_node (b_);
132 return a->start < b->start ? -1 : a->start > b->start;
135 /* Returns the first range map node in RM, or a null pointer if
137 static struct range_map_node *
138 first_node (const struct range_map *rm)
140 return bt_to_range_map_node (bt_first (&rm->bt));
143 /* Returns the next range map node in RM following NODE, or a
144 null pointer if NODE is the last node in RM. */
145 static struct range_map_node *
146 next_node (const struct range_map *rm, const struct range_map_node *node)
148 return bt_to_range_map_node (bt_next (&rm->bt, &node->bt_node));
151 /* Returns the previous range map node in RM preceding NODE, or a
152 null pointer if NODE is the first node in RM. */
153 static struct range_map_node *
154 prev_node (const struct range_map *rm, const struct range_map_node *node)
156 return bt_to_range_map_node (bt_prev (&rm->bt, &node->bt_node));