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 there 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 slots
  64  *
  65  * @returns
  66  *    created set
  67  */
  68 set *new_set (set_cmp_fun func, int slots);
  69
  70 /** Deletes a set and all elements of it. */
  71 void del_set (set *set);
  72
  73 /**
  74  * Searches an element in a set.
  75  *
  76  * @param set   the set to search in
  77  * @param key   the element to is searched
  78  * @param size  the size of key
  79  * @param hash  the hash value of key
  80  *
  81  * @return
  82  *    The address of the found element in the set or NULL if it was not found.
  83  */
  84 void *set_find (set *set, const void *key, size_t size, unsigned hash);
  85
  86 /**
  87  * Inserts an element into a set.
  88  *
  89  * @param set   the set to insert in
  90  * @param key   a pointer to the element to be inserted.  Element is copied!
  91  * @param size  the size of the element that should be inserted
  92  * @param hash  the hash-value of the element
  93  *
  94  * @return a pointer to the inserted element
  95  *
  96  * @note
  97  *    It is not possible to insert on element more than once. If an element
  98  *    that should be inserted is already in the set, this functions does
  99  *    nothing but returning its pointer.
 100  */
 101 void *set_insert (set *set, const void *key, size_t size, unsigned hash);
 102
 103 /**
 104  * Inserts an element into a set and returns its set_entry.
 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 set_entry of the inserted element
 112  *
 113  * @note
 114  *    It is not possible to insert an 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 set_entry.
 117  */
 118 set_entry *set_hinsert (set *set, const void *key, size_t size, unsigned hash);
 119
 120 /**
 121  * Inserts an element into a set, zero-terminate it 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 on 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_hinsert0 (set *set, const void *key, size_t size, unsigned hash);
 136
 137 /** Returns the first element of a set. */
 138 void *set_first (set *set);
 139
 140 /** Returns the next element of a set. */
 141 void *set_next (set *set);
 142
 143 /** Breaks the iteration of a set. Must be called before the next set_first() call */
 144 void set_break (set *set);
 145
 146 /* implementation specific */
 147 #define new_set(cmp, slots) (SET_TRACE (new_set) ((cmp), (slots)))
 148 #define set_find(set, key, size, hash) \
 149   _set_search ((set), (key), (size), (hash), _set_find)
 150 #define set_insert(set, key, size, hash) \
 151   _set_search ((set), (key), (size), (hash), _set_insert)
 152 #define set_hinsert(set, key, size, hash) \
 153   ((set_entry *)_set_search ((set), (key), (size), (hash), _set_hinsert))
 154 #define set_hinsert0(set, key, size, hash) \
 155   ((set_entry *)_set_search ((set), (key), (size), (hash), _set_hinsert0))
 156
 157 #define SET_VRFY(set) (void)0
 158
 159 #ifdef STATS
 160 void set_stats (set *);
 161 #else
 162 # define set_stats(s) ((void)0)
 163 #endif
 164
 165 #ifdef DEBUG
 166 void set_describe (set *);
 167 #endif
 168
 169
 170 /* Private */
 171
 172 typedef enum { _set_find, _set_insert, _set_hinsert, _set_hinsert0 } _set_action;
 173
 174 void *_set_search (set *, const void *, size_t, unsigned, _set_action);
 175
 176 #if defined(DEBUG) && defined(HAVE_GNU_MALLOC)
 177 extern const char *set_tag;
 178 # ifdef SET_ID
 179 #   define SET_TRACE set_tag = SET_ID,
 180 # else
 181 #   define SET_TRACE set_tag = __FILE__,
 182 # endif
 183 #else /* !(DEBUG && HAVE_GNU_MALLOC) */
 184 #   define SET_TRACE
 185 #endif /* !(DEBUG && HAVE_GNU_MALLOC) */
 186
 187 #endif