/* objc-map.c -- Implementation of map data structures for ObjC compiler
|
/* objc-map.c -- Implementation of map data structures for ObjC compiler
|
Copyright 2011 Free Software Foundation, Inc.
|
Copyright 2011 Free Software Foundation, Inc.
|
Written by Nicola Pero <nicola.pero@meta-innovation.com>
|
Written by Nicola Pero <nicola.pero@meta-innovation.com>
|
|
|
This program is free software; you can redistribute it and/or modify it
|
This program is free software; you can redistribute it and/or modify it
|
under the terms of the GNU Lesser Public License as published by the
|
under the terms of the GNU Lesser Public License as published by the
|
Free Software Foundation; either version 3, or (at your option) any
|
Free Software Foundation; either version 3, or (at your option) any
|
later version.
|
later version.
|
|
|
This program is distributed in the hope that it will be useful,
|
This program is distributed in the hope that it will be useful,
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
GNU Lesser Public License for more details.
|
GNU Lesser Public License for more details.
|
|
|
You should have received a copy of the GNU Lesser Public License
|
You should have received a copy of the GNU Lesser Public License
|
along with this program; if not, write to the Free Software
|
along with this program; if not, write to the Free Software
|
Foundation, 51 Franklin Street - Fifth Floor,
|
Foundation, 51 Franklin Street - Fifth Floor,
|
Boston, MA 02110-1301, USA. */
|
Boston, MA 02110-1301, USA. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tree.h"
|
#include "tree.h"
|
#include "ggc.h"
|
#include "ggc.h"
|
#include "objc-map.h"
|
#include "objc-map.h"
|
|
|
#define OUT_OF_MEMORY { fprintf (stderr, "Out of memory\n"); abort (); }
|
#define OUT_OF_MEMORY { fprintf (stderr, "Out of memory\n"); abort (); }
|
|
|
static
|
static
|
size_t
|
size_t
|
ATTRIBUTE_PURE
|
ATTRIBUTE_PURE
|
next_power_of_two (size_t x)
|
next_power_of_two (size_t x)
|
{
|
{
|
size_t result = 1;
|
size_t result = 1;
|
|
|
if (x < 2)
|
if (x < 2)
|
return 2;
|
return 2;
|
|
|
/* Avoid the long calculation if x is already a power of two. Since
|
/* Avoid the long calculation if x is already a power of two. Since
|
we internally always increase/shrink tables by powers of 2, the
|
we internally always increase/shrink tables by powers of 2, the
|
calculation should only be done once, when the table is first
|
calculation should only be done once, when the table is first
|
set up. */
|
set up. */
|
if ((x & (x - 1)) == 0)
|
if ((x & (x - 1)) == 0)
|
return x;
|
return x;
|
|
|
/* Calculate log_2 by counting how many times we can divide by 2
|
/* Calculate log_2 by counting how many times we can divide by 2
|
before reaching 0. */
|
before reaching 0. */
|
while (x > 0)
|
while (x > 0)
|
{
|
{
|
x = x >> 1;
|
x = x >> 1;
|
result = result << 1;
|
result = result << 1;
|
}
|
}
|
return result;
|
return result;
|
}
|
}
|
|
|
objc_map_t
|
objc_map_t
|
objc_map_alloc_ggc (size_t initial_capacity)
|
objc_map_alloc_ggc (size_t initial_capacity)
|
{
|
{
|
objc_map_t map = (objc_map_t) ggc_internal_cleared_vec_alloc_stat (1, sizeof (struct objc_map_private));
|
objc_map_t map = (objc_map_t) ggc_internal_cleared_vec_alloc_stat (1, sizeof (struct objc_map_private));
|
if (map == NULL)
|
if (map == NULL)
|
OUT_OF_MEMORY;
|
OUT_OF_MEMORY;
|
|
|
initial_capacity = next_power_of_two (initial_capacity);
|
initial_capacity = next_power_of_two (initial_capacity);
|
|
|
map->number_of_slots = initial_capacity;
|
map->number_of_slots = initial_capacity;
|
map->mask = initial_capacity - 1;
|
map->mask = initial_capacity - 1;
|
map->maximum_load_factor = 70;
|
map->maximum_load_factor = 70;
|
map->max_number_of_non_empty_slots = (initial_capacity * map->maximum_load_factor) / 100;
|
map->max_number_of_non_empty_slots = (initial_capacity * map->maximum_load_factor) / 100;
|
|
|
map->slots = (tree *)ggc_internal_cleared_vec_alloc_stat (initial_capacity, sizeof (tree));
|
map->slots = (tree *)ggc_internal_cleared_vec_alloc_stat (initial_capacity, sizeof (tree));
|
map->values = (tree *)ggc_internal_cleared_vec_alloc_stat (initial_capacity, sizeof (tree));
|
map->values = (tree *)ggc_internal_cleared_vec_alloc_stat (initial_capacity, sizeof (tree));
|
|
|
if (map->slots == NULL)
|
if (map->slots == NULL)
|
OUT_OF_MEMORY;
|
OUT_OF_MEMORY;
|
|
|
if (map->values == NULL)
|
if (map->values == NULL)
|
OUT_OF_MEMORY;
|
OUT_OF_MEMORY;
|
|
|
return map;
|
return map;
|
}
|
}
|
|
|
void
|
void
|
objc_map_set_maximum_load_factor (objc_map_t map, int number_between_zero_and_one_hundred)
|
objc_map_set_maximum_load_factor (objc_map_t map, int number_between_zero_and_one_hundred)
|
{
|
{
|
if (map->number_of_non_empty_slots != 0)
|
if (map->number_of_non_empty_slots != 0)
|
return;
|
return;
|
|
|
map->maximum_load_factor = number_between_zero_and_one_hundred;
|
map->maximum_load_factor = number_between_zero_and_one_hundred;
|
map->max_number_of_non_empty_slots = (map->number_of_slots * number_between_zero_and_one_hundred) / 100;
|
map->max_number_of_non_empty_slots = (map->number_of_slots * number_between_zero_and_one_hundred) / 100;
|
}
|
}
|
|
|
int
|
int
|
objc_map_maximum_load_factor (objc_map_t map)
|
objc_map_maximum_load_factor (objc_map_t map)
|
{
|
{
|
return map->maximum_load_factor;
|
return map->maximum_load_factor;
|
}
|
}
|
|
|
static void
|
static void
|
objc_map_private_resize (objc_map_t map, size_t new_number_of_slots)
|
objc_map_private_resize (objc_map_t map, size_t new_number_of_slots)
|
{
|
{
|
tree *old_slots = map->slots;
|
tree *old_slots = map->slots;
|
tree *old_values = map->values;
|
tree *old_values = map->values;
|
size_t i, old_number_of_slots = map->number_of_slots;
|
size_t i, old_number_of_slots = map->number_of_slots;
|
|
|
if (new_number_of_slots < (map->number_of_non_empty_slots))
|
if (new_number_of_slots < (map->number_of_non_empty_slots))
|
new_number_of_slots = 2 * map->number_of_non_empty_slots;
|
new_number_of_slots = 2 * map->number_of_non_empty_slots;
|
|
|
new_number_of_slots = next_power_of_two (new_number_of_slots);
|
new_number_of_slots = next_power_of_two (new_number_of_slots);
|
|
|
map->number_of_slots = new_number_of_slots;
|
map->number_of_slots = new_number_of_slots;
|
map->mask = map->number_of_slots - 1;
|
map->mask = map->number_of_slots - 1;
|
map->max_number_of_non_empty_slots = (map->number_of_slots * map->maximum_load_factor) / 100;
|
map->max_number_of_non_empty_slots = (map->number_of_slots * map->maximum_load_factor) / 100;
|
|
|
|
|
map->slots = (tree *)ggc_internal_cleared_vec_alloc_stat (map->number_of_slots, sizeof (tree));
|
map->slots = (tree *)ggc_internal_cleared_vec_alloc_stat (map->number_of_slots, sizeof (tree));
|
map->values = (tree *)ggc_internal_cleared_vec_alloc_stat (map->number_of_slots, sizeof (tree));
|
map->values = (tree *)ggc_internal_cleared_vec_alloc_stat (map->number_of_slots, sizeof (tree));
|
|
|
if (map->slots == NULL)
|
if (map->slots == NULL)
|
OUT_OF_MEMORY;
|
OUT_OF_MEMORY;
|
|
|
if (map->values == NULL)
|
if (map->values == NULL)
|
OUT_OF_MEMORY;
|
OUT_OF_MEMORY;
|
|
|
for (i = 0; i < old_number_of_slots; i++)
|
for (i = 0; i < old_number_of_slots; i++)
|
if (old_slots[i] != OBJC_MAP_PRIVATE_EMPTY_SLOT)
|
if (old_slots[i] != OBJC_MAP_PRIVATE_EMPTY_SLOT)
|
{
|
{
|
size_t k = IDENTIFIER_HASH_VALUE (old_slots[i]) & map->mask;
|
size_t k = IDENTIFIER_HASH_VALUE (old_slots[i]) & map->mask;
|
|
|
if (map->slots[k] == OBJC_MAP_PRIVATE_EMPTY_SLOT)
|
if (map->slots[k] == OBJC_MAP_PRIVATE_EMPTY_SLOT)
|
{
|
{
|
map->slots[k] = old_slots[i];
|
map->slots[k] = old_slots[i];
|
map->values[k] = old_values[i];
|
map->values[k] = old_values[i];
|
}
|
}
|
else
|
else
|
{
|
{
|
size_t j = 1;
|
size_t j = 1;
|
while (1)
|
while (1)
|
{
|
{
|
k = (k + j) & map->mask;
|
k = (k + j) & map->mask;
|
if (map->slots[k] == OBJC_MAP_PRIVATE_EMPTY_SLOT)
|
if (map->slots[k] == OBJC_MAP_PRIVATE_EMPTY_SLOT)
|
{
|
{
|
map->slots[k] = old_slots[i];
|
map->slots[k] = old_slots[i];
|
map->values[k] = old_values[i];
|
map->values[k] = old_values[i];
|
break;
|
break;
|
}
|
}
|
j++;
|
j++;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
ggc_free (old_slots);
|
ggc_free (old_slots);
|
ggc_free (old_values);
|
ggc_free (old_values);
|
}
|
}
|
|
|
void
|
void
|
objc_map_private_grow (struct objc_map_private *map)
|
objc_map_private_grow (struct objc_map_private *map)
|
{
|
{
|
objc_map_private_resize (map, map->number_of_slots * 2);
|
objc_map_private_resize (map, map->number_of_slots * 2);
|
}
|
}
|
|
|
#include "gt-objc-objc-map.h"
|
#include "gt-objc-objc-map.h"
|
|
|
