Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / objc / objc-map.c
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"