include/pub_tool_rangemap.h

   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-2017 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 return NULL (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    This function never returns NULL. */
  50 RangeMap* VG_(newRangeMap) ( Alloc_Fn_t alloc_fn,
  51                              const HChar* cc,
  52                              Free_Fn_t free_fn,
  53                              UWord initialVal );
  54
  55 /* Free all memory associated with a RangeMap. */
  56 void VG_(deleteRangeMap) ( RangeMap* );
  57
  58 /* Bind the range [key_min, key_max] to val, overwriting any other
  59    bindings existing in the range.  Asserts if key_min > key_max.  If
  60    as a result of this addition, there come to be multiple adjacent
  61    ranges with the same value, these ranges are merged together.  Note
  62    that this is slow: O(N) in the number of existing ranges. */
  63 void VG_(bindRangeMap) ( RangeMap* rm,
  64                          UWord key_min, UWord key_max, UWord val );
  65
  66 /* Looks up |key| in the array and returns the associated value and
  67    the key bounds.  Can never fail since the RangeMap covers the
  68    entire key space.  This is fast: O(log N) in the number of
  69    ranges. */
  70 void VG_(lookupRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max,
  71                            /*OUT*/UWord* val, const RangeMap* rm, UWord key );
  72
  73 /* How many elements are there in the map? */
  74 UInt VG_(sizeRangeMap) ( const RangeMap* rm );
  75
  76 /* Get the i'th component */
  77 void VG_(indexRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max,
  78                           /*OUT*/UWord* val, const RangeMap* rm, Word ix );
  79
  80 #endif   // __PUB_TOOL_RANGEMAP_H
  81
  82 /*--------------------------------------------------------------------*/
  83 /*--- end                                      pub_tool_rangemap.h ---*/
  84 /*--------------------------------------------------------------------*/