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

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