1/* objc-map.cc -- Implementation of map data structures for ObjC compiler
2   Copyright (C) 2011-2022 Free Software Foundation, Inc.
3   Written by Nicola Pero <nicola.pero@meta-innovation.com>
4
5This program is free software; you can redistribute it and/or modify it
6under the terms of the GNU Lesser Public License as published by the
7Free Software Foundation; either version 3, or (at your option) any
8later version.
9
10This program is distributed in the hope that it will be useful,
11but WITHOUT ANY WARRANTY; without even the implied warranty of
12MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13GNU Lesser Public License for more details.
14
15You should have received a copy of the GNU Lesser Public License
16along with this program; if not, write to the Free Software
17Foundation, 51 Franklin Street - Fifth Floor,
18Boston, MA 02110-1301, USA.  */
19
20#include "config.h"
21#include "system.h"
22#include "coretypes.h"
23#include "tree.h"
24#include "objc-map.h"
25
26#define OUT_OF_MEMORY { fprintf (stderr, "Out of memory\n"); abort (); }
27
28static
29size_t
30ATTRIBUTE_PURE
31next_power_of_two (size_t x)
32{
33  size_t result = 1;
34
35  if (x < 2)
36    return 2;
37
38  /* Avoid the long calculation if x is already a power of two.  Since
39     we internally always increase/shrink tables by powers of 2, the
40     calculation should only be done once, when the table is first
41     set up.  */
42  if ((x & (x - 1)) == 0)
43    return x;
44
45  /* Calculate log_2 by counting how many times we can divide by 2
46     before reaching 0.  */
47  while (x > 0)
48    {
49      x = x >> 1;
50      result = result << 1;
51    }
52  return result;
53}
54
55objc_map_t
56objc_map_alloc_ggc (size_t initial_capacity)
57{
58  objc_map_t map = ggc_cleared_alloc<objc_map_private> ();
59  if (map == NULL)
60    OUT_OF_MEMORY;
61
62  initial_capacity = next_power_of_two (initial_capacity);
63
64  map->number_of_slots = initial_capacity;
65  map->mask = initial_capacity - 1;
66  map->maximum_load_factor = 70;
67  map->max_number_of_non_empty_slots = (initial_capacity * map->maximum_load_factor) / 100;
68
69  map->slots = ggc_cleared_vec_alloc<tree> (initial_capacity);
70  map->values = ggc_cleared_vec_alloc<tree> (initial_capacity);
71
72  if (map->slots == NULL)
73    OUT_OF_MEMORY;
74
75  if (map->values == NULL)
76    OUT_OF_MEMORY;
77
78  return map;
79}
80
81void
82objc_map_set_maximum_load_factor (objc_map_t map, int number_between_zero_and_one_hundred)
83{
84  if (map->number_of_non_empty_slots != 0)
85    return;
86
87  map->maximum_load_factor = number_between_zero_and_one_hundred;
88  map->max_number_of_non_empty_slots = (map->number_of_slots * number_between_zero_and_one_hundred) / 100;
89}
90
91int
92objc_map_maximum_load_factor (objc_map_t map)
93{
94  return map->maximum_load_factor;
95}
96
97static void
98objc_map_private_resize (objc_map_t map, size_t new_number_of_slots)
99{
100  tree *old_slots = map->slots;
101  tree *old_values = map->values;
102  size_t i, old_number_of_slots = map->number_of_slots;
103
104  if (new_number_of_slots < (map->number_of_non_empty_slots))
105    new_number_of_slots = 2 * map->number_of_non_empty_slots;
106
107  new_number_of_slots = next_power_of_two (new_number_of_slots);
108
109  map->number_of_slots = new_number_of_slots;
110  map->mask = map->number_of_slots - 1;
111  map->max_number_of_non_empty_slots = (map->number_of_slots * map->maximum_load_factor) / 100;
112
113
114  map->slots = ggc_cleared_vec_alloc<tree> (map->number_of_slots);
115  map->values = ggc_cleared_vec_alloc<tree> (map->number_of_slots);
116
117  if (map->slots == NULL)
118    OUT_OF_MEMORY;
119
120  if (map->values == NULL)
121    OUT_OF_MEMORY;
122
123  for (i = 0; i < old_number_of_slots; i++)
124    if (old_slots[i] != OBJC_MAP_PRIVATE_EMPTY_SLOT)
125      {
126	size_t k = IDENTIFIER_HASH_VALUE (old_slots[i]) & map->mask;
127
128	if (map->slots[k] == OBJC_MAP_PRIVATE_EMPTY_SLOT)
129	  {
130	    map->slots[k] = old_slots[i];
131	    map->values[k] = old_values[i];
132	  }
133	else
134	  {
135	    size_t j = 1;
136	    while (1)
137	      {
138		k = (k + j) & map->mask;
139		if (map->slots[k] == OBJC_MAP_PRIVATE_EMPTY_SLOT)
140		  {
141		    map->slots[k] = old_slots[i];
142		    map->values[k] = old_values[i];
143		    break;
144		  }
145		j++;
146	      }
147	  }
148      }
149
150  ggc_free (old_slots);
151  ggc_free (old_values);
152}
153
154void
155objc_map_private_grow (struct objc_map_private *map)
156{
157  objc_map_private_resize (map, map->number_of_slots * 2);
158}
159
160#include "gt-objc-objc-map.h"
161