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