1 /* objc-map.c -- Implementation of map data structures for ObjC compiler 2 Copyright 2011 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 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 57 objc_map_alloc_ggc (size_t initial_capacity) 58 { 59 objc_map_t map = (objc_map_t) ggc_internal_cleared_vec_alloc_stat (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_stat (initial_capacity, sizeof (tree)); 71 map->values = (tree *)ggc_internal_cleared_vec_alloc_stat (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 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 93 objc_map_maximum_load_factor (objc_map_t map) 94 { 95 return map->maximum_load_factor; 96 } 97 98 static void 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_stat (map->number_of_slots, sizeof (tree)); 116 map->values = (tree *)ggc_internal_cleared_vec_alloc_stat (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 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