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. */ 43 typedef 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|. */ 49 RangeMap* 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. */ 55 void 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. */ 62 void 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. */ 69 void 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? */ 73 Word VG_(sizeRangeMap) ( RangeMap* rm ); 74 75 /* Get the i'th component */ 76 void 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