nsz Git - libfirm/blob - ir/adt/pset.h

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/adt/pset.h
   4  * Purpose:     Declarations for pset.
   5  * Author:      Markus Armbruster
   6  * Modified by:
   7  * Created:     1999 by getting from fiasco
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 1995, 1996 Markus Armbruster
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 #ifndef _PSET_H
  14 #define _PSET_H
  15
  16 #include <stddef.h>
  17
  18 #include "hashptr.h"
  19
  20 /*
  21  * Define some convenience macros using the predefined hash function.
  22  */
  23 #define pset_insert_ptr(set,key) pset_insert(set, key, HASH_PTR(key))
  24 #define pset_hinsert_ptr(set,key) pset_hinsert(set, key, HASH_PTR(key))
  25 #define pset_remove_ptr(set,key) pset_remove(set, key, HASH_PTR(key))
  26 #define pset_find_ptr(set,key) pset_find(set, key, HASH_PTR(key))
  27
  28 /**
  29  * The abstract type of a pset (Set of pointers).
  30  *
  31  * This kind of sets stores only pointer to elements, the elements itself
  32  * must be stored somewere else.
  33  *
  34  * @see set
  35  */
  36 typedef struct pset pset;
  37
  38 /** The entry of a pset, representing an element pointer in the set and it's meta-information */
  39 typedef struct {
  40   unsigned hash;
  41   void *dptr;
  42 } pset_entry;
  43
  44 /**
  45  * The type of a set compare function.
  46  *
  47  * @param elt   pointer to an element
  48  * @param key   pointer to another element
  49  *
  50  * @return
  51  *    0 if the elements are identically, non-zero else
  52  */
  53 typedef int (*pset_cmp_fun) (const void *elt, const void *key);
  54
  55 /**
  56  * Creates a new pset.
  57  *
  58  * @param func    The compare function of this pset.
  59  * @param slots   Initial number of collision chains.  I.e., #slots
  60  *                different keys can be hashed without collisions.
  61  *
  62  * @returns
  63  *    created pset
  64  */
  65 pset *new_pset (pset_cmp_fun func, int slots);
  66
  67 /**
  68  * Deletes a pset.
  69  *
  70  * @param pset   the pset
  71  *
  72  * @note
  73  *    This does NOT delete the elements of this pset, just it's pointers!
  74  */
  75 void del_pset (pset *pset);
  76
  77 /**
  78  * Returns the number of elements in a pset.
  79  *
  80  * @param pset   the pset
  81  */
  82 int pset_count (pset *pset);
  83
  84 /**
  85  * Searches an element pointer in a pset.
  86  *
  87  * @param pset  the pset to search in
  88  * @param key   the element to search
  89  * @param hash  the hash value of key
  90  *
  91  * @return
  92  *    the pointer of the found element in the pset of NULL if it was not found
  93  */
  94 void *pset_find (pset *pset, const void *key, unsigned hash);
  95
  96 /**
  97  * Inserts an element pointer into a pset.
  98  *
  99  * @param pset  the pset to insert in
 100  * @param key   a pointer to the element to be inserted
 101  * @param hash  the hash-value of the element
 102  *
 103  * @return a pointer to the inserted element
 104  *
 105  * @note
 106  *    It is not possible to insert on element more than once. If a element
 107  *    that should be inserted is already in the set, this functions does
 108  *    nothing but returning its already existing set_entry.
 109
 110  */
 111 void *pset_insert (pset *pset, const void *key, unsigned hash);
 112
 113 /**
 114  * Inserts an element pointer into a pset and returns its pset_entry.
 115  *
 116  * @param pset  the pset to insert in
 117  * @param key   a pointer to the element to be inserted
 118  * @param hash  the hash-value of the element
 119  *
 120  * @return a pointer to the pset_entry of the inserted element
 121  *
 122  * @note
 123  *    It is not possible to insert on element more than once. If a element
 124  *    that should be inserted is already in the pset, this functions does
 125  *    nothing but returning its pset_entry.
 126  */
 127 pset_entry *pset_hinsert (pset *pset, const void *key, unsigned hash);
 128
 129 /**
 130  * Removes an element from a pset.
 131  *
 132  * @param pset  the pset to insert in
 133  * @param key   a pointer to the element to be inserted
 134  * @param hash  the hash-value of the element
 135  *
 136  * @return
 137  *    the pointer to the removed element
 138  *
 139  * @remark
 140  *    The current implementation did not allow to remove non-existing elements.
 141  *    Further, it is allowed to remove elements during an iteration
 142  *    including the current one.
 143  */
 144 void *pset_remove (pset *pset, const void *key, unsigned hash);
 145
 146 /**
 147  * Returns the first element of a pset.
 148  *
 149  * @param pset  the pset to iterate
 150  *
 151  * @return a pointer to the element or NULL if the set is empty
 152  */
 153 void *pset_first (pset *pset);
 154
 155 /**
 156  * Returns the next element of a pset.
 157  *
 158  * @param pset  the pset to iterate
 159  *
 160  * @return a pointer to the next element or NULL if the
 161  *         iteration is finished
 162  */
 163 void *pset_next (pset *pset);
 164
 165 /**
 166  * Breaks the iteration of a set. Must be called before
 167  * the next pset_first() call if the iteration was NOT
 168  * finished.
 169  *
 170  * @param pset  the pset
 171  */
 172 void pset_break (pset *pset);
 173
 174 #define new_pset(cmp, slots) (PSET_TRACE (new_pset) ((cmp), (slots)))
 175 #define pset_find(pset, key, hash) \
 176   _pset_search ((pset), (key), (hash), _pset_find)
 177 #define pset_insert(pset, key, hash) \
 178   _pset_search ((pset), (key), (hash), _pset_insert)
 179 #define pset_hinsert(pset, key, hash) \
 180   ((pset_entry *)_pset_search ((pset), (key), (hash), _pset_hinsert))
 181
 182 #ifdef STATS
 183 /**
 184  * Prints statistics on a set to stdout.
 185  *
 186  * @param pset  the pset
 187  */
 188 void pset_stats (pset *pset);
 189 #else
 190 # define pset_stats(s) ((void)0)
 191 #endif
 192
 193 #ifdef DEBUG
 194 /**
 195  * Describe a pset.
 196  *
 197  * Writes a description of a set to stdout. The description includes:
 198  * - a header telling how many elements (nkey) and segments (nseg) are in use
 199  * - for every collision chain the number of element with its hash values
 200  *
 201  * @param pset  the pset
 202  */
 203 void pset_describe (pset *pset);
 204 #endif
 205
 206 /* @@@ NYI */
 207 #define PSET_VRFY(pset) (void)0
 208
 209
 210 /* Private */
 211
 212 typedef enum { _pset_find, _pset_insert, _pset_hinsert } _pset_action;
 213
 214 void *_pset_search (pset *, const void *, unsigned, _pset_action);
 215
 216 #if defined(DEBUG) && defined(HAVE_GNU_MALLOC)
 217 extern const char *pset_tag;
 218 # ifdef PSET_ID
 219 #   define PSET_TRACE pset_tag = SET_ID,
 220 # else
 221 #   define PSET_TRACE pset_tag = __FILE__,
 222 # endif
 223 #else /* !(DEBUG && HAVE_GNU_MALLOC) */
 224 #   define PSET_TRACE
 225 #endif /* !(DEBUG && HAVE_GNU_MALLOC) */
 226
 227 #endif