gcc/objc/objc-map.c

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