gui: Allow File|Open to select an encoding for system files.
[pspp] / src / libpspp / range-map.c
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
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
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
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
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 *
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 *
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 *
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 \f
112 /* Returns the range_map_node containing BT_NODE. */
113 static struct range_map_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
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 *
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 *
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 *
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