1 /* objc-map.c -- Implementation of map data structures for ObjC compiler
2 Copyright (C) 2011-2013 Free Software Foundation, Inc.
3 Written by Nicola Pero <nicola.pero@meta-innovation.com>
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
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.
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. */
22 #include "coretypes.h"
27 #define OUT_OF_MEMORY { fprintf (stderr, "Out of memory\n"); abort (); }
32 next_power_of_two (size_t x
)
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
43 if ((x
& (x
- 1)) == 0)
46 /* Calculate log_2 by counting how many times we can divide by 2
57 objc_map_alloc_ggc (size_t initial_capacity
)
59 objc_map_t map
= (objc_map_t
) ggc_internal_cleared_vec_alloc (1, sizeof (struct objc_map_private
));
63 initial_capacity
= next_power_of_two (initial_capacity
);
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;
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
));
73 if (map
->slots
== NULL
)
76 if (map
->values
== NULL
)
83 objc_map_set_maximum_load_factor (objc_map_t map
, int number_between_zero_and_one_hundred
)
85 if (map
->number_of_non_empty_slots
!= 0)
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;
93 objc_map_maximum_load_factor (objc_map_t map
)
95 return map
->maximum_load_factor
;
99 objc_map_private_resize (objc_map_t map
, size_t new_number_of_slots
)
101 tree
*old_slots
= map
->slots
;
102 tree
*old_values
= map
->values
;
103 size_t i
, old_number_of_slots
= map
->number_of_slots
;
105 if (new_number_of_slots
< (map
->number_of_non_empty_slots
))
106 new_number_of_slots
= 2 * map
->number_of_non_empty_slots
;
108 new_number_of_slots
= next_power_of_two (new_number_of_slots
);
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;
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
));
118 if (map
->slots
== NULL
)
121 if (map
->values
== NULL
)
124 for (i
= 0; i
< old_number_of_slots
; i
++)
125 if (old_slots
[i
] != OBJC_MAP_PRIVATE_EMPTY_SLOT
)
127 size_t k
= IDENTIFIER_HASH_VALUE (old_slots
[i
]) & map
->mask
;
129 if (map
->slots
[k
] == OBJC_MAP_PRIVATE_EMPTY_SLOT
)
131 map
->slots
[k
] = old_slots
[i
];
132 map
->values
[k
] = old_values
[i
];
139 k
= (k
+ j
) & map
->mask
;
140 if (map
->slots
[k
] == OBJC_MAP_PRIVATE_EMPTY_SLOT
)
142 map
->slots
[k
] = old_slots
[i
];
143 map
->values
[k
] = old_values
[i
];
151 ggc_free (old_slots
);
152 ggc_free (old_values
);
156 objc_map_private_grow (struct objc_map_private
*map
)
158 objc_map_private_resize (map
, map
->number_of_slots
* 2);
161 #include "gt-objc-objc-map.h"