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 for equality of two
  54  *    elements of a sets, they can be only equal if there sizes are
  55  *    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   number of initial slots
  64  *
  65  * @returns
  66  *    created set
  67  */
  68 set *new_set (set_cmp_fun func, int slots);
  69
  70 /**
  71  * Deletes a set and all elements of it.
  72  */
  73 void del_set (set *set);
  74
  75 /**
  76  * Returns the number of elements in a set.
  77  *
  78  * @param set   the set
  79  */
  80 int set_count (set *set);
  81
  82 /**
  83  * Searches an element in a set.
  84  *
  85  * @param set   the set to search in
  86  * @param key   the element to is searched
  87  * @param size  the size of key
  88  * @param hash  the hash value of key
  89  *
  90  * @return
  91  *    The address of the found element in the set or NULL if it was not found.
  92  */
  93 void *set_find (set *set, const void *key, size_t size, unsigned hash);
  94
  95 /**
  96  * Inserts an element into a set.
  97  *
  98  * @param set   the set to insert in
  99  * @param key   a pointer to the element to be inserted.  Element is copied!
 100  * @param size  the size of the element that should be inserted
 101  * @param hash  the hash-value of the element
 102  *
 103  * @return a pointer to the inserted element
 104  *
 105  * @note
 106  *    It is not possible to insert on element more than once. If an element
 107  *    that should be inserted is already in the set, this functions does
 108  *    nothing but returning its pointer.
 109  */
 110 void *set_insert (set *set, const void *key, size_t size, unsigned hash);
 111
 112 /**
 113  * Inserts an element into a set and returns its set_entry.
 114  *
 115  * @param set   the set to insert in
 116  * @param key   a pointer to the element to be inserted. Element is copied!
 117  * @param size  the size of the element that should be inserted
 118  * @param hash  the hash-value of the element
 119  *
 120  * @return a pointer to the set_entry of the inserted element
 121  *
 122  * @note
 123  *    It is not possible to insert an element more than once. If an element
 124  *    that should be inserted is already in the set, this functions does
 125  *    nothing but returning its set_entry.
 126  */
 127 set_entry *set_hinsert (set *set, const void *key, size_t size, unsigned hash);
 128
 129 /**
 130  * Inserts an element into a set, zero-terminate it and returns its set_entry.
 131  *
 132  * @param set   the set to insert in
 133  * @param key   a pointer to the element to be inserted.  Element is copied!
 134  * @param size  the size of the element that should be inserted
 135  * @param hash  the hash-value of the element
 136  *
 137  * @return a pointer to the set_entry of the inserted element
 138  *
 139  * @note
 140  *    It is not possible to insert on element more than once. If an element
 141  *    that should be inserted is already in the set, this functions does
 142  *    nothing but returning its set_entry.
 143  */
 144 set_entry *set_hinsert0 (set *set, const void *key, size_t size, unsigned hash);
 145
 146 /**
 147  * Returns the first element of a set.
 148  *
 149  * @param set  the set to iterate
 150  *
 151  * @return a pointer to the element or NULL if the set is empty
 152  */
 153 void *set_first (set *set);
 154
 155 /**
 156  * Returns the next element of a set.
 157  *
 158  * @param set  the set to iterate
 159  *
 160  * @return a pointer to the next element or NULL if the
 161  *         iteration is finished
 162  */
 163 void *set_next (set *set);
 164
 165 /**
 166  * Breaks the iteration of a set. Must be called before
 167  * the next pset_first() call if the iteration was NOT
 168  * finished.
 169  *
 170  * @param pset  the pset
 171  */
 172 void set_break (set *set);
 173
 174 /* implementation specific */
 175 #define new_set(cmp, slots) (SET_TRACE (new_set) ((cmp), (slots)))
 176 #define set_find(set, key, size, hash) \
 177   _set_search ((set), (key), (size), (hash), _set_find)
 178 #define set_insert(set, key, size, hash) \
 179   _set_search ((set), (key), (size), (hash), _set_insert)
 180 #define set_hinsert(set, key, size, hash) \
 181   ((set_entry *)_set_search ((set), (key), (size), (hash), _set_hinsert))
 182 #define set_hinsert0(set, key, size, hash) \
 183   ((set_entry *)_set_search ((set), (key), (size), (hash), _set_hinsert0))
 184
 185 #define SET_VRFY(set) (void)0
 186
 187 #ifdef STATS
 188 /**
 189  * Prints statistics on a set to stdout.
 190  *
 191  * @param set  the set
 192  */
 193 void set_stats (set *set);
 194 #else
 195 # define set_stats(s) ((void)0)
 196 #endif
 197
 198 #ifdef DEBUG
 199 void set_describe (set *);
 200 #endif
 201
 202
 203 /* Private */
 204
 205 typedef enum { _set_find, _set_insert, _set_hinsert, _set_hinsert0 } _set_action;
 206
 207 void *_set_search (set *, const void *, size_t, unsigned, _set_action);
 208
 209 #if defined(DEBUG) && defined(HAVE_GNU_MALLOC)
 210 extern const char *set_tag;
 211 # ifdef SET_ID
 212 #   define SET_TRACE set_tag = SET_ID,
 213 # else
 214 #   define SET_TRACE set_tag = __FILE__,
 215 # endif
 216 #else /* !(DEBUG && HAVE_GNU_MALLOC) */
 217 #   define SET_TRACE
 218 #endif /* !(DEBUG && HAVE_GNU_MALLOC) */
 219
 220 #endif