1/* objc-map.cc -- Implementation of map data structures for ObjC compiler 2 Copyright (C) 2011-2022 Free Software Foundation, Inc. 3 Written by Nicola Pero <nicola.pero@meta-innovation.com> 4 5This program is free software; you can redistribute it and/or modify it 6under the terms of the GNU Lesser Public License as published by the 7Free Software Foundation; either version 3, or (at your option) any 8later version. 9 10This program is distributed in the hope that it will be useful, 11but WITHOUT ANY WARRANTY; without even the implied warranty of 12MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13GNU Lesser Public License for more details. 14 15You should have received a copy of the GNU Lesser Public License 16along with this program; if not, write to the Free Software 17Foundation, 51 Franklin Street - Fifth Floor, 18Boston, MA 02110-1301, USA. */ 19 20#include "config.h" 21#include "system.h" 22#include "coretypes.h" 23#include "tree.h" 24#include "objc-map.h" 25 26#define OUT_OF_MEMORY { fprintf (stderr, "Out of memory\n"); abort (); } 27 28static 29size_t 30ATTRIBUTE_PURE 31next_power_of_two (size_t x) 32{ 33 size_t result = 1; 34 35 if (x < 2) 36 return 2; 37 38 /* Avoid the long calculation if x is already a power of two. Since 39 we internally always increase/shrink tables by powers of 2, the 40 calculation should only be done once, when the table is first 41 set up. */ 42 if ((x & (x - 1)) == 0) 43 return x; 44 45 /* Calculate log_2 by counting how many times we can divide by 2 46 before reaching 0. */ 47 while (x > 0) 48 { 49 x = x >> 1; 50 result = result << 1; 51 } 52 return result; 53} 54 55objc_map_t 56objc_map_alloc_ggc (size_t initial_capacity) 57{ 58 objc_map_t map = ggc_cleared_alloc<objc_map_private> (); 59 if (map == NULL) 60 OUT_OF_MEMORY; 61 62 initial_capacity = next_power_of_two (initial_capacity); 63 64 map->number_of_slots = initial_capacity; 65 map->mask = initial_capacity - 1; 66 map->maximum_load_factor = 70; 67 map->max_number_of_non_empty_slots = (initial_capacity * map->maximum_load_factor) / 100; 68 69 map->slots = ggc_cleared_vec_alloc<tree> (initial_capacity); 70 map->values = ggc_cleared_vec_alloc<tree> (initial_capacity); 71 72 if (map->slots == NULL) 73 OUT_OF_MEMORY; 74 75 if (map->values == NULL) 76 OUT_OF_MEMORY; 77 78 return map; 79} 80 81void 82objc_map_set_maximum_load_factor (objc_map_t map, int number_between_zero_and_one_hundred) 83{ 84 if (map->number_of_non_empty_slots != 0) 85 return; 86 87 map->maximum_load_factor = number_between_zero_and_one_hundred; 88 map->max_number_of_non_empty_slots = (map->number_of_slots * number_between_zero_and_one_hundred) / 100; 89} 90 91int 92objc_map_maximum_load_factor (objc_map_t map) 93{ 94 return map->maximum_load_factor; 95} 96 97static void 98objc_map_private_resize (objc_map_t map, size_t new_number_of_slots) 99{ 100 tree *old_slots = map->slots; 101 tree *old_values = map->values; 102 size_t i, old_number_of_slots = map->number_of_slots; 103 104 if (new_number_of_slots < (map->number_of_non_empty_slots)) 105 new_number_of_slots = 2 * map->number_of_non_empty_slots; 106 107 new_number_of_slots = next_power_of_two (new_number_of_slots); 108 109 map->number_of_slots = new_number_of_slots; 110 map->mask = map->number_of_slots - 1; 111 map->max_number_of_non_empty_slots = (map->number_of_slots * map->maximum_load_factor) / 100; 112 113 114 map->slots = ggc_cleared_vec_alloc<tree> (map->number_of_slots); 115 map->values = ggc_cleared_vec_alloc<tree> (map->number_of_slots); 116 117 if (map->slots == NULL) 118 OUT_OF_MEMORY; 119 120 if (map->values == NULL) 121 OUT_OF_MEMORY; 122 123 for (i = 0; i < old_number_of_slots; i++) 124 if (old_slots[i] != OBJC_MAP_PRIVATE_EMPTY_SLOT) 125 { 126 size_t k = IDENTIFIER_HASH_VALUE (old_slots[i]) & map->mask; 127 128 if (map->slots[k] == OBJC_MAP_PRIVATE_EMPTY_SLOT) 129 { 130 map->slots[k] = old_slots[i]; 131 map->values[k] = old_values[i]; 132 } 133 else 134 { 135 size_t j = 1; 136 while (1) 137 { 138 k = (k + j) & map->mask; 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 break; 144 } 145 j++; 146 } 147 } 148 } 149 150 ggc_free (old_slots); 151 ggc_free (old_values); 152} 153 154void 155objc_map_private_grow (struct objc_map_private *map) 156{ 157 objc_map_private_resize (map, map->number_of_slots * 2); 158} 159 160#include "gt-objc-objc-map.h" 161