1 | /* objc-map.cc -- Implementation of map data structures for ObjC compiler |
2 | Copyright (C) 2011-2024 Free Software Foundation, Inc. |
3 | Written by Nicola Pero <nicola.pero@meta-innovation.com> |
4 | |
5 | This program is free software; you can redistribute it and/or modify it |
6 | under the terms of the GNU Lesser Public License as published by the |
7 | Free Software Foundation; either version 3, or (at your option) any |
8 | later version. |
9 | |
10 | This program is distributed in the hope that it will be useful, |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
13 | GNU Lesser Public License for more details. |
14 | |
15 | You should have received a copy of the GNU Lesser Public License |
16 | along with this program; if not, write to the Free Software |
17 | Foundation, 51 Franklin Street - Fifth Floor, |
18 | Boston, 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 | |
28 | static |
29 | size_t |
30 | ATTRIBUTE_PURE |
31 | next_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 | |
55 | objc_map_t |
56 | objc_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 (x: 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> (c: initial_capacity); |
70 | map->values = ggc_cleared_vec_alloc<tree> (c: 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 | |
81 | void |
82 | objc_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 | |
91 | int |
92 | objc_map_maximum_load_factor (objc_map_t map) |
93 | { |
94 | return map->maximum_load_factor; |
95 | } |
96 | |
97 | static void |
98 | objc_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 (x: 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> (c: map->number_of_slots); |
115 | map->values = ggc_cleared_vec_alloc<tree> (c: 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 | |
154 | void |
155 | objc_map_private_grow (struct objc_map_private *map) |
156 | { |
157 | objc_map_private_resize (map, new_number_of_slots: map->number_of_slots * 2); |
158 | } |
159 | |
160 | #include "gt-objc-objc-map.h" |
161 | |