gcc/objc/objc-map.c

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