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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief      optimized version of set for sets containing only pointers
   9  *             (deprecated)
  10  * @author     Markus Armbruster
  11  */
  12 #ifndef FIRM_ADT_PSET_H
  13 #define FIRM_ADT_PSET_H
  14
  15 #include <stddef.h>
  16
  17 #include "hashptr.h"
  18
  19 #include "../begin.h"
  20
  21 /**
  22  * @ingroup adt
  23  * @defgroup pset Pointer Set
  24  * (Hash)sets containing pointers.
  25  * @note This code has been deprecated. Use pset_new or cpset for new code.
  26  * @{
  27  */
  28
  29 /**
  30  * The default comparison function for pointers.
  31  * @param x A pointer.
  32  * @param y A pointer.
  33  * @return 0 if @p x and @p y are equal. Some value != 0 otherwise.
  34  */
  35 FIRM_API int pset_default_ptr_cmp(const void *x, const void *y);
  36
  37 /**
  38  * The abstract type of a pset (Set of pointers).
  39  *
  40  * This kind of sets stores only pointer to elements, the elements itself
  41  * must be stored somewhere else.
  42  *
  43  * @see set
  44  */
  45 typedef struct pset pset;
  46
  47 /** Inserts into pointer set with default hash function. */
  48 #define pset_insert_ptr(set,key)  pset_insert(set, key, hash_ptr(key))
  49 /** Inserts into pointer set with default hash function and return entry */
  50 #define pset_hinsert_ptr(set,key) pset_hinsert(set, key, hash_ptr(key))
  51 /** Removes pointer from pointer set with default hash function */
  52 #define pset_remove_ptr(set,key)  pset_remove(set, key, hash_ptr(key))
  53 /** Finds pointer in pointer set with default hash function */
  54 #define pset_find_ptr(set,key)    pset_find(set, key, hash_ptr(key))
  55 /** Creates new pointer set with default compare function */
  56 #define pset_new_ptr(slots)       new_pset(pset_default_ptr_cmp, slots)
  57 /** Creates new pointer set with default compare function and default size */
  58 #define pset_new_ptr_default()    pset_new_ptr(64)
  59
  60 /** The entry of a pset, representing an element pointer in the set and its meta-information */
  61 typedef struct {
  62   unsigned hash; /**< hash value of element */
  63   void *dptr;    /**< pointer to element data */
  64 } pset_entry;
  65
  66 /**
  67  * The type of a set compare function.
  68  *
  69  * @param elt   pointer to an element
  70  * @param key   pointer to another element
  71  *
  72  * @return
  73  *    0 if the elements are identically, non-zero else
  74  */
  75 typedef int (*pset_cmp_fun) (const void *elt, const void *key);
  76
  77 /**
  78  * Creates a new pset.
  79  *
  80  * @param func    The compare function of this pset.
  81  * @param slots   Initial number of collision chains.  I.e., \#slots
  82  *                different keys can be hashed without collisions.
  83  *
  84  * @returns
  85  *    created pset
  86  */
  87 FIRM_API pset *new_pset(pset_cmp_fun func, size_t slots);
  88
  89 /**
  90  * Deletes a pset.
  91  *
  92  * @param pset   the pset
  93  *
  94  * @note
  95  *    This does NOT delete the elements of this pset, just its pointers!
  96  */
  97 FIRM_API void del_pset(pset *pset);
  98
  99 /**
 100  * Returns the number of elements in a pset.
 101  *
 102  * @param pset   the pset
 103  */
 104 FIRM_API size_t pset_count(pset *pset);
 105
 106 /**
 107  * Searches an element pointer in a pset.
 108  *
 109  * @param pset  the pset to search in
 110  * @param key   the element to search
 111  * @param hash  the hash value of key
 112  *
 113  * @return
 114  *    the pointer of the found element in the pset or NULL if it was not found
 115  */
 116 FIRM_API void *pset_find(pset *pset, const void *key, unsigned hash);
 117
 118 /**
 119  * Inserts an element pointer into a pset.
 120  *
 121  * @param pset  the pset to insert in
 122  * @param key   a pointer to the element to be inserted
 123  * @param hash  the hash-value of the element
 124  *
 125  * @return a pointer to the inserted element
 126  *
 127  * @note
 128  *    It is not possible to insert an element more than once. If an element
 129  *    that should be inserted is already in the set, this functions does
 130  *    nothing but returning its already existing set_entry.
 131
 132  */
 133 FIRM_API void *pset_insert(pset *pset, const void *key, unsigned hash);
 134
 135 /**
 136  * Inserts an element pointer into a pset and returns its pset_entry.
 137  *
 138  * @param pset  the pset to insert in
 139  * @param key   a pointer to the element to be inserted
 140  * @param hash  the hash-value of the element
 141  *
 142  * @return a pointer to the pset_entry of the inserted element
 143  *
 144  * @note
 145  *    It is not possible to insert an element more than once. If an element
 146  *    that should be inserted is already in the pset, this functions does
 147  *    nothing but returning its pset_entry.
 148  */
 149 FIRM_API pset_entry *pset_hinsert(pset *pset, const void *key, unsigned hash);
 150
 151 /**
 152  * Removes an element from a pset.
 153  *
 154  * @param pset  the pset to delete in
 155  * @param key   a pointer to the element to be deleted
 156  * @param hash  the hash-value of the element
 157  *
 158  * @return
 159  *    the pointer to the removed element
 160  *
 161  * @remark
 162  *    The current implementation did not allow to remove non-existing elements.
 163  *    @@@ so, does it do now?
 164  *    Further, it is allowed to remove elements during an iteration
 165  *    including the current one.
 166  */
 167 FIRM_API void *pset_remove(pset *pset, const void *key, unsigned hash);
 168
 169 /**
 170  * Returns the first element of a pset.
 171  *
 172  * @param pset  the pset to iterate
 173  *
 174  * @return a pointer to the element or NULL if the set is empty
 175  */
 176 FIRM_API void *pset_first(pset *pset);
 177
 178 /**
 179  * Returns the first element of a pset.
 180  * This is a wrapper for pset_first(set); It allows to express the
 181  * intended type of the set elements (instead of weakly typed void*).
 182  *
 183  * @param type  destination type of the pointers in the set
 184  * @param pset  the pset to iterate
 185  *
 186  * @return a pointer to the element or NULL if the set is empty
 187  */
 188 #define pset_first(type, pset) ((type*)pset_first((pset)))
 189
 190 /**
 191  * Returns the next element of a pset.
 192  *
 193  * @param pset  the pset to iterate
 194  *
 195  * @return a pointer to the next element or NULL if the
 196  *         iteration is finished
 197  */
 198 FIRM_API void *pset_next(pset *pset);
 199
 200 /**
 201  * Returns the next element of a pset.
 202  * This is a wrapper for pset_next(set); It allows to express the
 203  * intended type of the set elements (instead of weakly typed void*).
 204  *
 205  * @param type  destination type of the pointers in the set
 206  * @param pset  the pset to iterate
 207  *
 208  * @return a pointer to the next element or NULL if the
 209  *         iteration is finished
 210  */
 211 #define pset_next(type, pset) ((type*)pset_next((pset)))
 212
 213 /**
 214  * Breaks the iteration of a set. Must be called before
 215  * the next pset_first() call if the iteration was NOT
 216  * finished.
 217  *
 218  * @param pset  the pset
 219  */
 220 FIRM_API void pset_break(pset *pset);
 221
 222 /**
 223  * Iterates oven an pset.
 224  *
 225  * @param pset   the pset
 226  * @param type   type of iterator variable
 227  * @param entry  the iterator
 228  */
 229 #define foreach_pset(pset, type, entry) for (type *entry = pset_first(type, pset); entry; entry = pset_next(type, pset))
 230
 231 /**
 232  * Inserts all elements of the pointer set src into
 233  * the set target (union).
 234  *
 235  * @param target  the target set, will contain the union
 236  * @param src     a set, will not be changed
 237  */
 238 FIRM_API void pset_insert_pset_ptr(pset *target, pset *src);
 239
 240 /** @cond PRIVATE */
 241
 242 #define new_pset(cmp, slots) ((new_pset) ((cmp), (slots)))
 243 #define pset_find(pset, key, hash) \
 244   _pset_search ((pset), (key), (hash), _pset_find)
 245 #define pset_insert(pset, key, hash) \
 246   _pset_search ((pset), (key), (hash), _pset_insert)
 247 #define pset_hinsert(pset, key, hash) \
 248   ((pset_entry *)_pset_search ((pset), (key), (hash), _pset_hinsert))
 249
 250 typedef enum { _pset_find, _pset_insert, _pset_hinsert } _pset_action;
 251
 252 FIRM_API void *_pset_search(pset *, const void *, unsigned, _pset_action);
 253
 254 /** @endcond */
 255
 256 /** @} */
 257
 258 #include "../end.h"
 259
 260 #endif