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