This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Add pointer-map and traversal of pointer-set
- From: Paolo Bonzini <paolo dot bonzini at lu dot unisi dot ch>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>
- Date: Thu, 07 Dec 2006 11:15:45 +0100
- Subject: [PATCH] Add pointer-map and traversal of pointer-set
I think this is a valuable addition to the bag of data structures in GCC.
Bootstrapped/regtested i686-pc-linux-gnu, and widely used in my private
branch.
Ok for mainline? (I may work later on converting existing data
structures to the new pointer_map).
Paolo
2006-12-07 Paolo Bonzini <bonzini@gnu.org>
* pointer-set.c (insert_aux): Only return insertion slot.
(pointer_set_insert): Adjust.
(pointer_set_traverse, struct pointer_map_t, pointer_map_create,
pointer_map_destroy, pointer_map_insert, pointer_map_contains,
pointer_map_traverse): New.
* pointer-set.h (pointer_set_traverse, struct pointer_map_t,
pointer_map_create, pointer_map_destroy, pointer_map_insert,
pointer_map_contains, pointer_map_traverse): Declare.
Index: pointer-set.c
===================================================================
--- pointer-set.c (revision 118179)
+++ pointer-set.c (working copy)
@@ -114,22 +114,16 @@ pointer_set_contains (struct pointer_set
}
}
-/* 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
+/* 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 (void *p, 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;
@@ -144,12 +138,10 @@ insert_aux (void *p, void **slots, size_
int
pointer_set_insert (struct pointer_set_t *pset, 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;
@@ -158,9 +150,10 @@ pointer_set_insert (struct pointer_set_t
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);
+ {
+ void *value = pset->slots[i];
+ n = insert_aux (value, new_slots, new_n_slots, new_log_slots);
+ new_slots[n] = value;
}
XDELETEVEC (pset->slots);
@@ -169,5 +162,138 @@ pointer_set_insert (struct pointer_set_t
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 (struct pointer_set_t *pset,
+ bool (*fn) (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;
+}
+
+
+struct pointer_map_t
+{
+ size_t log_slots;
+ size_t n_slots; /* n_slots = 2^log_slots */
+ size_t n_elements;
+
+ 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 (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 (struct pointer_map_t *pmap, 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, 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;
+ void **new_keys = XCNEWVEC (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])
+ {
+ 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 (struct pointer_map_t *pmap,
+ bool (*fn) (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;
+}
Index: pointer-set.h
===================================================================
--- pointer-set.h (revision 118179)
+++ pointer-set.h (working copy)
@@ -22,11 +22,21 @@ Software Foundation, 51 Franklin Street,
#define POINTER_SET_H
struct pointer_set_t;
-
struct pointer_set_t *pointer_set_create (void);
void pointer_set_destroy (struct pointer_set_t *pset);
int pointer_set_contains (struct pointer_set_t *pset, void *p);
int pointer_set_insert (struct pointer_set_t *pset, void *p);
+void pointer_set_traverse (struct pointer_set_t *, bool (*) (void *, void *),
+ void *);
+
+struct pointer_map_t;
+struct pointer_map_t *pointer_map_create (void);
+void pointer_map_destroy (struct pointer_map_t *pmap);
+
+void **pointer_map_contains (struct pointer_map_t *pmap, void *p);
+void **pointer_map_insert (struct pointer_map_t *pmap, void *p);
+void pointer_map_traverse (struct pointer_map_t *,
+ bool (*) (void *, void **, void *), void *);
#endif /* POINTER_SET_H */