include/valgrind/pub_tool_rangemap.h

0001
0002 /*--------------------------------------------------------------------*/
0003 /*--- A mapping where the keys exactly cover the address space.    ---*/
0004 /*---                                          pub_tool_rangemap.h ---*/
0005 /*--------------------------------------------------------------------*/
0006
0007 /*
0008    This file is part of Valgrind, a dynamic binary instrumentation
0009    framework.
0010
0011    Copyright (C) 2014-2017 Mozilla Foundation
0012
0013    This program is free software; you can redistribute it and/or
0014    modify it under the terms of the GNU General Public License as
0015    published by the Free Software Foundation; either version 2 of the
0016    License, or (at your option) any later version.
0017
0018    This program is distributed in the hope that it will be useful, but
0019    WITHOUT ANY WARRANTY; without even the implied warranty of
0020    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
0021    General Public License for more details.
0022
0023    You should have received a copy of the GNU General Public License
0024    along with this program; if not, see <http://www.gnu.org/licenses/>.
0025
0026    The GNU General Public License is contained in the file COPYING.
0027 */
0028
0029 /* Contributed by Julian Seward <jseward@acm.org> */
0030
0031 #ifndef __PUB_TOOL_RANGEMAP_H
0032 #define __PUB_TOOL_RANGEMAP_H
0033
0034 //--------------------------------------------------------------------
0035 // PURPOSE: a mapping from the host machine word (UWord) ranges to
0036 // arbitrary other UWord values.  The set of ranges exactly covers all
0037 // possible UWord values.
0038 // --------------------------------------------------------------------
0039
0040 /* It's an abstract type. */
0041 typedef  struct _RangeMap  RangeMap;
0042
0043 /* Create a new RangeMap, using given allocation and free functions.
0044    alloc_fn must not return NULL (that is, if it returns it must have
0045    succeeded.)  The new array will contain a single range covering the
0046    entire key space, which will be bound to the value |initialVal|.
0047    This function never returns NULL. */
0048 RangeMap* VG_(newRangeMap) ( Alloc_Fn_t alloc_fn,
0049                              const HChar* cc,
0050                              Free_Fn_t free_fn,
0051                              UWord initialVal );
0052
0053 /* Free all memory associated with a RangeMap. */
0054 void VG_(deleteRangeMap) ( RangeMap* );
0055
0056 /* Bind the range [key_min, key_max] to val, overwriting any other
0057    bindings existing in the range.  Asserts if key_min > key_max.  If
0058    as a result of this addition, there come to be multiple adjacent
0059    ranges with the same value, these ranges are merged together.  Note
0060    that this is slow: O(N) in the number of existing ranges. */
0061 void VG_(bindRangeMap) ( RangeMap* rm,
0062                          UWord key_min, UWord key_max, UWord val );
0063
0064 /* Looks up |key| in the array and returns the associated value and
0065    the key bounds.  Can never fail since the RangeMap covers the
0066    entire key space.  This is fast: O(log N) in the number of
0067    ranges. */
0068 void VG_(lookupRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max,
0069                            /*OUT*/UWord* val, const RangeMap* rm, UWord key );
0070
0071 /* How many elements are there in the map? */
0072 UInt VG_(sizeRangeMap) ( const RangeMap* rm );
0073
0074 /* Get the i'th component */
0075 void VG_(indexRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max,
0076                           /*OUT*/UWord* val, const RangeMap* rm, Word ix );
0077
0078 #endif   // __PUB_TOOL_RANGEMAP_H
0079
0080 /*--------------------------------------------------------------------*/
0081 /*--- end                                      pub_tool_rangemap.h ---*/
0082 /*--------------------------------------------------------------------*/