/* Copyright (c) 2000-2010, Dirk Krause All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. * Redistributions in binary form must reproduce the above opyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. * Neither the name of the Dirk Krause nor the names of contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF Sdkbf_ucharH DAMAGE. */ /** @file dkbf.c Bit field and bit matrix module. */ #include "dk.h" #include "dkmem.h" /** Inside the dkbf module. */ #define DK_BF_C 1 #include "dkbf.h" #line 52 "dkbf.ctr" /** Abbreviation. */ typedef unsigned char *dkbf_ucptr; /** Abbreviation. */ typedef unsigned char dkbf_uchar; /** Masks to access single bits in a byte. */ static unsigned char the_bits[] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 }; dk_bitfield_t * dkbf_open DK_P1(size_t, bits) { dk_bitfield_t *back = NULL; size_t bytes; if(bits) { bytes = (bits / 8) + 1; back = dk_new(dk_bitfield_t,1); if(back) { back->data = NULL; back->bits = bits; back->data = dk_new(dkbf_uchar,bytes); if(back->data) { DK_MEMRES((back->data),bytes) ; } else { dk_delete(back); back = NULL; } } } return back; } void dkbf_matrix_close DK_P1(dk_bitmatrix_t *,m) { unsigned char *ptr, **pptr; size_t i; if(m) { if(m->data) { pptr = m->data; for(i = 0; i < m->c; i++) { ptr = *pptr; dk_delete(ptr); pptr++; } pptr = m->data; dk_delete(pptr); } m->data = NULL; m->c = 0; m->r = 0; dk_delete(m); } } dk_bitmatrix_t * dkbf_matrix_open DK_P2(size_t,c, size_t,r) { dk_bitmatrix_t *back = NULL; size_t bytes_per_row = 0, i = 0; int ok; unsigned char **pptr; ok = 0; if((c > 0) && (r > 0)) { back = dk_new(dk_bitmatrix_t,1); if(back) { back->data = NULL; back->c = 0; back->r = 0; bytes_per_row = 1 + c / 8; back->data = dk_new(dkbf_ucptr,r); if(back->data) { pptr = back->data; for(i = 0; i < r; i++) { *(pptr++) = NULL; } pptr = back->data; ok = 1; for(i = 0; i < r; i++) { *pptr = dk_new(dkbf_uchar,bytes_per_row); if(!(*pptr)) { ok = 0; } pptr++; } back->c = c; back->r = r; } if(!ok) { dkbf_matrix_close(back); back = NULL; } } } return back; } void dkbf_matrix_set DK_P4(dk_bitmatrix_t *,bm, size_t,x, size_t,y, int,v) { size_t i1, i2; unsigned char *ptr; if(bm) { if((x < bm->c) && (y < bm->r)) { ptr = (bm->data)[y]; i1 = x / 8; i2 = x % 8; if(v) { ptr[i1] |= the_bits[i2]; } else { ptr[i1] &= (~(the_bits[i2])); } } } } int dkbf_matrix_get DK_P3(dk_bitmatrix_t *,bm, size_t,x, size_t,y) { int back = 0; unsigned char *ptr; size_t i1, i2; if(bm) { if((x < bm->c) && (y < bm->r)) { ptr = (bm->data)[y]; i1 = x / 8; i2 = x % 8; if(ptr[i1] & the_bits[i2]) { back = 1; } } } return back; } void dkbf_matrix_reset DK_P1(dk_bitmatrix_t *,bm) { size_t i, j, jmax; unsigned char *ptr, **pptr; if(bm) { pptr = bm->data; jmax = 1 + (bm->c) / 8; for(i = 0; i < bm->r; i++) { ptr = *(pptr++); for(j = 0; j < jmax; j++) { *(ptr++) = 0x00; } } } } /* Not optimized yet. Expand a graph way matrix. An entry set by dkbf_matrix_set(bm, x, y, 1) sets the bit in row y and column x. This means there is a directed edge from graph node y to graph node x. Graph way expansion means, if there is no direct way from y to x we have to check, whether there is a node j with (direct or indirect) ways from y to j and from j to x. We have to run several passes, we can stop after we have not found any new changes in a pass. */ int dkbf_matrix_expand DK_P1(dk_bitmatrix_t *,bm) { int back = 0; int must_continue = 0; int cc; size_t x, y, j; if(bm) { if(bm->r == bm->c) { back = 1; cc = 1; while(cc) { cc = 0; for(y = 0; y < bm->r; y++) { for(x = 0; x < bm->c; x++) { if(!dkbf_matrix_get(bm, x, y)) { must_continue = 1; for(j = 0; ((j < bm->r) && (must_continue)); j++) { if(dkbf_matrix_get(bm, j, y)) { if(dkbf_matrix_get(bm, x, j)) { dkbf_matrix_set(bm, x, y, 1); cc = 1; must_continue = 0; } } } } } } } } } return back; } void dkbf_close DK_P1(dk_bitfield_t *, bf) { char *ptr; if(bf) { ptr = (char *)(bf->data); if(ptr) { dk_delete(ptr); } bf->data = NULL; bf->bits = 0; dk_delete(bf); } } void dkbf_set DK_P3(dk_bitfield_t *, bf, size_t, bit, int, val) { size_t i1, i2; if(bf) { if((bf->bits) > bit) { i1 = bit / 8; i2 = bit % 8; if(val) { (bf->data)[i1] |= the_bits[i2]; } else { (bf->data)[i2] &= (~(the_bits[i2])); } } } } void dkbf_reset DK_P1(dk_bitfield_t *,bf) { size_t bytes, i; unsigned char *ptr; if(bf) { ptr = bf->data; bytes = 1 + (bf->bits) / 8; for(i = 0; i < bytes; i++) { *(ptr++) = 0x00; } } } int dkbf_get DK_P2(dk_bitfield_t *, bf, size_t, bit) { int back = 0; size_t i1, i2; if(bf) { if((bf->bits) > bit) { i1 = bit / 8; i2 = bit % 8; if( ( (bf->data)[i1] ) & (the_bits[i2]) ) { back = 1; } } } return back; }