From ffe4c677aa8e6bac4fe345dd0c92d54792f013bf Mon Sep 17 00:00:00 2001 From: Michael Beck Date: Tue, 22 Jun 2004 11:12:47 +0000 Subject: [PATCH] Added functionality: - query number of elements of a set - remove element during itaration more doxygen comments [r3182] --- ir/adt/pset.h | 49 +++++++++++++++++++++++++++++++++++++++++++------ ir/adt/set.c | 27 ++++++++++++++++++++++++--- ir/adt/set.h | 45 +++++++++++++++++++++++++++++++++++++++------ 3 files changed, 106 insertions(+), 15 deletions(-) diff --git a/ir/adt/pset.h b/ir/adt/pset.h index 8f7d59f22..620a44d51 100644 --- a/ir/adt/pset.h +++ b/ir/adt/pset.h @@ -46,7 +46,7 @@ typedef int (*pset_cmp_fun) (const void *elt, const void *key); * Creates a new pset. * * @param func the compare function of this pset - * @param slots number of slots + * @param slots number of initial slots * * @returns * created pset @@ -61,6 +61,13 @@ pset *new_pset (pset_cmp_fun func, int slots); */ void del_pset (pset *pset); +/** + * Returns the number of elements in a pset. + * + * @param pset the pset + */ +int pset_count (pset *pset); + /** * Searches an element pointer in a pset. * @@ -117,17 +124,38 @@ pset_entry *pset_hinsert (pset *pset, const void *key, unsigned hash); * the pointer to the removed element * * @remark - * The current implementation did not allow to remove non-existing elements + * The current implementation did not allow to remove non-existing elements. + * Further, it is allowed to remove elements during an iteration + * including the current one. */ void *pset_remove (pset *pset, const void *key, unsigned hash); -/** returns the first element of a pset */ +/** + * Returns the first element of a pset. + * + * @param pset the pset to iterate + * + * @return a pointer to the element or NULL if the set is empty + */ void *pset_first (pset *pset); -/** returns the next element of a pset */ +/** + * Returns the next element of a pset. + * + * @param pset the pset to iterate + * + * @return a pointer to the next element or NULL if the + * iteration is finished + */ void *pset_next (pset *pset); -/** Breaks the iteration of a set. Must be called before the next pset_first() call */ +/** + * Breaks the iteration of a set. Must be called before + * the next pset_first() call if the iteration was NOT + * finished. + * + * @param pset the pset + */ void pset_break (pset *pset); #define new_pset(cmp, slots) (PSET_TRACE (new_pset) ((cmp), (slots))) @@ -139,12 +167,21 @@ void pset_break (pset *pset); ((pset_entry *)_pset_search ((pset), (key), (hash), _pset_hinsert)) #ifdef STATS -void pset_stats (pset *); +/** + * Prints statistics on a set to stdout. + * + * @param pset the pset + */ +void pset_stats (pset *pset); #else # define pset_stats(s) ((void)0) #endif #ifdef DEBUG +/** + * Describe a set by printing all elements + * to stdout. + */ void pset_describe (pset *); #endif diff --git a/ir/adt/set.c b/ir/adt/set.c index f81fa39b4..6ca07ec6c 100644 --- a/ir/adt/set.c +++ b/ir/adt/set.c @@ -198,7 +198,7 @@ SET * table->dir[i] = (Segment *)obstack_alloc (&table->obst, sizeof (Segment) * SEGMENT_SIZE); - memset (table->dir[i], 0, sizeof (Segment) * SEGMENT_SIZE); + memset(table->dir[i], 0, sizeof (Segment) * SEGMENT_SIZE); table->nseg++; } @@ -223,6 +223,12 @@ PMANGLE(del) (SET *table) xfree (table); } +int +MANGLEP(count) (SET *table) +{ + return table->nkey; +} + /* * do one iteration step, return 1 * if still data in the set, 0 else @@ -263,7 +269,8 @@ MANGLEP(first) (SET *table) void * MANGLEP(next) (SET *table) { - assert (table->iter_tail); + if (!table->iter_tail) + return NULL; /* follow collision chain */ table->iter_tail = table->iter_tail->chain; @@ -281,7 +288,6 @@ MANGLEP(next) (SET *table) void MANGLEP(break) (SET *table) { - assert (table->iter_tail); table->iter_tail = NULL; } @@ -490,9 +496,24 @@ pset_remove (SET *table, const void *key, unsigned hash) stat_chain_len (table, chain_len); q = *p; + + if (q == table->iter_tail) { + /* removing current element */ + table->iter_tail = q->chain; + if (!table->iter_tail) { + /* go to next segment */ + do { + if (!iter_step (table)) + break; + } while (!table->dir[table->iter_i][table->iter_j]); + table->iter_tail = table->dir[table->iter_i][table->iter_j]; + } + } + *p = (*p)->chain; q->chain = table->free_list; table->free_list = q; + --table->nkey; return q->entry.dptr; } diff --git a/ir/adt/set.h b/ir/adt/set.h index b171c66da..a97ca622f 100644 --- a/ir/adt/set.h +++ b/ir/adt/set.h @@ -60,16 +60,25 @@ typedef int (*set_cmp_fun) (const void *elt, const void *key, size_t size); * Creates a new set. * * @param func the compare function of this set - * @param slots number of slots + * @param slots number of initial slots * * @returns * created set */ set *new_set (set_cmp_fun func, int slots); -/** Deletes a set and all elements of it. */ +/** + * Deletes a set and all elements of it. + */ void del_set (set *set); +/** + * Returns the number of elements in a set. + * + * @param set the set + */ +int set_count (set *set); + /** * Searches an element in a set. * @@ -134,13 +143,32 @@ set_entry *set_hinsert (set *set, const void *key, size_t size, unsigned hash); */ set_entry *set_hinsert0 (set *set, const void *key, size_t size, unsigned hash); -/** Returns the first element of a set. */ +/** + * Returns the first element of a set. + * + * @param set the set to iterate + * + * @return a pointer to the element or NULL if the set is empty + */ void *set_first (set *set); -/** Returns the next element of a set. */ +/** + * Returns the next element of a set. + * + * @param set the set to iterate + * + * @return a pointer to the next element or NULL if the + * iteration is finished + */ void *set_next (set *set); -/** Breaks the iteration of a set. Must be called before the next set_first() call */ +/** + * Breaks the iteration of a set. Must be called before + * the next pset_first() call if the iteration was NOT + * finished. + * + * @param pset the pset + */ void set_break (set *set); /* implementation specific */ @@ -157,7 +185,12 @@ void set_break (set *set); #define SET_VRFY(set) (void)0 #ifdef STATS -void set_stats (set *); +/** + * Prints statistics on a set to stdout. + * + * @param set the set + */ +void set_stats (set *set); #else # define set_stats(s) ((void)0) #endif -- 2.20.1