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"