1
2/*--------------------------------------------------------------------*/
3/*--- A mapping where the keys exactly cover the address space.    ---*/
4/*---                                          pub_tool_rangemap.h ---*/
5/*--------------------------------------------------------------------*/
6
7/*
8   This file is part of Valgrind, a dynamic binary instrumentation
9   framework.
10
11   Copyright (C) 2014-2014 Mozilla Foundation
12
13   This program is free software; you can redistribute it and/or
14   modify it under the terms of the GNU General Public License as
15   published by the Free Software Foundation; either version 2 of the
16   License, or (at your option) any later version.
17
18   This program is distributed in the hope that it will be useful, but
19   WITHOUT ANY WARRANTY; without even the implied warranty of
20   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
21   General Public License for more details.
22
23   You should have received a copy of the GNU General Public License
24   along with this program; if not, write to the Free Software
25   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
26   02111-1307, USA.
27
28   The GNU General Public License is contained in the file COPYING.
29*/
30
31/* Contributed by Julian Seward <jseward@acm.org> */
32
33#ifndef __PUB_TOOL_RANGEMAP_H
34#define __PUB_TOOL_RANGEMAP_H
35
36//--------------------------------------------------------------------
37// PURPOSE: a mapping from the host machine word (UWord) ranges to
38// arbitrary other UWord values.  The set of ranges exactly covers all
39// possible UWord values.
40// --------------------------------------------------------------------
41
42/* It's an abstract type. */
43typedef  struct _RangeMap  RangeMap;
44
45/* Create a new RangeMap, using given allocation and free functions.
46   Alloc fn must not fail (that is, if it returns it must have
47   succeeded.)  The new array will contain a single range covering the
48   entire key space, which will be bound to the value |initialVal|. */
49RangeMap* VG_(newRangeMap) ( void*(*alloc_fn)(const HChar*,SizeT),
50                             const HChar* cc,
51                             void(*free_fn)(void*),
52                             UWord initialVal );
53
54/* Free all memory associated with a RangeMap. */
55void VG_(deleteRangeMap) ( RangeMap* );
56
57/* Bind the range [key_min, key_max] to val, overwriting any other
58   bindings existing in the range.  Asserts if key_min > key_max.  If
59   as a result of this addition, there come to be multiple adjacent
60   ranges with the same value, these ranges are merged together.  Note
61   that this is slow: O(N) in the number of existing ranges. */
62void VG_(bindRangeMap) ( RangeMap* rm,
63                         UWord key_min, UWord key_max, UWord val );
64
65/* Looks up |key| in the array and returns the associated value and
66   the key bounds.  Can never fail since the RangeMap covers the
67   entire key space.  This is fast: O(log N) in the number of
68   ranges. */
69void VG_(lookupRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max,
70                           /*OUT*/UWord* val, RangeMap* rm, UWord key );
71
72/* How many elements are there in the map? */
73Word VG_(sizeRangeMap) ( RangeMap* rm );
74
75/* Get the i'th component */
76void VG_(indexRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max,
77                          /*OUT*/UWord* val, RangeMap* rm, Word ix );
78
79#endif   // __PUB_TOOL_RANGEMAP_H
80
81/*--------------------------------------------------------------------*/
82/*--- end                                      pub_tool_rangemap.h ---*/
83/*--------------------------------------------------------------------*/
84