nsz Git - libfirm/blob - include/libfirm/adt/set.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       hashset: datastructure containing objects accessible by their key
  23  * @author      Markus Armbruster
  24  */
  25 #ifndef FIRM_ADT_SET_H
  26 #define FIRM_ADT_SET_H
  27
  28 #include <stddef.h>
  29
  30 #include "../begin.h"
  31
  32 /**
  33  * The abstract type of a set.
  34  *
  35  * This sets stores copies of its elements, so there is no need
  36  * to store the elements after they were added to a set.
  37  *
  38  * @see pset
  39  */
  40 typedef struct set set;
  41
  42 /** The entry of a set, representing an element in the set and its meta-information */
  43 typedef struct set_entry {
  44         unsigned hash;  /**< the hash value of the element */
  45         size_t size;    /**< the size of the element */
  46         int dptr[1];    /**< the element itself, data copied in must not need more
  47                              alignment than this */
  48 } set_entry;
  49
  50 /**
  51  * The type of a set compare function.
  52  *
  53  * @param elt   pointer to an element
  54  * @param key   pointer to another element
  55  * @param size  size of the elements
  56  *
  57  * @return
  58  *    0 if the elements are identically, non-zero else
  59  *
  60  * @note
  61  *    Although it is possible to define different meanings of equality
  62  *    of two elements of a set, they can be only equal if their sizes are
  63  *    are equal. This is checked before the compare function is called.
  64  */
  65 typedef int (*set_cmp_fun) (const void *elt, const void *key, size_t size);
  66
  67 /**
  68  * Creates a new set.
  69  *
  70  * @param func    The compare function of this set.
  71  * @param slots   Initial number of collision chains.  I.e., \#slots
  72  *                different keys can be hashed without collisions.
  73  *
  74  * @returns
  75  *    created set
  76  */
  77 FIRM_API set *new_set(set_cmp_fun func, size_t slots);
  78
  79 /**
  80  * Deletes a set and all elements of it.
  81  *
  82  * @param set  the set to delete
  83  */
  84 FIRM_API void del_set(set *set);
  85
  86 /**
  87  * Returns the number of elements in a set.
  88  *
  89  * @param set   the set
  90  */
  91 FIRM_API size_t set_count(set *set);
  92
  93 /**
  94  * Searches an element in a set.
  95  *
  96  * @param set   the set to search in
  97  * @param key   the element to is searched
  98  * @param size  the size of key
  99  * @param hash  the hash value of key
 100  *
 101  * @return
 102  *    The address of the found element in the set or NULL if it was not found.
 103  */
 104 FIRM_API void *set_find(set *set, const void *key, size_t size, unsigned hash);
 105
 106 /**
 107  * Inserts an element into a set.
 108  *
 109  * @param set   the set to insert in
 110  * @param key   a pointer to the element to be inserted.  Element is copied!
 111  * @param size  the size of the element that should be inserted
 112  * @param hash  the hash-value of the element
 113  *
 114  * @return a pointer to the inserted element
 115  *
 116  * @note
 117  *    It is not possible to insert one element more than once. If an element
 118  *    that should be inserted is already in the set, this functions does
 119  *    nothing but returning its pointer.
 120  */
 121 FIRM_API void *set_insert(set *set, const void *key, size_t size, unsigned hash);
 122
 123 /**
 124  * Inserts an element into a set and returns its set_entry.
 125  *
 126  * @param set   the set to insert in
 127  * @param key   a pointer to the element to be inserted. Element is copied!
 128  * @param size  the size of the element that should be inserted
 129  * @param hash  the hash-value of the element
 130  *
 131  * @return a pointer to the set_entry of the inserted element
 132  *
 133  * @note
 134  *    It is not possible to insert an element more than once. If an element
 135  *    that should be inserted is already in the set, this functions does
 136  *    nothing but returning its set_entry.
 137  */
 138 FIRM_API set_entry *set_hinsert(set *set, const void *key, size_t size, unsigned hash);
 139
 140 /**
 141  * Inserts an element into a set, zero-terminate it and returns its set_entry.
 142  *
 143  * @param set   the set to insert in
 144  * @param key   a pointer to the element to be inserted.  Element is copied!
 145  * @param size  the size of the element that should be inserted
 146  * @param hash  the hash-value of the element
 147  *
 148  * @return a pointer to the set_entry of the inserted element
 149  *
 150  * @note
 151  *    It is not possible to insert on element more than once. If an element
 152  *    that should be inserted is already in the set, this functions does
 153  *    nothing but returning its set_entry.
 154  */
 155 FIRM_API set_entry *set_hinsert0(set *set, const void *key, size_t size, unsigned hash);
 156
 157 /**
 158  * Returns the first element of a set.
 159  *
 160  * @param set  the set to iterate
 161  *
 162  * @return a pointer to the element or NULL if the set is empty
 163  */
 164 FIRM_API void *set_first(set *set);
 165
 166 /**
 167  * Returns the next element of a set.
 168  *
 169  * @param set  the set to iterate
 170  *
 171  * @return a pointer to the next element or NULL if the
 172  *         iteration is finished
 173  */
 174 FIRM_API void *set_next(set *set);
 175
 176 /**
 177  * Breaks the iteration of a set. Must be called before
 178  * the next set_first() call if the iteration was NOT
 179  * finished.
 180  *
 181  * @param set  the set
 182  */
 183 FIRM_API void set_break(set *set);
 184
 185 /**
 186  * Iterates over an set.
 187  *
 188  * @param set    the set
 189  * @param type   type of iterator variable
 190  * @param entry  the iterator
 191  */
 192 #define foreach_set(set, type, entry) for (entry = (type) set_first(set); entry; entry = (type) set_next(set))
 193
 194 /* implementation specific */
 195 #define new_set(cmp, slots) ((new_set) ((cmp), (slots)))
 196 #define set_find(set, key, size, hash) \
 197   _set_search ((set), (key), (size), (hash), _set_find)
 198 #define set_insert(set, key, size, hash) \
 199   _set_search ((set), (key), (size), (hash), _set_insert)
 200 #define set_hinsert(set, key, size, hash) \
 201   ((set_entry *)_set_search ((set), (key), (size), (hash), _set_hinsert))
 202 #define set_hinsert0(set, key, size, hash) \
 203   ((set_entry *)_set_search ((set), (key), (size), (hash), _set_hinsert0))
 204
 205 #define SET_VRFY(set) (void)0
 206
 207 #ifdef STATS
 208 /**
 209  * Prints statistics on a set to stdout.
 210  *
 211  * @param set  the set
 212  */
 213 void set_stats (set *set);
 214 #else
 215 # define set_stats(s) ((void)0)
 216 #endif
 217
 218 /* Private */
 219
 220 typedef enum { _set_find, _set_insert, _set_hinsert, _set_hinsert0 } _set_action;
 221
 222 FIRM_API void *_set_search(set *, const void *, size_t, unsigned, _set_action);
 223
 224 #include "../end.h"
 225
 226 #endif