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 *	String Map implementation.
23 */
24
25#ifndef _DBE_STRINGMAP_H
26#define _DBE_STRINGMAP_H
27
28#include <assert.h>
29#include <vec.h>
30#include <Map.h>
31#include <util.h>
32
33template <typename Value_t>
34class StringMap : public Map<const char*, Value_t>
35{
36public:
37
38  StringMap (int htable_size = 1024, int chunk_size = 16384);
39  ~StringMap ();
40  void clear ();
41  void put (const char *key, Value_t val);
42  Value_t get (const char *key);
43  Value_t get (const char *key, typename Map<const char*, Value_t>::Relation rel);
44  Value_t remove (const char*);
45  Vector<const char*> *keySet ();
46  Vector<Value_t> *values ();
47
48private:
49
50  static unsigned
51  hash (const char *key)
52  {
53    return (unsigned) crc64 (key, strlen (key));
54  }
55
56  struct Entry
57  {
58    char *key;
59    Value_t val;
60  };
61
62  int CHUNK_SIZE, HTABLE_SIZE;
63  int entries;
64  int nchunks;
65  Entry **chunks;
66  Vector<Entry*> *index;
67  Entry **hashTable;
68};
69
70template <typename Value_t>
71StringMap<Value_t>::StringMap (int htable_size, int chunk_size)
72{
73  HTABLE_SIZE = htable_size;
74  CHUNK_SIZE = chunk_size;
75  entries = 0;
76  nchunks = 0;
77  chunks = NULL;
78  index = new Vector<Entry*>;
79  hashTable = new Entry*[HTABLE_SIZE];
80  for (int i = 0; i < HTABLE_SIZE; i++)
81    hashTable[i] = NULL;
82}
83
84template <typename Value_t>
85StringMap<Value_t>::~StringMap ()
86{
87  for (int i = 0; i < entries; ++i)
88    {
89      Entry *entry = index->fetch (i);
90      free (entry->key);
91    }
92  for (int i = 0; i < nchunks; i++)
93    delete[] chunks[i];
94  delete[] chunks;
95  delete index;
96  delete[] hashTable;
97}
98
99template <typename Value_t>
100void
101StringMap<Value_t>::clear ()
102{
103  for (int i = 0; i < entries; ++i)
104    {
105      Entry *entry = index->fetch (i);
106      free (entry->key);
107    }
108  entries = 0;
109  index->reset ();
110  for (int i = 0; i < HTABLE_SIZE; i++)
111    hashTable[i] = NULL;
112}
113
114template <typename Value_t>
115void
116StringMap<Value_t>::put (const char *key, Value_t val)
117{
118  unsigned idx = hash (key) % HTABLE_SIZE;
119  Entry *entry = hashTable[idx];
120  if (entry && strcmp (entry->key, key) == 0)
121    {
122      entry->val = val;
123      return;
124    }
125  int lo = 0;
126  int hi = entries - 1;
127  while (lo <= hi)
128    {
129      int md = (lo + hi) / 2;
130      entry = index->fetch (md);
131      int cmp = strcmp (entry->key, key);
132      if (cmp < 0)
133	lo = md + 1;
134      else if (cmp > 0)
135	hi = md - 1;
136      else
137	{
138	  entry->val = val;
139	  return;
140	}
141    }
142  if (entries >= nchunks * CHUNK_SIZE)
143    {
144      nchunks++;
145
146      // Reallocate Entry chunk array
147      Entry **new_chunks = new Entry*[nchunks];
148      for (int i = 0; i < nchunks - 1; i++)
149	new_chunks[i] = chunks[i];
150      delete[] chunks;
151      chunks = new_chunks;
152
153      // Allocate new chunk for entries.
154      chunks[nchunks - 1] = new Entry[CHUNK_SIZE];
155    }
156  entry = &chunks[entries / CHUNK_SIZE][entries % CHUNK_SIZE];
157  entry->key = strdup (key);
158  entry->val = val;
159  index->insert (lo, entry);
160  hashTable[idx] = entry;
161  entries++;
162}
163
164template <typename Value_t>
165Value_t
166StringMap<Value_t>::get (const char *key)
167{
168  unsigned idx = hash (key) % HTABLE_SIZE;
169  Entry *entry = hashTable[idx];
170  if (entry && strcmp (entry->key, key) == 0)
171    return entry->val;
172  int lo = 0;
173  int hi = entries - 1;
174  while (lo <= hi)
175    {
176      int md = (lo + hi) / 2;
177      entry = index->fetch (md);
178      int cmp = strcmp (entry->key, key);
179      if (cmp < 0)
180	lo = md + 1;
181      else if (cmp > 0)
182	hi = md - 1;
183      else
184	{
185	  hashTable[idx] = entry;
186	  return entry->val;
187	}
188    }
189  return (Value_t) 0;
190}
191
192template <typename Value_t>
193Value_t
194StringMap<Value_t>::get (const char *key, typename Map<const char*,
195			 Value_t>::Relation rel)
196{
197  if (rel != Map<const char*, Value_t>::REL_EQ)
198    return (Value_t) 0;
199  return get (key);
200}
201
202template <typename Value_t>
203Value_t
204StringMap<Value_t>::remove (const char*)
205{
206  // Not implemented
207  if (1)
208    assert (0);
209  return (Value_t) 0;
210}
211
212template <typename Value_t>
213Vector<Value_t> *
214StringMap<Value_t>::values ()
215{
216  Vector<Value_t> *vals = new Vector<Value_t>(entries);
217  for (int i = 0; i < entries; ++i)
218    {
219      Entry *entry = index->fetch (i);
220      vals->append (entry->val);
221    }
222  return vals;
223}
224
225template <typename Value_t>
226Vector<const char*> *
227StringMap<Value_t>::keySet ()
228{
229  Vector<const char*> *keys = new Vector<const char*>(entries);
230  for (int i = 0; i < entries; ++i)
231    {
232      Entry *entry = index->fetch (i);
233      keys->append (entry->key);
234    }
235  return keys;
236}
237
238#endif
239