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 *  Cache Map implementation.
23 *
24 *  Cache Map makes the following assumptions:
25 *    - Cache Map is used for very fast but not guaranteed mapping;
26 *    - only REL_EQ Relation can be used;
27 *    - all objects used as keys or values has to be managed
28 *      outside CacheMap (f.e. deletion);
29 *    - (Key_t)0 is invalid key;
30 *    - (Value_t)0 is invalid value;
31 *    - <TBC>
32 */
33
34#ifndef _DBE_CACHEMAP_H
35#define _DBE_CACHEMAP_H
36
37#include <assert.h>
38#include <vec.h>
39#include <Map.h>
40
41template <typename Key_t, typename Value_t>
42class CacheMap : public Map<Key_t, Value_t>
43{
44public:
45
46  CacheMap ();
47  ~CacheMap ();
48  void put (Key_t key, Value_t val);
49  Value_t get (Key_t key);
50  Value_t get (Key_t key, typename Map<Key_t, Value_t>::Relation rel);
51  Value_t
52  remove (Key_t key);
53
54private:
55
56  struct Entry
57  {
58    Key_t key;
59    Value_t val;
60
61    Entry ()
62    {
63      key = (Key_t) 0;
64    }
65  };
66
67  static const int INIT_SIZE;
68  static const int MAX_SIZE;
69
70  static unsigned hash (Key_t key);
71  Entry *getEntry (Key_t key);
72
73  int cursize;
74  int nputs;
75  int nchunks;
76  Entry **chunks;
77};
78
79template <typename Key_t, typename Value_t>
80const int CacheMap<Key_t, Value_t>::INIT_SIZE = 1 << 14;
81template <typename Key_t, typename Value_t>
82const int CacheMap<Key_t, Value_t>::MAX_SIZE = 1 << 20;
83
84template <typename Key_t, typename Value_t>CacheMap<Key_t, Value_t>
85::CacheMap ()
86{
87  cursize = INIT_SIZE;
88  chunks = new Entry*[32];
89  nchunks = 0;
90  chunks[nchunks++] = new Entry[cursize];
91  nputs = 0;
92}
93
94template <typename Key_t, typename Value_t>
95CacheMap<Key_t, Value_t>::~CacheMap ()
96{
97  for (int i = 0; i < nchunks; i++)
98    delete[] chunks[i];
99  delete[] chunks;
100}
101
102template <typename Key_t, typename Value_t>
103unsigned
104CacheMap<Key_t, Value_t>::hash (Key_t key)
105{
106  unsigned h = (unsigned) key ^ (unsigned) (key >> 32);
107  h ^= (h >> 20) ^ (h >> 12);
108  return h ^ (h >> 7) ^ (h >> 4);
109}
110
111template <typename Key_t, typename Value_t>
112void
113CacheMap<Key_t, Value_t>::put (Key_t key, Value_t val)
114{
115  if (nputs >= cursize && cursize < MAX_SIZE)
116    {
117      // Allocate new chunk for entries.
118      chunks[nchunks++] = new Entry[cursize];
119      cursize *= 2;
120
121      // Copy all old entries to the newly allocated chunk
122      Entry *newchunk = chunks[nchunks - 1];
123      int prevsz = 0;
124      int nextsz = INIT_SIZE;
125      for (int i = 0; i < nchunks - 1; i++)
126	{
127	  Entry *oldchunk = chunks[i];
128	  for (int j = prevsz; j < nextsz; j++)
129	    newchunk[j] = oldchunk[j - prevsz];
130	  prevsz = nextsz;
131	  nextsz *= 2;
132	}
133    }
134  Entry *entry = getEntry (key);
135  entry->key = key;
136  entry->val = val;
137  nputs++;
138}
139
140template <typename Key_t, typename Value_t>
141typename CacheMap<Key_t, Value_t>::Entry *
142CacheMap<Key_t, Value_t>::getEntry (Key_t key)
143{
144  unsigned idx = hash (key);
145  int i = nchunks - 1;
146  int j = cursize / 2;
147  for (; i > 0; i -= 1, j /= 2)
148    if (idx & j)
149      break;
150  if (i == 0)
151    j *= 2;
152  return &chunks[i][idx & (j - 1)];
153}
154
155template <typename Key_t, typename Value_t>
156Value_t
157CacheMap<Key_t, Value_t>::get (Key_t key)
158{
159  Entry *entry = getEntry (key);
160  return entry->key == key ? entry->val : (Value_t) 0;
161}
162
163template <typename Key_t, typename Value_t>
164Value_t
165CacheMap<Key_t, Value_t>::get (Key_t key, typename Map<Key_t, Value_t>::Relation rel)
166{
167  if (rel != Map<Key_t, Value_t>::REL_EQ)
168    return (Value_t) 0;
169  return get (key);
170}
171
172template <typename Key_t, typename Value_t>
173Value_t
174CacheMap<Key_t, Value_t>::remove (Key_t key)
175{
176  Entry *entry = getEntry (key);
177  Value_t res = (Value_t) 0;
178  if (entry->key == key)
179    {
180      res = entry->val;
181      entry->val = (Value_t) 0;
182    }
183  return res;
184}
185
186#endif
187