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