code_c/Maasha/src/lib/barray.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 "barray.h"
   6
   7 #define SIZE_BLOCK 10000000
   8
   9 barray *barray_new( size_t nmemb )
  10 {
  11     /* Martin A. Hansen, November 2008. */
  12
  13     /* Initialize a new zeroed byte array
  14      * with nmemb number of elements. */
  15
  16     barray *ba = NULL;
  17
  18     ba        = mem_get( sizeof( barray ) );
  19     ba->array = mem_get_zero( nmemb * sizeof( ba->array ) );
  20     ba->nmemb = nmemb;
  21     ba->end   = 0;
  22
  23     return ba;
  24 }
  25
  26
  27 size_t barray_new_size( size_t nmemb_old )
  28 {
  29     /* Martin A. Hansen, November 2008. */
  30
  31     /* Returns a new larger byte array size. */
  32
  33     size_t nmemb_new = 1;
  34
  35     while ( nmemb_new < nmemb_old ) {
  36         nmemb_new += SIZE_BLOCK;
  37     }
  38
  39 //    fprintf( stderr, "New size: %zu\n", nmemb_new );
  40
  41     return nmemb_new;
  42 }
  43
  44
  45 void barray_resize( barray *ba, size_t nmemb_new )
  46 {
  47     /* Martin A. Hansen, November 2008. */
  48
  49     /* Reallocate a byte array, any new elements will be zeroed. */
  50
  51     size_t size_old = ba->nmemb * sizeof( ba->array );
  52     size_t size_new = nmemb_new * sizeof( ba->array );
  53
  54     ba->array = ( ushort * ) mem_resize_zero( ( void * ) ba->array, size_old, size_new );
  55     ba->nmemb = nmemb_new;
  56 }
  57
  58
  59 void barray_print( barray *ba )
  60 {
  61     /* Martin A. Hansen, November 2008. */
  62
  63     /* Debug function to print the content of a byte array. */
  64
  65     int i;
  66
  67     printf( "\nba->nmemb: %zu   ba->end: %zu\n", ba->nmemb, ba->end );
  68
  69     for ( i = 0; i < ba->nmemb; i++ ) {
  70         printf( "%d: %d\n", i, ba->array[ i ] );
  71     }
  72 }
  73
  74
  75 void barray_interval_inc( barray *ba, size_t beg, size_t end, ushort score )
  76 {
  77     /* Martin A. Hansen, November 2008. */
  78
  79     /* Increments a given interval of a byte array with a given score.
  80      * Resizes the byte array if needed. */
  81
  82     assert( beg >= 0 );
  83     assert( end >= 0 );
  84     assert( end >= beg );
  85     assert( score > 0 );
  86
  87     if ( end > ba->nmemb ) {
  88         barray_resize( ba, barray_new_size( end ) );
  89     }
  90
  91     size_t i = 0;
  92
  93     for ( i = beg; i <= end; i++ ) {
  94         ba->array[ i ] += score;
  95     }
  96
  97     ba->end = MAX( ba->end, end );
  98 }
  99
 100
 101 bool barray_interval_scan( barray *ba, size_t *pos_pt, size_t *beg_pt, size_t *end_pt )
 102 {
 103     /* Martin A. Hansen, November 2008. */
 104
 105     /* Scan a byte array from a given position
 106      * for the next interval of non-zero values. */
 107
 108     size_t pos = *pos_pt;
 109     size_t beg = *beg_pt;
 110     size_t end = *end_pt;
 111
 112     if ( pos > ba->end || ba->end == 0 ) {
 113         return FALSE;
 114     }
 115
 116     while ( pos < ba->end && ba->array[ pos ] == 0 ) {
 117         pos++;
 118     }
 119
 120     beg = pos;
 121
 122     while ( pos <= ba->end && ba->array[ pos ] != 0 ) {
 123         pos++;
 124     }
 125
 126     end = pos;
 127
 128
 129     if ( end >= beg )
 130     {
 131         *pos_pt = pos;
 132         *beg_pt = beg;
 133         *end_pt = end - 1;
 134
 135         return TRUE;
 136     }
 137
 138     return FALSE;
 139 }
 140
 141
 142 ushort barray_interval_max( barray *ba, size_t beg, size_t end )
 143 {
 144     /* Martin A. Hansen, December 2008. */
 145
 146     /* Locate the max value in an interval within a byte array. */
 147
 148     size_t i   = 0;
 149     ushort max = 0;
 150
 151     for ( i = beg; i <= end; i++ ) {
 152         max = MAX( max, ba->array[ i ] );
 153     }
 154
 155     return max;
 156 }
 157
 158
 159 void barray_destroy( barray **ba_ppt )
 160 {
 161     /* Martin A. Hansen, November 2008. */
 162
 163     /* Deallocates a byte array and set it to NULL. */
 164
 165     barray *ba = *ba_ppt;
 166
 167     mem_free( ba->array );
 168     mem_free( ba );
 169
 170     ba      = NULL;
 171     *ba_ppt = NULL;
 172 }