1/* Copyright (C) 2021-2024 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 35template <typename Key_t, typename Value_t> 36class IntervalMap : public Map<Key_t, Value_t> 37{ 38public: 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 47private: 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 63template <typename Key_t, typename Value_t> 64const int IntervalMap<Key_t, Value_t>::CHUNK_SIZE = 16384; 65 66template <typename Key_t, typename Value_t> 67IntervalMap<Key_t, Value_t>::IntervalMap () 68{ 69 entries = 0; 70 nchunks = 0; 71 chunks = NULL; 72 index = new Vector<Entry*>; 73} 74 75template <typename Key_t, typename Value_t> 76IntervalMap<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 84template <typename Key_t, typename Value_t> 85void 86IntervalMap<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 126template <typename Key_t, typename Value_t> 127Value_t 128IntervalMap<Key_t, Value_t>::get (Key_t key) 129{ 130 return get (key, Map<Key_t, Value_t>::REL_EQ); 131} 132 133template <typename Key_t, typename Value_t> 134Value_t 135IntervalMap<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 184template <typename Key_t, typename Value_t> 185Value_t 186IntervalMap<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 195