Jack2 1.9.6

bitset.h

00001 /*
00002 * bitset.h -- some simple bit vector set operations.
00003 *
00004 * This is useful for sets of small non-negative integers.  There are
00005 * some obvious set operations that are not implemented because I
00006 * don't need them right now.
00007 *
00008 * These functions represent sets as arrays of unsigned 32-bit
00009 * integers allocated on the heap.  The first entry contains the set
00010 * cardinality (number of elements allowed), followed by one or more
00011 * words containing bit vectors.
00012 *
00013 *  $Id: bitset.h,v 1.2 2005/11/23 11:24:29 letz Exp $
00014 */
00015 
00016 /*
00017  *  Copyright (C) 2005 Jack O'Quin
00018  *
00019  *  This program is free software; you can redistribute it and/or
00020  *  modify it under the terms of the GNU General Public License as
00021  *  published by the Free Software Foundation; either version 2 of the
00022  *  License, or (at your option) any later version.
00023  *
00024  *  This program is distributed in the hope that it will be useful,
00025  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00026  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00027  *  General Public License for more details.
00028  *
00029  *  You should have received a copy of the GNU General Public License
00030  *  along with this program; if not, write to the Free Software
00031  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00032  */
00033 
00034 #ifndef __bitset_h__
00035 #define __bitset_h__
00036 
00037 #include <inttypes.h>                   /* POSIX standard fixed-size types */
00038 #include <assert.h>                     /* `#define NDEBUG' to disable */
00039 
00040 /* On some 64-bit machines, this implementation may be slightly
00041  * inefficient, depending on how compilers allocate space for
00042  * uint32_t.  For the set sizes I currently need, this is acceptable.
00043  * It should not be hard to pack the bits better, if that becomes
00044  * worthwhile.
00045  */
00046 typedef uint32_t _bitset_word_t;
00047 typedef _bitset_word_t *bitset_t;
00048 
00049 #define WORD_SIZE(cardinality) (1+((cardinality)+31)/32)
00050 #define BYTE_SIZE(cardinality) (WORD_SIZE(cardinality)*sizeof(_bitset_word_t))
00051 #define WORD_INDEX(element) (1+(element)/32)
00052 #define BIT_INDEX(element) ((element)&037)
00053 
00054 static inline void
00055 bitset_add(bitset_t set
00056                , unsigned int element)
00057 {
00058     assert(element < set
00059                [0]);
00060     set
00061         [WORD_INDEX(element)] |= (1 << BIT_INDEX(element));
00062 }
00063 
00064 static inline void
00065 bitset_copy(bitset_t to_set, bitset_t from_set)
00066 {
00067     assert(to_set[0] == from_set[0]);
00068     memcpy(to_set, from_set, BYTE_SIZE(to_set[0]));
00069 }
00070 
00071 static inline void
00072 bitset_create(bitset_t *set
00073               , unsigned int cardinality)
00074 {
00075     *set
00076     = (bitset_t) calloc(WORD_SIZE(cardinality),
00077                         sizeof(_bitset_word_t));
00078     assert(*set
00079           );
00080     *set
00081     [0] = cardinality;
00082 }
00083 
00084 static inline void
00085 bitset_destroy(bitset_t *set
00086               )
00087 {
00088     if (*set
00089        ) {
00090         free(*set
00091             );
00092         *set
00093         = (bitset_t) 0;
00094     }
00095 }
00096 
00097 static inline int
00098 bitset_empty(bitset_t set
00099                 )
00100 {
00101     int i;
00102     _bitset_word_t result = 0;
00103     int nwords = WORD_SIZE(set
00104                            [0]);
00105     for (i = 1; i < nwords; i++) {
00106         result |= set
00107                       [i];
00108     }
00109     return (result == 0);
00110 }
00111 
00112 static inline int
00113 bitset_contains(bitset_t set
00114                     , unsigned int element)
00115 {
00116     assert(element < set
00117                [0]);
00118     return (0 != (set
00119                   [WORD_INDEX(element)] & (1 << BIT_INDEX(element))));
00120 }
00121 
00122 static inline void
00123 bitset_remove(bitset_t set
00124                   , unsigned int element)
00125 {
00126     assert(element < set
00127                [0]);
00128     set
00129         [WORD_INDEX(element)] &= ~(1 << BIT_INDEX(element));
00130 }
00131 
00132 #endif /* __bitset_h__ */