1 /* objc-map.c -- Implementation of map data structures for ObjC compiler
2 Copyright (C) 2011-2014 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 "ggc.h"
25 #include "objc-map.h"
26
27 #define OUT_OF_MEMORY { fprintf (stderr, "Out of memory\n"); abort (); }
28
29 static
30 size_t
31 ATTRIBUTE_PURE
next_power_of_two(size_t x)32 next_power_of_two (size_t x)
33 {
34 size_t result = 1;
35
36 if (x < 2)
37 return 2;
38
39 /* Avoid the long calculation if x is already a power of two. Since
40 we internally always increase/shrink tables by powers of 2, the
41 calculation should only be done once, when the table is first
42 set up. */
43 if ((x & (x - 1)) == 0)
44 return x;
45
46 /* Calculate log_2 by counting how many times we can divide by 2
47 before reaching 0. */
48 while (x > 0)
49 {
50 x = x >> 1;
51 result = result << 1;
52 }
53 return result;
54 }
55
56 objc_map_t
objc_map_alloc_ggc(size_t initial_capacity)57 objc_map_alloc_ggc (size_t initial_capacity)
58 {
59 objc_map_t map = (objc_map_t) ggc_internal_cleared_vec_alloc (1, sizeof (struct objc_map_private));
60 if (map == NULL)
61 OUT_OF_MEMORY;
62
63 initial_capacity = next_power_of_two (initial_capacity);
64
65 map->number_of_slots = initial_capacity;
66 map->mask = initial_capacity - 1;
67 map->maximum_load_factor = 70;
68 map->max_number_of_non_empty_slots = (initial_capacity * map->maximum_load_factor) / 100;
69
70 map->slots = (tree *)ggc_internal_cleared_vec_alloc (initial_capacity, sizeof (tree));
71 map->values = (tree *)ggc_internal_cleared_vec_alloc (initial_capacity, sizeof (tree));
72
73 if (map->slots == NULL)
74 OUT_OF_MEMORY;
75
76 if (map->values == NULL)
77 OUT_OF_MEMORY;
78
79 return map;
80 }
81
82 void
objc_map_set_maximum_load_factor(objc_map_t map,int number_between_zero_and_one_hundred)83 objc_map_set_maximum_load_factor (objc_map_t map, int number_between_zero_and_one_hundred)
84 {
85 if (map->number_of_non_empty_slots != 0)
86 return;
87
88 map->maximum_load_factor = number_between_zero_and_one_hundred;
89 map->max_number_of_non_empty_slots = (map->number_of_slots * number_between_zero_and_one_hundred) / 100;
90 }
91
92 int
objc_map_maximum_load_factor(objc_map_t map)93 objc_map_maximum_load_factor (objc_map_t map)
94 {
95 return map->maximum_load_factor;
96 }
97
98 static void
objc_map_private_resize(objc_map_t map,size_t new_number_of_slots)99 objc_map_private_resize (objc_map_t map, size_t new_number_of_slots)
100 {
101 tree *old_slots = map->slots;
102 tree *old_values = map->values;
103 size_t i, old_number_of_slots = map->number_of_slots;
104
105 if (new_number_of_slots < (map->number_of_non_empty_slots))
106 new_number_of_slots = 2 * map->number_of_non_empty_slots;
107
108 new_number_of_slots = next_power_of_two (new_number_of_slots);
109
110 map->number_of_slots = new_number_of_slots;
111 map->mask = map->number_of_slots - 1;
112 map->max_number_of_non_empty_slots = (map->number_of_slots * map->maximum_load_factor) / 100;
113
114
115 map->slots = (tree *)ggc_internal_cleared_vec_alloc (map->number_of_slots, sizeof (tree));
116 map->values = (tree *)ggc_internal_cleared_vec_alloc (map->number_of_slots, sizeof (tree));
117
118 if (map->slots == NULL)
119 OUT_OF_MEMORY;
120
121 if (map->values == NULL)
122 OUT_OF_MEMORY;
123
124 for (i = 0; i < old_number_of_slots; i++)
125 if (old_slots[i] != OBJC_MAP_PRIVATE_EMPTY_SLOT)
126 {
127 size_t k = IDENTIFIER_HASH_VALUE (old_slots[i]) & map->mask;
128
129 if (map->slots[k] == OBJC_MAP_PRIVATE_EMPTY_SLOT)
130 {
131 map->slots[k] = old_slots[i];
132 map->values[k] = old_values[i];
133 }
134 else
135 {
136 size_t j = 1;
137 while (1)
138 {
139 k = (k + j) & map->mask;
140 if (map->slots[k] == OBJC_MAP_PRIVATE_EMPTY_SLOT)
141 {
142 map->slots[k] = old_slots[i];
143 map->values[k] = old_values[i];
144 break;
145 }
146 j++;
147 }
148 }
149 }
150
151 ggc_free (old_slots);
152 ggc_free (old_values);
153 }
154
155 void
objc_map_private_grow(struct objc_map_private * map)156 objc_map_private_grow (struct objc_map_private *map)
157 {
158 objc_map_private_resize (map, map->number_of_slots * 2);
159 }
160
161 #include "gt-objc-objc-map.h"
162