
/*--------------------------------------------------------------------*/
/*--- A mapping where the keys exactly cover the address space.    ---*/
/*---                                                 m_rangemap.c ---*/
/*--------------------------------------------------------------------*/

/*
   This file is part of Valgrind, a dynamic binary instrumentation
   framework.

   Copyright (C) 2014-2017 Mozilla Foundation

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2 of the
   License, or (at your option) any later version.

   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   02111-1307, USA.

   The GNU General Public License is contained in the file COPYING.
*/

/* Contributed by Julian Seward <jseward@acm.org> */

#include "pub_core_basics.h"
#include "pub_core_libcassert.h"
#include "pub_core_libcprint.h"
#include "pub_core_xarray.h"
#include "pub_core_rangemap.h"    /* self */


/* See pub_tool_rangemap.h for details of what this is all about. */

#define UWORD_MIN ((UWord)0)
#define UWORD_MAX (~(UWord)0)

typedef
   struct { UWord key_min; UWord key_max; UWord val; }
   Range;


struct _RangeMap {
   Alloc_Fn_t alloc_fn;                /* alloc fn (nofail) */
   const HChar* cc;                    /* cost centre for alloc */
   Free_Fn_t free_fn;                  /* free fn */
   XArray* ranges;
};


/* fwds */
static void preen (/*MOD*/RangeMap* rm);
static Word find ( const RangeMap* rm, UWord key );
static void split_at ( /*MOD*/RangeMap* rm, UWord key );
static void show ( const RangeMap* rm );


RangeMap* VG_(newRangeMap) ( Alloc_Fn_t alloc_fn,
                             const HChar* cc,
                             Free_Fn_t free_fn,
                             UWord initialVal )
{
   /* check user-supplied info .. */
   vg_assert(alloc_fn);
   vg_assert(free_fn);
   RangeMap* rm = alloc_fn(cc, sizeof(RangeMap));
   rm->alloc_fn = alloc_fn;
   rm->cc       = cc;
   rm->free_fn  = free_fn;
   rm->ranges = VG_(newXA)( alloc_fn, cc, free_fn, sizeof(Range) );
   /* Add the initial range */
   Range r;
   r.key_min = UWORD_MIN;
   r.key_max = UWORD_MAX;
   r.val     = initialVal;
   Word i = VG_(addToXA)(rm->ranges, &r);
   vg_assert(i == 0);
   vg_assert(VG_(sizeXA)(rm->ranges) == 1);
   /* */
   return rm;
}

void VG_(deleteRangeMap) ( RangeMap* rm )
{
   vg_assert(rm);
   vg_assert(rm->free_fn);
   vg_assert(rm->ranges);
   VG_(deleteXA)(rm->ranges);
   rm->free_fn(rm);
}

void VG_(bindRangeMap) ( RangeMap* rm,
                         UWord key_min, UWord key_max, UWord val )
{
   vg_assert(key_min <= key_max);
   split_at(rm, key_min);
   if (key_max < UWORD_MAX)
      split_at(rm, key_max + 1);
   Word iMin, iMax, i;
   iMin = find(rm, key_min);
   iMax = find(rm, key_max);
   for (i = iMin; i <= iMax; i++) {
      Range* rng = VG_(indexXA)(rm->ranges, i);
      rng->val = val;
   }
   preen(rm);
}

void VG_(lookupRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max,
                           /*OUT*/UWord* val, const RangeMap* rm, UWord key )
{
   Word   i   = find(rm, key);
   Range* rng = (Range*)VG_(indexXA)(rm->ranges, i);
   *key_min = rng->key_min;
   *key_max = rng->key_max;
   *val     = rng->val;
}

UInt VG_(sizeRangeMap) ( const RangeMap* rm )
{
   vg_assert(rm && rm->ranges);
   Word size = VG_(sizeXA)(rm->ranges);
   vg_assert(size >= 0);
   return size;
}

void VG_(indexRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max,
                          /*OUT*/UWord* val, const RangeMap* rm, Word ix )
{
   vg_assert(rm && rm->ranges);
   Range* rng = (Range*)VG_(indexXA)(rm->ranges, ix);
   *key_min = rng->key_min;
   *key_max = rng->key_max;
   *val     = rng->val;
}

/* Helper functions, not externally visible. */

static void preen (/*MOD*/RangeMap* rm)
{
   Word    i;
   XArray* ranges = rm->ranges;
   for (i = 0; i < VG_(sizeXA)(ranges) - 1; i++) {
      Range* rng0 = VG_(indexXA)(ranges, i+0);
      Range* rng1 = VG_(indexXA)(ranges, i+1);
      if (rng0->val != rng1->val)
         continue;
      rng0->key_max = rng1->key_max;
      VG_(removeIndexXA)(ranges, i+1);
      /* Back up one, so as not to miss an opportunity to merge with
         the entry after this one. */
      i--;
   }
}

static Word find ( const RangeMap* rm, UWord key )
{
   XArray* ranges = rm->ranges;
   Word    lo     = 0;
   Word    hi     = VG_(sizeXA)(ranges);
   while (True) {
      /* The unsearched space is lo .. hi inclusive */
      if (lo > hi) {
         /* Not found.  This can't happen. */
         VG_(core_panic)("RangeMap::find: not found");
         /*NOTREACHED*/
         return -1;
      }
      Word   mid         = (lo + hi) / 2;
      Range* mid_rng     = (Range*)VG_(indexXA)(ranges, mid);
      UWord  key_mid_min = mid_rng->key_min;
      UWord  key_mid_max = mid_rng->key_max;
      if (key < key_mid_min) { hi = mid-1; continue; }
      if (key > key_mid_max) { lo = mid+1; continue; }
      return mid;
   }
}

static void split_at ( /*MOD*/RangeMap* rm, UWord key )
{
   XArray* ranges = rm->ranges;
   Word    i      = find(rm, key);
   Range   rng_i0 = *(Range*)VG_(indexXA)( ranges, i+0 );
   if (rng_i0.key_min == key)
      return;
   VG_(insertIndexXA)( ranges, i+1, &rng_i0 );
   /* The insert could have relocated the payload, hence the
      re-indexing of i+0 here. */
   Range* rng_i0p = (Range*)VG_(indexXA)( ranges, i+0 );
   Range* rng_i1p = (Range*)VG_(indexXA)( ranges, i+1 );
   rng_i0p->key_max = key-1;
   rng_i1p->key_min = key;
}

__attribute__((unused))
static void show ( const RangeMap* rm )
{
   Word i;
   VG_(printf)("<< %ld entries:\n", VG_(sizeXA)(rm->ranges) );
   for (i = 0; i < VG_(sizeXA)(rm->ranges); i++) {
      Range* rng = (Range*)VG_(indexXA)(rm->ranges, i);
      VG_(printf)("  %016llx  %016llx  --> 0x%llx\n",
                  (ULong)rng->key_min, (ULong)rng->key_max, (ULong)rng->val);
   }
   VG_(printf)(">>\n");
}


/*--------------------------------------------------------------------*/
/*--- end                                             m_rangemap.c ---*/
/*--------------------------------------------------------------------*/