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

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