code_c/Maasha/src/lib/bits.c

   1 /* Martin Asser Hansen (mail@maasha.dk) Copyright (C) 2008 - All right reserved */
   2
   3 #include "common.h"
   4 #include "mem.h"
   5 #include "bits.h"
   6
   7
   8 static int mask_array[ 8 ] = {
   9     BIT1,   /* 10000000 */
  10     BIT2,   /* 01000000 */
  11     BIT3,   /* 00100000 */
  12     BIT4,   /* 00010000 */
  13     BIT5,   /* 00001000 */
  14     BIT6,   /* 00000100 */
  15     BIT7,   /* 00000010 */
  16     BIT8,   /* 00000001 */
  17 };
  18
  19
  20 void bitarray_new( bitarray **ba_ppt, size_t size )
  21 {
  22     /* Martin A. Hansen, August 2008. */
  23
  24     /* Initialize a new bitarray of a given size in bits. */
  25
  26     bitarray *ba_pt   = *ba_ppt;
  27     size_t    str_len = 0;
  28     size_t    modulus = 0;
  29
  30     assert( size > 0 );
  31
  32     ba_pt = mem_get( sizeof( bitarray ) );
  33
  34     str_len = size / BITS_IN_BYTE;
  35     modulus = size % BITS_IN_BYTE;
  36
  37     if ( modulus != 0 ) {
  38         str_len++;
  39     }
  40
  41     ba_pt->size    = size;
  42     ba_pt->str_len = str_len;
  43     ba_pt->str     = mem_get_zero( str_len + 1 );
  44     ba_pt->bits_on = 0;
  45
  46     *ba_ppt = ba_pt;
  47 }
  48
  49
  50 void bitarray_fill( bitarray *ba_pt )
  51 {
  52     /* Martin A. Hansen, August 2008. */
  53
  54     /* Set all bits in bitarray to 'on'. */
  55
  56     memset( ba_pt->str, BYTE_ON, ba_pt->str_len );
  57
  58     ba_pt->bits_on = ba_pt->size;
  59 }
  60
  61
  62 void bitarray_zero( bitarray *ba_pt )
  63 {
  64     /* Martin A. Hansen, August 2008. */
  65
  66     /* Set all bits in bitarray to 'off'. */
  67
  68     bzero( ba_pt->str, ba_pt->str_len );
  69
  70     ba_pt->bits_on = 0;
  71 }
  72
  73
  74 bool bitarray_bit_on( bitarray *ba_pt, size_t pos )
  75 {
  76     /* Martin A. Hansen, August 2008. */
  77
  78     /* Test if a specific bit in a bitarray is set to 'on'. */
  79
  80     /* if pos == 0:                         */
  81     /* ruler:    01234567 89012345 67890123 */
  82     /* bitarray: 00100100 10001000 00010001 */
  83     /* pos:      x                          */
  84     /* BIT1:     10000000                   */
  85     /* AND (&):  00000000                   */
  86
  87     /* if pos > 0 && modulus > 0:           */
  88     /* ruler:    01234567 89012345 67890123 */
  89     /* bitarray: 00100100 10001000 00010001 */
  90     /* pos:                           x     */
  91     /* BIT4 (modulus 3):           00010000 */
  92     /* AND (&):                    00010000 */
  93
  94     assert( pos <= ba_pt->size );
  95
  96     size_t str_pos = 0;
  97     size_t modulus = 0;
  98
  99     modulus = pos % BITS_IN_BYTE;
 100     str_pos = pos ? ( pos / BITS_IN_BYTE ) : 0;
 101
 102     if ( modulus != 0 ) {
 103         str_pos++;
 104     }
 105
 106     if ( ba_pt->str[ str_pos ] & mask_array[ modulus ] ) {
 107         return TRUE;
 108     } else {
 109         return FALSE;
 110     }
 111 }
 112
 113
 114 void bitarray_bit_set( bitarray *ba_pt, size_t pos )
 115 {
 116     /* Martin A. Hansen, August 2008. */
 117
 118     /* Set the bit at a given position in a bitarray to 'on'. */
 119
 120     /* if pos == 0:                         */
 121     /* ruler:    01234567 89012345 67890123 */
 122     /* bitarray: 00100100 10001000 00010001 */
 123     /* pos:      x                          */
 124     /* BIT1:     10000000                   */
 125     /* OR (|):   10100100                   */
 126
 127     /* if pos > 0 && modulus > 0:           */
 128     /* ruler:    01234567 89012345 67890123 */
 129     /* bitarray: 00100100 10001000 00010001 */
 130     /* pos:                            x    */
 131     /* BIT5 (modulus 4):           00001000 */
 132     /* OR (|):                     00011001 */
 133
 134     assert( pos <= ba_pt->size );
 135
 136     size_t str_pos = 0;
 137     size_t modulus = 0;
 138
 139     modulus = pos % BITS_IN_BYTE;
 140     str_pos = pos ? ( pos / BITS_IN_BYTE ) : 0;
 141
 142     if ( modulus != 0 ) {
 143         str_pos++;
 144     }
 145
 146     ba_pt->str[ str_pos ] |= mask_array[ modulus ];
 147 }
 148
 149
 150 void bitarray_print( bitarray *ba_pt )
 151 {
 152     /* Martin A. Hansen, August 2008. */
 153
 154     /* Debug function to print a bitarray. */
 155
 156     char   *str = NULL;
 157     size_t  i   = 0;
 158
 159     str = mem_get_zero( ba_pt->size + 1 );
 160
 161     for ( i = 0; i < ba_pt->size; i++ )
 162     {
 163         if ( bitarray_bit_on( ba_pt, i ) ) {
 164             str[ i ] = '1';
 165         } else {
 166             str[ i ] = '0';
 167         }
 168     }
 169
 170     printf( "\n" );
 171     printf( "ba_pt->str:       %s\n",   str );
 172     printf( "ba_pt->str (raw): %s\n",   ba_pt->str );
 173     printf( "ba_pt->size:      %zu\n",  ba_pt->size );
 174     printf( "ba_pt->str_len:   %zu\n",  ba_pt->str_len );
 175     printf( "ba_pt->bits_on:   %zu\n",  ba_pt->bits_on );
 176
 177     mem_free( &str );
 178 }
 179
 180
 181 void bitarray_destroy( bitarray **ba_ppt )
 182 {
 183     /* Martin A. Hansen, August 2008. */
 184
 185     /* Deallocate memory for bitarray. */
 186
 187     bitarray *ba_pt = *ba_ppt;
 188
 189     mem_free( &ba_pt->str );
 190
 191     *ba_ppt = NULL;
 192 }