pintos-os.org Git - pspp/blob - src/libpspp/range-map.h

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007 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 #ifndef LIBPSPP_RANGE_MAP_H
  18 #define LIBPSPP_RANGE_MAP_H
  19
  20 /* Range map data structure, implemented as a balanced binary
  21    tree.
  22
  23    This is a dictionary data structure that maps from contiguous
  24    ranges of "unsigned long int" keys to arbitrary data
  25    values.
  26
  27    The implementation is not robust against ranges that include
  28    ULONG_MAX in their ranges.  Such ranges are difficult to deal
  29    with in C anyhow, because a range that includes 0 through
  30    ULONG_MAX inclusive has a width of ULONG_MAX + 1, which equals
  31    0. */
  32
  33 #include <stdbool.h>
  34
  35 #include <libpspp/bt.h>
  36
  37 /* Returns the data structure corresponding to the given NODE,
  38    assuming that NODE is embedded as the given MEMBER name in
  39    data type STRUCT. */
  40 #define range_map_data(NODE, STRUCT, MEMBER)                            \
  41         ((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
  42
  43 /* A range map node, to be embedded in the data value. */
  44 struct range_map_node
  45   {
  46     struct bt_node bt_node;     /* Balanced tree node. */
  47     unsigned long int start;    /* Start of range. */
  48     unsigned long int end;      /* End of range, plus one. */
  49   };
  50
  51 /* Returns the start of the range in the given NODE. */
  52 static inline unsigned long int
  53 range_map_node_get_start (const struct range_map_node *node)
  54 {
  55   return node->start;
  56 }
  57
  58 /* Returns the end of the range in the given NODE, plus one. */
  59 static inline unsigned long int
  60 range_map_node_get_end (const struct range_map_node *node)
  61 {
  62   return node->end;
  63 }
  64
  65 /* Returns the width of the range in the given NODE. */
  66 static inline unsigned long int
  67 range_map_node_get_width (const struct range_map_node *node)
  68 {
  69   return node->end - node->start;
  70 }
  71 \f
  72 /* Range map. */
  73 struct range_map
  74   {
  75     struct bt bt;
  76   };
  77
  78 void range_map_init (struct range_map *);
  79
  80 bool range_map_is_empty (const struct range_map *);
  81
  82 void range_map_insert (struct range_map *,
  83                        unsigned long int start, unsigned long int width,
  84                        struct range_map_node *new);
  85 void range_map_delete (struct range_map *, struct range_map_node *);
  86
  87 struct range_map_node *range_map_lookup (const struct range_map *,
  88                                          unsigned long int position);
  89 struct range_map_node *range_map_first (const struct range_map *);
  90 struct range_map_node *range_map_next (const struct range_map *,
  91                                        const struct range_map_node *);
  92
  93 #endif /* libpspp/range-map.h */