gprofng/src/IntervalMap.h

   1 /* Copyright (C) 2021 Free Software Foundation, Inc.
   2    Contributed by Oracle.
   3
   4    This file is part of GNU Binutils.
   5
   6    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3, or (at your option)
   9    any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program; if not, write to the Free Software
  18    Foundation, 51 Franklin Street - Fifth Floor, Boston,
  19    MA 02110-1301, USA.  */
  20
  21 /*
  22  *  Interval Map implementation.
  23  *
  24  *    Interval Map makes the following assumptions:
  25  *    - if duplicate keys, the last one will be stored
  26  *    - <TBC>
  27  */
  28 #ifndef _DBE_INTERVALMAP_H
  29 #define _DBE_INTERVALMAP_H
  30
  31 #include <assert.h>
  32 #include <vec.h>
  33 #include <Map.h>
  34
  35 template <typename Key_t, typename Value_t>
  36 class IntervalMap : public Map<Key_t, Value_t>
  37 {
  38 public:
  39
  40   IntervalMap ();
  41   ~IntervalMap ();
  42   void put (Key_t key, Value_t val);
  43   Value_t get (Key_t key);
  44   Value_t get (Key_t key, typename Map<Key_t, Value_t>::Relation rel);
  45   Value_t remove (Key_t key);
  46
  47 private:
  48
  49   struct Entry
  50   {
  51     Key_t key;
  52     Value_t val;
  53   };
  54
  55   static const int CHUNK_SIZE;
  56
  57   int entries;
  58   int nchunks;
  59   Entry **chunks;
  60   Vector<Entry*> *index;
  61 };
  62
  63 template <typename Key_t, typename Value_t>
  64 const int IntervalMap<Key_t, Value_t>::CHUNK_SIZE = 16384;
  65
  66 template <typename Key_t, typename Value_t>
  67 IntervalMap<Key_t, Value_t>::IntervalMap ()
  68 {
  69   entries = 0;
  70   nchunks = 0;
  71   chunks = NULL;
  72   index = new Vector<Entry*>;
  73 }
  74
  75 template <typename Key_t, typename Value_t>
  76 IntervalMap<Key_t, Value_t>::~IntervalMap ()
  77 {
  78   for (int i = 0; i < nchunks; i++)
  79     delete[] chunks[i];
  80   delete[] chunks;
  81   delete index;
  82 }
  83
  84 template <typename Key_t, typename Value_t>
  85 void
  86 IntervalMap<Key_t, Value_t>::put (Key_t key, Value_t val)
  87 {
  88   int lo = 0;
  89   int hi = entries - 1;
  90   while (lo <= hi)
  91     {
  92       int md = (lo + hi) / 2;
  93       Entry *entry = index->fetch (md);
  94       int cmp = entry->key < key ? -1 : entry->key > key ? 1 : 0;
  95       if (cmp < 0)
  96         lo = md + 1;
  97       else if (cmp > 0)
  98         hi = md - 1;
  99       else
 100         {
 101           entry->val = val;
 102           return;
 103         }
 104     }
 105
 106   if (entries >= nchunks * CHUNK_SIZE)
 107     {
 108       nchunks++;
 109       // Reallocate Entry chunk array
 110       Entry **new_chunks = new Entry*[nchunks];
 111       for (int i = 0; i < nchunks - 1; i++)
 112         new_chunks[i] = chunks[i];
 113       delete chunks;
 114       chunks = new_chunks;
 115
 116       // Allocate new chunk for entries.
 117       chunks[nchunks - 1] = new Entry[CHUNK_SIZE];
 118     }
 119   Entry *entry = &chunks[entries / CHUNK_SIZE][entries % CHUNK_SIZE];
 120   entry->key = key;
 121   entry->val = val;
 122   index->insert (lo, entry);
 123   entries++;
 124 }
 125
 126 template <typename Key_t, typename Value_t>
 127 Value_t
 128 IntervalMap<Key_t, Value_t>::get (Key_t key)
 129 {
 130   return get (key, Map<Key_t, Value_t>::REL_EQ);
 131 }
 132
 133 template <typename Key_t, typename Value_t>
 134 Value_t
 135 IntervalMap<Key_t, Value_t>::get (Key_t key, typename Map<Key_t, Value_t>::Relation rel)
 136 {
 137   int lo = 0;
 138   int hi = entries - 1;
 139   while (lo <= hi)
 140     {
 141       int md = (lo + hi) / 2;
 142       Entry *entry = index->fetch (md);
 143       int cmp = entry->key < key ? -1 : entry->key > key ? 1 : 0;
 144       switch (rel)
 145         {
 146         case Map<Key_t, Value_t>::REL_LT:
 147           if (cmp < 0)
 148             lo = md + 1;
 149           else
 150             hi = md - 1;
 151           break;
 152         case Map<Key_t, Value_t>::REL_GT:
 153           if (cmp <= 0)
 154             lo = md + 1;
 155           else
 156             hi = md - 1;
 157           break;
 158         case Map<Key_t, Value_t>::REL_LE:
 159         case Map<Key_t, Value_t>::REL_GE:
 160         case Map<Key_t, Value_t>::REL_EQ:
 161           if (cmp < 0)
 162             lo = md + 1;
 163           else if (cmp > 0)
 164             hi = md - 1;
 165           else
 166             return entry->val;
 167           break;
 168         }
 169     }
 170   switch (rel)
 171     {
 172     case Map<Key_t, Value_t>::REL_LT:
 173     case Map<Key_t, Value_t>::REL_LE:
 174       return hi >= 0 ? index->fetch (hi)->val : (Value_t) 0;
 175     case Map<Key_t, Value_t>::REL_GT:
 176     case Map<Key_t, Value_t>::REL_GE:
 177       return lo < entries ? index->fetch (lo)->val : (Value_t) 0;
 178     case Map<Key_t, Value_t>::REL_EQ:
 179       break;
 180     }
 181   return (Value_t) 0;
 182 }
 183
 184 template <typename Key_t, typename Value_t>
 185 Value_t
 186 IntervalMap<Key_t, Value_t>::remove (Key_t)
 187 {
 188   // Not implemented
 189   if (1)
 190     assert (0);
 191   return (Value_t) 0;
 192 }
 193
 194 #endif