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

   1 /* Declarations for set.
   2    Copyright (C) 1995, 1996 Markus Armbruster */
   3
   4 /* $Id$ */
   5
   6 /**
   7  * @file set.h
   8  *
   9  * Declarations for set.
  10  */
  11
  12 #ifndef _SET_H
  13 #define _SET_H
  14
  15 #include <stddef.h>
  16
  17 /**
  18  * The abstract type of a set.
  19  *
  20  * This sets stores copies of its elements, so there is no need
  21  * to store the elements after there were added to a set.
  22  *
  23  * @see pset
  24  */
  25 typedef struct set set;
  26
  27 /** The entry of a set, representing an element in the set and it's meta-information */
  28 typedef struct set_entry {
  29   unsigned hash;    /**< the hash value of the element */
  30   size_t size;      /**< the size of the element */
  31   int dptr[1];                  /**< the element itself, data copied in must not need more
  32                                    alignment than this */
  33 } set_entry;
  34
  35 /**
  36  * The type of a set compare function.
  37  *
  38  * @param elt   pointer to an element
  39  * @param key   pointer to another element
  40  * @param size  size of the elements
  41  *
  42  * @return
  43  *    0 if the elements are identically, non-zero else
  44  *
  45  * @note
  46  *    Although it is possible to define different meanings for equality of two
  47  *    elements of a sets, they can be only equal if there sizes are
  48  *    equal. This is checked before the compare function is called.
  49  */
  50 typedef int (*set_cmp_fun) (const void *elt, const void *key, size_t size);
  51
  52 /**
  53  * Creates a new set.
  54  *
  55  * @param func    the compare function of this set
  56  * @param slots   number of slots
  57  *
  58  * @returns
  59  *    created set
  60  */
  61 set *new_set (set_cmp_fun func, int slots);
  62
  63 /** Deletes a set and all elements of it. */
  64 void del_set (set *set);
  65
  66 /**
  67  * Searches an element in a set.
  68  *
  69  * @param set   the set to search in
  70  * @param key   the element to is searched
  71  * @param size  the size of key
  72  * @param hash  the hash value of key
  73  *
  74  * @return
  75  *    the address of the found element in the set of NULL if it was not found
  76  */
  77 void *set_find (set *set, const void *key, size_t size, unsigned hash);
  78
  79 /**
  80  * Inserts an element into a set.
  81  *
  82  * @param set   the set to insert in
  83  * @param key   a pointer to the element to be inserted
  84  * @param size  the size of the element that should be inserted
  85  * @param hash  the hash-value of the element
  86  *
  87  * @return a pointer to the inserted element
  88  *
  89  * @note
  90  *    It is not possible to insert on element more than once. If a element
  91  *    that should be inserted is already in the set, this functions does
  92  *    nothing but returning its pointer.
  93  */
  94 void *set_insert (set *set, const void *key, size_t size, unsigned hash);
  95
  96 /**
  97  * Inserts an element into a set and returns its set_entry.
  98  *
  99  * @param set   the set to insert in
 100  * @param key   a pointer to the element to be inserted
 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 set_entry of the inserted element
 105  *
 106  * @note
 107  *    It is not possible to insert on element more than once. If a element
 108  *    that should be inserted is already in the set, this functions does
 109  *    nothing but returning its set_entry.
 110  */
 111 set_entry *set_hinsert (set *set, const void *key, size_t size, unsigned hash);
 112
 113 /**
 114  * Inserts an element into a set, zero-terminate it 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
 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 on element more than once. If a 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_hinsert0 (set *set, const void *key, size_t size, unsigned hash);
 129
 130 /** Returns the first element of a set. */
 131 void *set_first (set *set);
 132
 133 /** Returns the next element of a set. */
 134 void *set_next (set *set);
 135
 136 /** Breaks the iteration of a set. Must be called before the next set_first() call */
 137 void set_break (set *set);
 138
 139 /* implementation specific */
 140 #define new_set(cmp, slots) (SET_TRACE (new_set) ((cmp), (slots)))
 141 #define set_find(set, key, size, hash) \
 142   _set_search ((set), (key), (size), (hash), _set_find)
 143 #define set_insert(set, key, size, hash) \
 144   _set_search ((set), (key), (size), (hash), _set_insert)
 145 #define set_hinsert(set, key, size, hash) \
 146   ((set_entry *)_set_search ((set), (key), (size), (hash), _set_hinsert))
 147 #define set_hinsert0(set, key, size, hash) \
 148   ((set_entry *)_set_search ((set), (key), (size), (hash), _set_hinsert0))
 149
 150 #define SET_VRFY(set) (void)0
 151
 152 #ifdef STATS
 153 void set_stats (set *);
 154 #else
 155 # define set_stats(s) ((void)0)
 156 #endif
 157
 158 #ifdef DEBUG
 159 void set_describe (set *);
 160 #endif
 161
 162
 163 /* Private */
 164
 165 typedef enum { _set_find, _set_insert, _set_hinsert, _set_hinsert0 } _set_action;
 166
 167 void *_set_search (set *, const void *, size_t, unsigned, _set_action);
 168
 169 #if defined(DEBUG) && defined(HAVE_GNU_MALLOC)
 170 extern const char *set_tag;
 171 # ifdef SET_ID
 172 #   define SET_TRACE set_tag = SET_ID,
 173 # else
 174 #   define SET_TRACE set_tag = __FILE__,
 175 # endif
 176 #else /* !(DEBUG && HAVE_GNU_MALLOC) */
 177 #   define SET_TRACE
 178 #endif /* !(DEBUG && HAVE_GNU_MALLOC) */
 179
 180 #endif