src/libpspp/range-map.h

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