]>
Commit | Line | Data |
---|---|---|
3cc2dd4b | 1 | /* objc-map.c -- Implementation of map data structures for ObjC compiler |
8d9254fc | 2 | Copyright (C) 2011-2020 Free Software Foundation, Inc. |
3cc2dd4b NP |
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" | |
2adfab87 | 23 | #include "tree.h" |
3cc2dd4b NP |
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 | { | |
766090c2 | 58 | objc_map_t map = ggc_cleared_alloc<objc_map_private> (); |
3cc2dd4b NP |
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 | ||
766090c2 TS |
69 | map->slots = ggc_cleared_vec_alloc<tree> (initial_capacity); |
70 | map->values = ggc_cleared_vec_alloc<tree> (initial_capacity); | |
3cc2dd4b NP |
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 (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 | ||
766090c2 TS |
114 | map->slots = ggc_cleared_vec_alloc<tree> (map->number_of_slots); |
115 | map->values = ggc_cleared_vec_alloc<tree> (map->number_of_slots); | |
3cc2dd4b NP |
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, map->number_of_slots * 2); | |
158 | } | |
159 | ||
160 | #include "gt-objc-objc-map.h" |