/* Set operations on pointers
- Copyright (C) 2004 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2006, 2007 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2, or (at your option)
+the Free Software Foundation; either version 3, or (at your option)
any later version.
GCC is distributed in the hope that it will be useful,
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to
-the Free Software Foundation, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "pointer-set.h"
-/* A pointer sets is represented as a simple open-addressing hash
+/* A pointer set is represented as a simple open-addressing hash
table. Simplifications: The hash code is based on the value of the
pointer, not what it points to. The number of buckets is always a
power of 2. Null pointers are a reserved value. Deletion is not
- supported. There is no mechanism for user control of hash
- function, equality comparison, initial size, or resizing policy.
-*/
+ supported (yet). There is no mechanism for user control of hash
+ function, equality comparison, initial size, or resizing policy. */
struct pointer_set_t
{
size_t n_slots; /* n_slots = 2^log_slots */
size_t n_elements;
- void **slots;
+ const void **slots;
};
/* Use the multiplicative method, as described in Knuth 6.4, to obtain
result->log_slots = 8;
result->n_slots = (size_t) 1 << result->log_slots;
- result->slots = XCNEWVEC (void *, result->n_slots);
+ result->slots = XCNEWVEC (const void *, result->n_slots);
return result;
}
/* Reclaims all memory associated with PSET. */
-void pointer_set_destroy (struct pointer_set_t *pset)
+void
+pointer_set_destroy (struct pointer_set_t *pset)
{
XDELETEVEC (pset->slots);
XDELETE (pset);
/* Returns nonzero if PSET contains P. P must be nonnull.
- Collisions are resolved by linear probing. More complicated
- collision management schemes are only useful when the load factor
- significantly exceeds 0.5, and we never let that happen. */
+ Collisions are resolved by linear probing. */
int
-pointer_set_contains (struct pointer_set_t *pset, void *p)
+pointer_set_contains (const struct pointer_set_t *pset, const void *p)
{
size_t n = hash1 (p, pset->n_slots, pset->log_slots);
while (true)
{
if (pset->slots[n] == p)
- return 1;
+ return 1;
else if (pset->slots[n] == 0)
- return 0;
+ return 0;
else
- {
- ++n;
- if (n == pset->n_slots)
- n = 0;
- }
+ {
+ ++n;
+ if (n == pset->n_slots)
+ n = 0;
+ }
}
}
-/* Subroutine of pointer_set_insert. Inserts P into an empty
- element of SLOTS, an array of length N_SLOTS. Returns nonzero
- if P was already present in N_SLOTS. */
-static int
-insert_aux (void *p, void **slots, size_t n_slots, size_t log_slots)
+/* Subroutine of pointer_set_insert. Return the insertion slot for P into
+ an empty element of SLOTS, an array of length N_SLOTS. */
+static inline size_t
+insert_aux (const void *p, const void **slots, size_t n_slots, size_t log_slots)
{
size_t n = hash1 (p, n_slots, log_slots);
while (true)
{
- if (slots[n] == p)
- return 1;
- else if (slots[n] == 0)
- {
- slots[n] = p;
- return 0;
- }
+ if (slots[n] == p || slots[n] == 0)
+ return n;
else
{
++n;
/* Inserts P into PSET if it wasn't already there. Returns nonzero
if it was already there. P must be nonnull. */
int
-pointer_set_insert (struct pointer_set_t *pset, void *p)
+pointer_set_insert (struct pointer_set_t *pset, const void *p)
{
- if (insert_aux (p, pset->slots, pset->n_slots, pset->log_slots))
- return 1;
-
- /* We've inserted a new element. Expand the table if necessary to keep
- the load factor small. */
- ++pset->n_elements;
+ size_t n;
+
+ /* For simplicity, expand the set even if P is already there. This can be
+ superfluous but can happen at most once. */
if (pset->n_elements > pset->n_slots / 4)
{
size_t new_log_slots = pset->log_slots + 1;
size_t new_n_slots = pset->n_slots * 2;
- void **new_slots = XCNEWVEC (void *, new_n_slots);
+ const void **new_slots = XCNEWVEC (const void *, new_n_slots);
size_t i;
for (i = 0; i < pset->n_slots; ++i)
- {
- if (pset->slots[i])
- insert_aux (pset->slots[i], new_slots, new_n_slots, new_log_slots);
+ {
+ const void *value = pset->slots[i];
+ n = insert_aux (value, new_slots, new_n_slots, new_log_slots);
+ new_slots[n] = value;
}
XDELETEVEC (pset->slots);
pset->slots = new_slots;
}
+ n = insert_aux (p, pset->slots, pset->n_slots, pset->log_slots);
+ if (pset->slots[n])
+ return 1;
+
+ pset->slots[n] = p;
+ ++pset->n_elements;
return 0;
}
+
+/* Pass each pointer in PSET to the function in FN, together with the fixed
+ parameter DATA. If FN returns false, the iteration stops. */
+
+void pointer_set_traverse (const struct pointer_set_t *pset,
+ bool (*fn) (const void *, void *), void *data)
+{
+ size_t i;
+ for (i = 0; i < pset->n_slots; ++i)
+ if (pset->slots[i] && !fn (pset->slots[i], data))
+ break;
+}
+
+\f
+/* A pointer map is represented the same way as a pointer_set, so
+ the hash code is based on the address of the key, rather than
+ its contents. Null keys are a reserved value. Deletion is not
+ supported (yet). There is no mechanism for user control of hash
+ function, equality comparison, initial size, or resizing policy. */
+
+struct pointer_map_t
+{
+ size_t log_slots;
+ size_t n_slots; /* n_slots = 2^log_slots */
+ size_t n_elements;
+
+ const void **keys;
+ void **values;
+};
+
+/* Allocate an empty pointer map. */
+struct pointer_map_t *
+pointer_map_create (void)
+{
+ struct pointer_map_t *result = XNEW (struct pointer_map_t);
+
+ result->n_elements = 0;
+ result->log_slots = 8;
+ result->n_slots = (size_t) 1 << result->log_slots;
+
+ result->keys = XCNEWVEC (const void *, result->n_slots);
+ result->values = XCNEWVEC (void *, result->n_slots);
+ return result;
+}
+
+/* Reclaims all memory associated with PMAP. */
+void pointer_map_destroy (struct pointer_map_t *pmap)
+{
+ XDELETEVEC (pmap->keys);
+ XDELETEVEC (pmap->values);
+ XDELETE (pmap);
+}
+
+/* Returns a pointer to the value to which P maps, if PMAP contains P. P
+ must be nonnull. Return NULL if PMAP does not contain P.
+
+ Collisions are resolved by linear probing. */
+void **
+pointer_map_contains (const struct pointer_map_t *pmap, const void *p)
+{
+ size_t n = hash1 (p, pmap->n_slots, pmap->log_slots);
+
+ while (true)
+ {
+ if (pmap->keys[n] == p)
+ return &pmap->values[n];
+ else if (pmap->keys[n] == 0)
+ return NULL;
+ else
+ {
+ ++n;
+ if (n == pmap->n_slots)
+ n = 0;
+ }
+ }
+}
+
+/* Inserts P into PMAP if it wasn't already there. Returns a pointer
+ to the value. P must be nonnull. */
+void **
+pointer_map_insert (struct pointer_map_t *pmap, const void *p)
+{
+ size_t n;
+
+ /* For simplicity, expand the map even if P is already there. This can be
+ superfluous but can happen at most once. */
+ if (pmap->n_elements > pmap->n_slots / 4)
+ {
+ size_t new_log_slots = pmap->log_slots + 1;
+ size_t new_n_slots = pmap->n_slots * 2;
+ const void **new_keys = XCNEWVEC (const void *, new_n_slots);
+ void **new_values = XCNEWVEC (void *, new_n_slots);
+ size_t i;
+
+ for (i = 0; i < pmap->n_slots; ++i)
+ if (pmap->keys[i])
+ {
+ const void *key = pmap->keys[i];
+ n = insert_aux (key, new_keys, new_n_slots, new_log_slots);
+ new_keys[n] = key;
+ new_values[n] = pmap->values[i];
+ }
+
+ XDELETEVEC (pmap->keys);
+ XDELETEVEC (pmap->values);
+ pmap->n_slots = new_n_slots;
+ pmap->log_slots = new_log_slots;
+ pmap->keys = new_keys;
+ pmap->values = new_values;
+ }
+
+ n = insert_aux (p, pmap->keys, pmap->n_slots, pmap->log_slots);
+ if (!pmap->keys[n])
+ {
+ ++pmap->n_elements;
+ pmap->keys[n] = p;
+ }
+
+ return &pmap->values[n];
+}
+
+/* Pass each pointer in PMAP to the function in FN, together with the pointer
+ to the value and the fixed parameter DATA. If FN returns false, the
+ iteration stops. */
+
+void pointer_map_traverse (const struct pointer_map_t *pmap,
+ bool (*fn) (const void *, void **, void *), void *data)
+{
+ size_t i;
+ for (i = 0; i < pmap->n_slots; ++i)
+ if (pmap->keys[i] && !fn (pmap->keys[i], &pmap->values[i], data))
+ break;
+}
OSDN Git Service
