src/libpspp/range-map.c

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 2007 Free Software Foundation, Inc.
   3
   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.
   8
   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.
  13
  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
  17    02110-1301, USA. */
  18
  19 #include <config.h>
  20
  21 #include <libpspp/range-map.h>
  22
  23 #include <libpspp/assertion.h>
  24 #include <libpspp/compiler.h>
  25
  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 *,
  29                                     const void *aux);
  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;
  35
  36 /* Initializes RM as an empty range map. */
  37 void
  38 range_map_init (struct range_map *rm)
  39 {
  40   bt_init (&rm->bt, compare_range_map_nodes, NULL);
  41 }
  42
  43 /* Returns true if RM contains no mappings,
  44    false if it contains at least one. */
  45 bool
  46 range_map_is_empty (const struct range_map *rm)
  47 {
  48   return bt_count (&rm->bt) == 0;
  49 }
  50
  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
  54    already in RM. */
  55 void
  56 range_map_insert (struct range_map *rm,
  57                   unsigned long int start, unsigned long int width,
  58                   struct range_map_node *new)
  59 {
  60   unsigned long int end = start + width;
  61   struct range_map_node *dup;
  62
  63   assert (width > 0);
  64   assert (end - 1 >= start);
  65
  66   new->start = start;
  67   new->end = end;
  68   dup = bt_to_range_map_node (bt_insert (&rm->bt, &new->bt_node));
  69
  70   /* Make sure NEW doesn't overlap any other node. */
  71   assert (dup == NULL);
  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);
  74 }
  75
  76 /* Deletes NODE from RM. */
  77 void
  78 range_map_delete (struct range_map *rm, struct range_map_node *node)
  79 {
  80   bt_delete (&rm->bt, &node->bt_node);
  81 }
  82
  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)
  88 {
  89   struct range_map_node tmp, *node;
  90
  91   tmp.start = position;
  92   node = bt_to_range_map_node (bt_find_le (&rm->bt, &tmp.bt_node));
  93   return node != NULL && position < node->end ? node : NULL;
  94 }
  95
  96 /* Returns the first node in RM, or a null pointer if RM is
  97    empty. */
  98 struct range_map_node *
  99 range_map_first (const struct range_map *rm)
 100 {
 101   return first_node (rm);
 102 }
 103
 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)
 110 {
 111   return node != NULL ? next_node (rm, node) : first_node (rm);
 112 }
 113 \f
 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)
 117 {
 118   return (bt_node != NULL
 119           ? bt_data (bt_node, struct range_map_node, bt_node)
 120           : NULL);
 121 }
 122
 123 /* Compares range map nodes A and B and returns a strcmp()-type
 124    result. */
 125 static int
 126 compare_range_map_nodes (const struct bt_node *a_,
 127                          const struct bt_node *b_,
 128                          const void *aux UNUSED)
 129 {
 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;
 133 }
 134
 135 /* Returns the first range map node in RM, or a null pointer if
 136    RM is empty. */
 137 static struct range_map_node *
 138 first_node (const struct range_map *rm)
 139 {
 140   return bt_to_range_map_node (bt_first (&rm->bt));
 141 }
 142
 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)
 147 {
 148   return bt_to_range_map_node (bt_next (&rm->bt, &node->bt_node));
 149 }
 150
 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)
 155 {
 156   return bt_to_range_map_node (bt_prev (&rm->bt, &node->bt_node));
 157 }
 158