Azinix

var_set.c

Go to the documentation of this file.
00001 
00002 /** \file var_set.c
00003 
00004 \brief Bit vectors
00005 
00006 The var_set_t data
00007 structure is essentially a bit array.  Its size is static.  The positions of
00008 the array are numbered from 0 to n-1, where n is the size of the var_set. When
00009 a bit is "set", its value is 1; when a bit is "clear", its value is 0.
00010 
00011 */
00012 
00013 
00014 #include "util.h"
00015 #include "var_set.h"
00016 
00017 
00018 /** \brief Allocate a new var_set data structure of size `size'.  Clears all the elements.  */
00019 
00020 var_set_t *
00021 var_set_new (int size)
00022 {
00023   int n_words =
00024     size / VAR_SET_WORD_SIZE + ((size % VAR_SET_WORD_SIZE == 0) ? 0 : 1);
00025   var_set_t *result =
00026     (var_set_t *) malloc (sizeof (int) + sizeof (int) +
00027               sizeof (unsigned int *) +
00028               n_words * sizeof (unsigned int));
00029   result->n_elts = size;
00030   result->n_words = n_words;
00031   result->data = (unsigned int *) ((char *) result
00032                    + sizeof (int)
00033                    + sizeof (int) + sizeof (unsigned int *));
00034   (void) var_set_clear (result);
00035   return result;
00036 }
00037 
00038 
00039 /** \brief Allocate a new var_set data structure with the same contents as `set'.  */
00040 
00041 var_set_t *
00042 var_set_copy (var_set_t *set)
00043 {
00044   int i;
00045   var_set_t *result = ALLOC (var_set_t, 1);
00046 
00047   *result = *set;
00048   result->data = ALLOC (unsigned int, result->n_words);
00049   for (i = 0; i < result->n_words; i++)
00050     result->data[i] = set->data[i];
00051   return result;
00052 }
00053 
00054 /** \brief Assign the contents of `result' to be the same as those of `set'.  
00055 
00056 `result' and `set' must be the same size.  */
00057 
00058 var_set_t *
00059 var_set_assign ( var_set_t *result,  var_set_t *set)
00060 {
00061   int i;
00062 
00063   assert (result->n_elts == set->n_elts);
00064   for (i = 0; i < result->n_words; i++)
00065     result->data[i] = set->data[i];
00066   return result;
00067 }
00068 
00069 /** \brief Free the var_set data structure `set'.  */
00070 
00071 void
00072 var_set_free (var_set_t *set)
00073 {
00074   free (set);
00075 }
00076 
00077 // caches number of bits set in a byte
00078 static int size_array[256];
00079 
00080 static void
00081 init_size_array ()
00082 {
00083   int i, j;
00084   int count;
00085 
00086   for (i = 0; i < 256; i++)
00087     {
00088       count = 0;
00089       for (j = 0; j < (int) VAR_SET_WORD_SIZE; j++)
00090     {
00091       count += VAR_SET_EXTRACT_BIT (i, j);
00092     }
00093       size_array[i] = count;
00094     }
00095 }
00096 
00097 /** \brief Return the number of bits in var_set `set' which are set (i.e. the
00098    cardinality of the set) */
00099 
00100 int
00101 var_set_n_elts (var_set_t *set)
00102 {
00103   register int i, j;
00104   register unsigned int value;
00105   int n_bytes = VAR_SET_WORD_SIZE / VAR_SET_BYTE_SIZE;
00106   int count = 0;
00107 
00108   if (size_array[1] == 0)
00109     {
00110       // should be 1 - implies its uninitialized, assuming static array entries are set to 0
00111       init_size_array ();
00112     }
00113 
00114   for (i = 0; i < set->n_words; i++)
00115     {
00116       value = set->data[i];
00117       for (j = 0; j < n_bytes; j++)
00118     {
00119       count += size_array[value & 0xff];
00120       value >>= VAR_SET_BYTE_SIZE;
00121     }
00122     }
00123   return count;
00124 }
00125 
00126 /** \brief  Compute the bitwise inclusive OR of `a' and `b', and store the result in
00127 `result'.  Also, return a pointer to `result'.  
00128 
00129 `a', `b', and `result' must be the same size.  
00130       
00131 Note that `result' can be the same as either or
00132 both of `a' and `b' (e.g. var_set_or(foo, foo, bar)).
00133 */
00134 
00135 var_set_t *
00136 var_set_or (
00137     var_set_t *result, 
00138     var_set_t *a, 
00139     var_set_t *b
00140 )
00141 {
00142   int i;
00143   assert (result->n_elts == a->n_elts);
00144   assert (result->n_elts == b->n_elts);
00145   for (i = 0; i < result->n_words; i++)
00146     result->data[i] = a->data[i] | b->data[i];
00147   return result;
00148 }
00149 
00150 /** \brief Compute the bitwise AND of `a' and `b', and store the result in `result'.
00151    Also, return a pointer to `result'.  
00152    
00153    `a', `b', and `result' must be the same size.  
00154       
00155 Note that `result' can be the same as either or both of `a'
00156 and `b' (e.g. var_set_and(foo, foo, bar)).
00157 */
00158 
00159 var_set_t *
00160 var_set_and (
00161     var_set_t *result, 
00162     var_set_t *a, 
00163     var_set_t *b)
00164 {
00165   int i;
00166   assert (result->n_elts == a->n_elts);
00167   assert (result->n_elts == b->n_elts);
00168   for (i = 0; i < result->n_words; i++)
00169     result->data[i] = a->data[i] & b->data[i];
00170   return result;
00171 }
00172 
00173 /** \brief  Compute the bitwise complement of `a', and store the result in `result'.
00174    Also, return a pointer to `result'.  
00175    
00176 `a' and `result' must be the same size.  
00177       
00178 Note that `result' can be the same as `a' (e.g.
00179 var_set_not(foo, foo)).
00180 */
00181 
00182 var_set_t *
00183 var_set_not (var_set_t *result, var_set_t *a)
00184 {
00185   int i;
00186   unsigned int mask;
00187 
00188   assert (result->n_elts == a->n_elts);
00189   for (i = 0; i < a->n_words; i++)
00190     result->data[i] = ~a->data[i];
00191   mask =
00192     (unsigned int) VAR_SET_ALL_ONES >> (a->n_words * VAR_SET_WORD_SIZE -
00193                     a->n_elts);
00194   result->data[a->n_words - 1] &= mask;
00195   return result;
00196 }
00197 
00198 /** \brief
00199  Return the value of the bit at position `index' in `set'.  
00200 
00201 `index' must be
00202 at least zero and less than the size of `set'.
00203 */
00204 
00205 int
00206 var_set_get_elt (var_set_t *set, int index)
00207 {
00208   assert (index >= 0 && index < set->n_elts);
00209   return VAR_SET_EXTRACT_BIT (set->data[index / VAR_SET_WORD_SIZE],
00210                   index % VAR_SET_WORD_SIZE);
00211 
00212   // trying to see if avoiding mult or modulus helps
00213   // return VAR_SET_EXTRACT_BIT( set->data[ index >> 32 ], index & 31 );
00214   // made almost no  difference - the compiler must have figured out the >> and & 31
00215 }
00216 
00217 /** \brief
00218 Set the value of the bit at position `index' in `set'.  
00219 
00220 `index' must be at
00221 least zero and less than the size of `set'.
00222 */
00223 
00224 void
00225 var_set_set_elt (var_set_t *set, int index)
00226 {
00227   unsigned int *value;
00228   assert (index >= 0 && index < set->n_elts);
00229   value = &(set->data[index / VAR_SET_WORD_SIZE]);
00230   *value = *value | (1 << (index % VAR_SET_WORD_SIZE));
00231 }
00232 
00233 /** \brief Clear the value of the bit at position `index' in `set'.  
00234 
00235 `index' must be at
00236 least zero and less than the size of `set'.
00237 */
00238 
00239 void
00240 var_set_clear_elt (var_set_t *set, int index)
00241 {
00242   unsigned int *value;
00243   assert (index >= 0 && index < set->n_elts);
00244   value = &(set->data[index / VAR_SET_WORD_SIZE]);
00245   *value = *value & ~(1 << (index % VAR_SET_WORD_SIZE));
00246 }
00247 
00248 /** \brief Clear the value of all the bits in `set'.  */
00249 
00250 void
00251 var_set_clear (var_set_t *set)
00252 {
00253   int i;
00254 
00255   for (i = 0; i < set->n_words; i++)
00256     set->data[i] = 0;
00257 }
00258 
00259 /** \brief Return 1 if the var_sets `a' and `b' intersect (i.e. have bits set in the
00260    same position); otherwise, return 0.  
00261    
00262    `a' and `b' must be the same size.
00263 */
00264 
00265 int
00266 var_set_intersect (var_set_t *a, var_set_t *b)
00267 {
00268   int i;
00269   assert (a->n_elts == b->n_elts);
00270   for (i = 0; i < a->n_words; i++)
00271     if (a->data[i] & b->data[i])
00272       return 1;
00273   return 0;
00274 }
00275 
00276 /** \brief Return 1 if every bit of var_set `a' is cleared; otherwise, return 0.  */
00277 
00278 int
00279 var_set_is_empty (var_set_t *a)
00280 {
00281   int i;
00282   for (i = 0; i < a->n_words; i++)
00283     if (a->data[i])
00284       return 0;
00285   return 1;
00286 }
00287 
00288 /** \brief Return 1 if every bit of var_set `a' is set; otherwise, return 0. */
00289 
00290 int
00291 var_set_is_full (var_set_t *a)
00292 {
00293   int i;
00294   int value;
00295   for (i = 0; i < a->n_words - 1; i++)
00296     if (a->data[i] != VAR_SET_ALL_ONES)
00297       return 0;
00298   value = VAR_SET_ALL_ONES >> (a->n_words * VAR_SET_WORD_SIZE - a->n_elts);
00299   return (a->data[a->n_words - 1] == (unsigned int) value);
00300 }
00301 
00302 /** \brief  Print to `fp' the value of each bit in var_set `set'.  
00303 
00304 Example output for a set of 4 elements: "1 0 1 1". */
00305 
00306 void
00307 var_set_print (FILE *fp, var_set_t *set)
00308 {
00309   int i;
00310   for (i = 0; i < set->n_elts; i++)
00311     {
00312       fprintf (fp, "%d ", var_set_get_elt (set, i));
00313     }
00314   fprintf (fp, "\n");
00315 }
00316 
00317 
00318 /** \brief   Return 1 if the var_sets `a' and `b' are equal at every bit position;
00319    otherwise, return 0.  
00320    
00321    `a' and `b' must be the same size.
00322 */
00323 
00324 int
00325 var_set_equal (var_set_t *a, var_set_t *b)
00326 {
00327   int i;
00328 
00329   assert (a->n_elts == b->n_elts);
00330   for (i = 0; i < a->n_words; i++)
00331     if (a->data[i] != b->data[i])
00332       return 0;
00333   return 1;
00334 }
00335 
00336 
00337 /** \brief  Return 0 if the var_sets `a' and `b' are equal at every bit position;
00338 otherwise, return 1.  
00339    
00340 `a' and `b' must be the same size.
00341 */
00342 
00343 int
00344 var_set_cmp ( char *obj1,  char *obj2)
00345 {
00346   int i;
00347   var_set_t *a = (var_set_t *) obj1;
00348   var_set_t *b = (var_set_t *) obj2;
00349 
00350   assert (a->n_elts == b->n_elts);
00351   for (i = 0; i < a->n_words; i++)
00352     if (a->data[i] != b->data[i])
00353       return 1;
00354   return 0;
00355 }
00356 
00357 
00358 /** \brief
00359  Compute a hash value for the var_set `set'.  
00360  
00361  This is to be used when
00362  var_sets are used as keys in the st package specifically,
00363  since st expects the hash function to take a key and a modulus
00364 */
00365 
00366 unsigned int
00367 var_set_hash_with_modulus (
00368     var_set_t * set, 
00369     unsigned int modulus    // st expects the hash function to take a key and a modulus 
00370   )
00371 {
00372   return var_set_hash (set) % modulus;
00373 }
00374 
00375 /** \brief Compute a hash value for the var_set `set'.  */
00376 
00377 unsigned int
00378 var_set_hash (var_set_t *set)
00379 {
00380   int i;
00381   unsigned int result = 0;
00382 
00383   for (i = 0; i < set->n_words; i++)
00384     result += (unsigned int) set->data[i];
00385   return result;
00386 }