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 typedef int (*set_cmp_fun) (const void *elt, const void *key, size_t size);
  46
  47 /**
  48  * Creates a new set.
  49  *
  50  * @param func    the compare function of this set
  51  * @param slots   number of slots
  52  *
  53  * @returns
  54  *    created set
  55  */
  56 set *new_set (set_cmp_fun func, int slots);
  57
  58 /** Deletes a set and all elements of it. */
  59 void del_set (set *set);
  60
  61 /**
  62  * Searches an element in a set.
  63  *
  64  * @param set   the set to search in
  65  * @param key   the element to is searched
  66  * @param size  the size of key
  67  * @param hash  the hash value of key
  68  *
  69  * @return
  70  *    the address of the found element in the set of NULL if it was not found
  71  */
  72 void *set_find (set *set, const void *key, size_t size, unsigned hash);
  73
  74 /**
  75  * Inserts an element into a set.
  76  *
  77  * @param set   the set to insert in
  78  * @param key   a pointer to the element to be inserted
  79  * @param size  the size of the element that should be inserted
  80  * @param hash  the hash-value of the element
  81  *
  82  * @return a pointer to the inserted element
  83  *
  84  * @note
  85  *    It is not possible to insert on element more than once. If a element
  86  *    that should be inserted is already in the set, this functions does
  87  *    nothing but returning its pointer.
  88  */
  89 void *set_insert (set *set, const void *key, size_t size, unsigned hash);
  90
  91 /**
  92  * Inserts an element into a set and returns its set_entry.
  93  *
  94  * @param set   the set to insert in
  95  * @param key   a pointer to the element to be inserted
  96  * @param size  the size of the element that should be inserted
  97  * @param hash  the hash-value of the element
  98  *
  99  * @return a pointer to the set_entry of the inserted element
 100  *
 101  * @note
 102  *    It is not possible to insert on element more than once. If a element
 103  *    that should be inserted is already in the set, this functions does
 104  *    nothing but returning its set_entry.
 105  */
 106 set_entry *set_hinsert (set *set, const void *key, size_t size, unsigned hash);
 107
 108 /** Returns the first element of a set. */
 109 void *set_first (set *set);
 110
 111 /** Returns the next element of a set. */
 112 void *set_next (set *set);
 113
 114 /** Breaks the iteration of a set. Must be called before the next set_first() call */
 115 void set_break (set *set);
 116
 117 /* implementation specific */
 118 #define new_set(cmp, slots) (SET_TRACE (new_set) ((cmp), (slots)))
 119 #define set_find(set, key, size, hash) \
 120   _set_search ((set), (key), (size), (hash), _set_find)
 121 #define set_insert(set, key, size, hash) \
 122   _set_search ((set), (key), (size), (hash), _set_insert)
 123 #define set_hinsert(set, key, size, hash) \
 124   ((set_entry *)_set_search ((set), (key), (size), (hash), _set_hinsert))
 125
 126 #define SET_VRFY(set) (void)0
 127
 128 #ifdef STATS
 129 void set_stats (set *);
 130 #else
 131 # define set_stats(s) ((void)0)
 132 #endif
 133
 134 #ifdef DEBUG
 135 void set_describe (set *);
 136 #endif
 137
 138
 139 /* Private */
 140
 141 typedef enum { _set_find, _set_insert, _set_hinsert } _set_action;
 142
 143 void *_set_search (set *, const void *, size_t, unsigned, _set_action);
 144
 145 #if defined(DEBUG) && defined(HAVE_GNU_MALLOC)
 146 extern const char *set_tag;
 147 # ifdef SET_ID
 148 #   define SET_TRACE set_tag = SET_ID,
 149 # else
 150 #   define SET_TRACE set_tag = __FILE__,
 151 # endif
 152 #else /* !(DEBUG && HAVE_GNU_MALLOC) */
 153 #   define SET_TRACE
 154 #endif /* !(DEBUG && HAVE_GNU_MALLOC) */
 155
 156 #endif