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

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