Azinix

var_set.h

Go to the documentation of this file.
00001 
00002 /** \file var_set.h
00003 
00004   \brief Bit vectors
00005 
00006 */
00007 
00008 #ifndef VAR_SET_H
00009 #define VAR_SET_H
00010 
00011 #ifdef __cplusplus
00012 extern "C" {
00013 #endif
00014 
00015 #define VAR_SET_BYTE_SIZE 8
00016 
00017 #define VAR_SET_WORD_SIZE ((sizeof(unsigned int))*(VAR_SET_BYTE_SIZE))
00018 #define VAR_SET_ALL_ZEROS 0
00019 #define VAR_SET_ALL_ONES  ((unsigned int) ~0)
00020 #define VAR_SET_EXTRACT_BIT(word,pos) (((word) & (1 << (pos))) != 0)
00021 
00022 /** \brief Bit vector */
00023 
00024 typedef struct var_set_t
00025 {
00026   int n_elts;
00027   int n_words;
00028   unsigned int *data;
00029 } var_set_t;
00030 
00031 extern var_set_t *var_set_new (int);
00032 extern var_set_t *var_set_copy (var_set_t *);
00033 extern var_set_t *var_set_assign (var_set_t *, var_set_t *);
00034 extern void var_set_free (var_set_t *);
00035 extern int var_set_n_elts (var_set_t *);
00036 extern var_set_t *var_set_or (var_set_t *, var_set_t *, var_set_t *);
00037 extern var_set_t *var_set_and (var_set_t *, var_set_t *, var_set_t *);
00038 extern var_set_t *var_set_not (var_set_t *, var_set_t *);
00039 extern int var_set_get_elt (var_set_t *, int);
00040 extern void var_set_set_elt (var_set_t *, int);
00041 extern void var_set_clear_elt (var_set_t *, int);
00042 extern void var_set_clear (var_set_t *);
00043 extern int var_set_intersect (var_set_t *, var_set_t *);
00044 extern int var_set_is_empty (var_set_t *);
00045 extern int var_set_is_full (var_set_t *);
00046 extern void var_set_print (FILE *, var_set_t *);
00047 extern int var_set_equal (var_set_t *, var_set_t *);
00048 extern int var_set_cmp (char *, char *);
00049 extern unsigned int var_set_hash_with_modulus (var_set_t *, unsigned int);
00050 extern unsigned int var_set_hash (var_set_t *);
00051 
00052 
00053 // extern inline var_set_t *
00054 // var_set_new (int size)
00055 // {
00056 //   int n_words =
00057 //     size / VAR_SET_WORD_SIZE + ((size % VAR_SET_WORD_SIZE == 0) ? 0 : 1);
00058 //   var_set_t *result =
00059 //     (var_set_t *) malloc (sizeof (int) + sizeof (int) +
00060 //            sizeof (unsigned int *) +
00061 //            n_words * sizeof (unsigned int));
00062 //   result->n_elts = size;
00063 //   result->n_words = n_words;
00064 //   result->data = (unsigned int *) (((char *) (result))
00065 //                 + sizeof (int)
00066 //                 + sizeof (int) + sizeof (unsigned int *));
00067 //   (void) var_set_clear (result);
00068 //   return result;
00069 // }
00070 // 
00071 // extern inline var_set_t *
00072 // var_set_or ( 
00073 //      var_set_t *result,
00074 //      var_set_t *a,
00075 //      var_set_t *b
00076 // )
00077 // {
00078 //   int i;
00079 //   util_assert (result->n_elts == a->n_elts);
00080 //   util_assert (result->n_elts == b->n_elts);
00081 //   for (i = 0; i < result->n_words; i++)
00082 //     result->data[i] = a->data[i] | b->data[i];
00083 //   return result;
00084 // }
00085 // 
00086 // extern inline var_set_t *
00087 // var_set_and (result, a, b)
00088 //      var_set_t *result;
00089 //      var_set_t *a;
00090 //      var_set_t *b;
00091 // {
00092 //   int i;
00093 //   util_assert (result->n_elts == a->n_elts);
00094 //   util_assert (result->n_elts == b->n_elts);
00095 //   for (i = 0; i < result->n_words; i++)
00096 //     result->data[i] = a->data[i] & b->data[i];
00097 //   return result;
00098 // }
00099 // 
00100 // extern inline var_set_t *
00101 // var_set_not (result, a)
00102 //      var_set_t *result;
00103 //      var_set_t *a;
00104 // {
00105 //   int i;
00106 //   unsigned int mask;
00107 // 
00108 //   util_assert (result->n_elts == a->n_elts);
00109 //   for (i = 0; i < a->n_words; i++)
00110 //     result->data[i] = ~a->data[i];
00111 //   mask =
00112 //     (unsigned int) VAR_SET_ALL_ONES >> (a->n_words * VAR_SET_WORD_SIZE -
00113 //                  a->n_elts);
00114 //   result->data[a->n_words - 1] &= mask;
00115 //   return result;
00116 // }
00117 // 
00118 // extern inline int
00119 // var_set_get_elt (set, index)
00120 //      var_set_t *set;
00121 //      int index;
00122 // {
00123 //   util_assert (index >= 0 && index < set->n_elts);
00124 //   return VAR_SET_EXTRACT_BIT (set->data[index / VAR_SET_WORD_SIZE],
00125 //                index % VAR_SET_WORD_SIZE);
00126 // 
00127 // }
00128 // 
00129 // extern inline void
00130 // var_set_set_elt (set, index)
00131 //      var_set_t *set;
00132 //      int index;
00133 // {
00134 //   unsigned int *value;
00135 //   util_assert (index >= 0 && index < set->n_elts);
00136 //   value = &(set->data[index / VAR_SET_WORD_SIZE]);
00137 //   *value = *value | (1 << (index % VAR_SET_WORD_SIZE));
00138 // }
00139 // 
00140 // extern inline void
00141 // var_set_clear_elt (set, index)
00142 //      var_set_t *set;
00143 //      int index;
00144 // {
00145 //   unsigned int *value;
00146 //   util_assert (index >= 0 && index < set->n_elts);
00147 //   value = &(set->data[index / VAR_SET_WORD_SIZE]);
00148 //   *value = *value & ~(1 << (index % VAR_SET_WORD_SIZE));
00149 // }
00150 // 
00151 // 
00152 // extern inline int
00153 // var_set_intersect (a, b)
00154 //      var_set_t *a;
00155 //      var_set_t *b;
00156 // {
00157 //   int i;
00158 //   util_assert (a->n_elts == b->n_elts);
00159 //   for (i = 0; i < a->n_words; i++)
00160 //     if (a->data[i] & b->data[i])
00161 //       return 1;
00162 //   return 0;
00163 // }
00164 // 
00165 // extern inline int
00166 // var_set_is_empty (a)
00167 //      var_set_t *a;
00168 // {
00169 //   int i;
00170 //   for (i = 0; i < a->n_words; i++)
00171 //     if (a->data[i])
00172 //       return 0;
00173 //   return 1;
00174 // }
00175 // 
00176 // extern inline int
00177 // var_set_is_full (a)
00178 //      var_set_t *a;
00179 // {
00180 //   int i;
00181 //   unsigned int value;
00182 //   for (i = 0; i < a->n_words - 1; i++)
00183 //     if (a->data[i] != VAR_SET_ALL_ONES)
00184 //       return 0;
00185 //   value = VAR_SET_ALL_ONES >> (a->n_words * VAR_SET_WORD_SIZE - a->n_elts);
00186 //   return (a->data[a->n_words - 1] == value);
00187 // }
00188 
00189 /**AutomaticStart*************************************************************/
00190 
00191 /*---------------------------------------------------------------------------*/
00192 /* Function prototypes                                                       */
00193 /*---------------------------------------------------------------------------*/
00194 
00195 
00196 /**AutomaticEnd***************************************************************/
00197 #ifdef __cplusplus
00198 }
00199 #endif
00200 
00201 #endif