1 /* objc-map.c -- Implementation of map data structures for ObjC compiler
2 Copyright (C) 2011-2015 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"
28 #define OUT_OF_MEMORY { fprintf (stderr, "Out of memory\n"); abort (); }
33 next_power_of_two (size_t x
)
40 /* Avoid the long calculation if x is already a power of two. Since
41 we internally always increase/shrink tables by powers of 2, the
42 calculation should only be done once, when the table is first
44 if ((x
& (x
- 1)) == 0)
47 /* Calculate log_2 by counting how many times we can divide by 2
58 objc_map_alloc_ggc (size_t initial_capacity
)
60 objc_map_t map
= ggc_cleared_alloc
<objc_map_private
> ();
64 initial_capacity
= next_power_of_two (initial_capacity
);
66 map
->number_of_slots
= initial_capacity
;
67 map
->mask
= initial_capacity
- 1;
68 map
->maximum_load_factor
= 70;
69 map
->max_number_of_non_empty_slots
= (initial_capacity
* map
->maximum_load_factor
) / 100;
71 map
->slots
= ggc_cleared_vec_alloc
<tree
> (initial_capacity
);
72 map
->values
= ggc_cleared_vec_alloc
<tree
> (initial_capacity
);
74 if (map
->slots
== NULL
)
77 if (map
->values
== NULL
)
84 objc_map_set_maximum_load_factor (objc_map_t map
, int number_between_zero_and_one_hundred
)
86 if (map
->number_of_non_empty_slots
!= 0)
89 map
->maximum_load_factor
= number_between_zero_and_one_hundred
;
90 map
->max_number_of_non_empty_slots
= (map
->number_of_slots
* number_between_zero_and_one_hundred
) / 100;
94 objc_map_maximum_load_factor (objc_map_t map
)
96 return map
->maximum_load_factor
;
100 objc_map_private_resize (objc_map_t map
, size_t new_number_of_slots
)
102 tree
*old_slots
= map
->slots
;
103 tree
*old_values
= map
->values
;
104 size_t i
, old_number_of_slots
= map
->number_of_slots
;
106 if (new_number_of_slots
< (map
->number_of_non_empty_slots
))
107 new_number_of_slots
= 2 * map
->number_of_non_empty_slots
;
109 new_number_of_slots
= next_power_of_two (new_number_of_slots
);
111 map
->number_of_slots
= new_number_of_slots
;
112 map
->mask
= map
->number_of_slots
- 1;
113 map
->max_number_of_non_empty_slots
= (map
->number_of_slots
* map
->maximum_load_factor
) / 100;
116 map
->slots
= ggc_cleared_vec_alloc
<tree
> (map
->number_of_slots
);
117 map
->values
= ggc_cleared_vec_alloc
<tree
> (map
->number_of_slots
);
119 if (map
->slots
== NULL
)
122 if (map
->values
== NULL
)
125 for (i
= 0; i
< old_number_of_slots
; i
++)
126 if (old_slots
[i
] != OBJC_MAP_PRIVATE_EMPTY_SLOT
)
128 size_t k
= IDENTIFIER_HASH_VALUE (old_slots
[i
]) & map
->mask
;
130 if (map
->slots
[k
] == OBJC_MAP_PRIVATE_EMPTY_SLOT
)
132 map
->slots
[k
] = old_slots
[i
];
133 map
->values
[k
] = old_values
[i
];
140 k
= (k
+ j
) & map
->mask
;
141 if (map
->slots
[k
] == OBJC_MAP_PRIVATE_EMPTY_SLOT
)
143 map
->slots
[k
] = old_slots
[i
];
144 map
->values
[k
] = old_values
[i
];
152 ggc_free (old_slots
);
153 ggc_free (old_values
);
157 objc_map_private_grow (struct objc_map_private
*map
)
159 objc_map_private_resize (map
, map
->number_of_slots
* 2);
162 #include "gt-objc-objc-map.h"