linux/alsa/bitset.h

   1 /*
   2 * bitset.h -- some simple bit vector set operations.
   3 *
   4 * This is useful for sets of small non-negative integers.  There are
   5 * some obvious set operations that are not implemented because I
   6 * don't need them right now.
   7 *
   8 * These functions represent sets as arrays of unsigned 32-bit
   9 * integers allocated on the heap.  The first entry contains the set
  10 * cardinality (number of elements allowed), followed by one or more
  11 * words containing bit vectors.
  12 *
  13 *  $Id: bitset.h,v 1.2 2005/11/23 11:24:29 letz Exp $
  14 */
  15
  16 /*
  17  *  Copyright (C) 2005 Jack O'Quin
  18  *
  19  *  This program is free software; you can redistribute it and/or
  20  *  modify it under the terms of the GNU General Public License as
  21  *  published by the Free Software Foundation; either version 2 of the
  22  *  License, or (at your option) any later version.
  23  *
  24  *  This program is distributed in the hope that it will be useful,
  25  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  26  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  27  *  General Public License for more details.
  28  *
  29  *  You should have received a copy of the GNU General Public License
  30  *  along with this program; if not, write to the Free Software
  31  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  32  */
  33
  34 #ifndef __bitset_h__
  35 #define __bitset_h__
  36
  37 #include <inttypes.h>                   /* POSIX standard fixed-size types */
  38 #include <assert.h>                     /* `#define NDEBUG' to disable */
  39
  40 /* On some 64-bit machines, this implementation may be slightly
  41  * inefficient, depending on how compilers allocate space for
  42  * uint32_t.  For the set sizes I currently need, this is acceptable.
  43  * It should not be hard to pack the bits better, if that becomes
  44  * worthwhile.
  45  */
  46 typedef uint32_t _bitset_word_t;
  47 typedef _bitset_word_t *bitset_t;
  48
  49 #define WORD_SIZE(cardinality) (1+((cardinality)+31)/32)
  50 #define BYTE_SIZE(cardinality) (WORD_SIZE(cardinality)*sizeof(_bitset_word_t))
  51 #define WORD_INDEX(element) (1+(element)/32)
  52 #define BIT_INDEX(element) ((element)&037)
  53
  54 static inline void
  55 bitset_add(bitset_t set
  56                , unsigned int element)
  57 {
  58     assert(element < set
  59                [0]);
  60     set
  61         [WORD_INDEX(element)] |= (1 << BIT_INDEX(element));
  62 }
  63
  64 static inline void
  65 bitset_copy(bitset_t to_set, bitset_t from_set)
  66 {
  67     assert(to_set[0] == from_set[0]);
  68     memcpy(to_set, from_set, BYTE_SIZE(to_set[0]));
  69 }
  70
  71 static inline void
  72 bitset_create(bitset_t *set
  73               , unsigned int cardinality)
  74 {
  75     *set
  76     = (bitset_t) calloc(WORD_SIZE(cardinality),
  77                         sizeof(_bitset_word_t));
  78     assert(*set
  79           );
  80     *set
  81     [0] = cardinality;
  82 }
  83
  84 static inline void
  85 bitset_destroy(bitset_t *set
  86               )
  87 {
  88     if (*set
  89        ) {
  90         free(*set
  91             );
  92         *set
  93         = (bitset_t) 0;
  94     }
  95 }
  96
  97 static inline int
  98 bitset_empty(bitset_t set
  99                 )
 100 {
 101     int i;
 102     _bitset_word_t result = 0;
 103     int nwords = WORD_SIZE(set
 104                            [0]);
 105     for (i = 1; i < nwords; i++) {
 106         result |= set
 107                       [i];
 108     }
 109     return (result == 0);
 110 }
 111
 112 static inline int
 113 bitset_contains(bitset_t set
 114                     , unsigned int element)
 115 {
 116     assert(element < set
 117                [0]);
 118     return (0 != (set
 119                   [WORD_INDEX(element)] & (1 << BIT_INDEX(element))));
 120 }
 121
 122 static inline void
 123 bitset_remove(bitset_t set
 124                   , unsigned int element)
 125 {
 126     assert(element < set
 127                [0]);
 128     set
 129         [WORD_INDEX(element)] &= ~(1 << BIT_INDEX(element));
 130 }
 131
 132 #endif /* __bitset_h__ */