Home | History | Annotate | Line # | Download | only in objc 
      1 /* objc-map.cc -- Implementation of map data structures for ObjC compiler
      2    Copyright (C) 2011-2022 Free Software Foundation, Inc.
      3    Written by Nicola Pero <nicola.pero (at) 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"
    161