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( "\nnmemb: %zu   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
  86     if ( end > ba->nmemb ) {
  87         barray_resize( ba, barray_new_size( end ) );
  88     }
  89
  90     size_t i = 0;
  91
  92     for ( i = beg; i <= end; i++ ) {
  93         ba->array[ i ] += score;
  94     }
  95
  96     ba->end = MAX( ba->end, end );
  97 }
  98
  99
 100 bool barray_interval_scan( barray *ba, size_t *pos_pt, size_t *beg_pt, size_t *end_pt )
 101 {
 102     /* Martin A. Hansen, November 2008. */
 103
 104     /* Scan a byte array from a given position
 105      * for the next interval of non-zero values. */
 106
 107     size_t pos = *pos_pt;
 108     size_t beg = *beg_pt;
 109     size_t end = *end_pt;
 110
 111     if ( pos > ba->end ) {
 112         return FALSE;
 113     }
 114
 115     while ( pos < ba->end && ba->array[ pos ] == 0 ) {
 116         pos++;
 117     }
 118
 119     beg = pos;
 120
 121     while ( pos <= ba->end && ba->array[ pos ] != 0 ) {
 122         pos++;
 123     }
 124
 125     end = pos;
 126
 127
 128     if ( end >= beg )
 129     {
 130         *pos_pt = pos;
 131         *beg_pt = beg;
 132         *end_pt = end - 1;
 133
 134         return TRUE;
 135     }
 136
 137     return FALSE;
 138 }
 139
 140
 141 void barray_destroy( barray **ba_ppt )
 142 {
 143     /* Martin A. Hansen, November 2008. */
 144
 145     /* Deallocates a byte array and set it to NULL. */
 146
 147     barray *ba = *ba_ppt;
 148
 149     mem_free( ba->array );
 150     mem_free( ba );
 151
 152     ba      = NULL;
 153     *ba_ppt = NULL;
 154 }