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