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