MultiSource/Benchmarks/DOE-ProxyApps-C/Pathfinder/bitfield.c

/*************************************************************************
 *
 *        PathFinder: finding a series of labeled nodes within a
 *                two-layer directed, cyclic graph.
 *               Copyright (2013) Sandia Corporation
 *
 * Copyright (2013) Sandia Corporation. Under the terms of Contract 
 * DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government 
 * retains certain rights in this software.
 *
 * This file is part of PathFinder.
 * 
 * PathFinder is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * PathFinder is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with PathFinder.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Questions? Contact J. Brian Rigdon (jbrigdo@sandia.gov)
 *
 */

#include "bitfield.h"
#include "node.h"
#include <stdio.h>


/* --------
 * Bitfield is a mask around a character pointer. An array of character
 * pointers is allocated such that there is a sequence of available bits
 * equal in length to the number of nodes in a given graph. Bitfield
 * defines operations that check if a bit corresponding to a node index
 * is set. This is used by the graph traversal path finding algorithms
 * to determine if a node has been visited.
 */


/* constructor */
Bitfield *Bitfield_new(int bitsNeeded)
{
    int size = (bitsNeeded+7) / 8; /* CHAR_BIT; */
    Bitfield *new = malloc(sizeof(Bitfield));
    if ( !new )
        return(NULL);
    new->bitfield = calloc(size, sizeof(char));
    if ( !new->bitfield )
    {
        free(new);
        return(NULL);
    }

    new->bitsNeeded = bitsNeeded;
    return new;
} 

/* destructor */
void Bitfield_delete(Bitfield *this)
{
    if ( this )
    {
        if ( this->bitfield )
            free(this->bitfield);
        free(this);
    }
}

/* Returns true if the specified node has been visited */
bool Bitfield_nodeVisited(Bitfield *this, struct NodeStruct *node)
{
    int index = node->nodeCount >> 3;
    char byte = this->bitfield[index];
    char bit = 1 << (node->nodeCount & 0x07);
    bool set = byte & bit;

    this->bitfield[index] |= bit;

    /* printf ( "Inside Bitfield nodeVisited: Node: %d, index %d, byte %x, bit: %x\n",
             node->nodeCount, index, byte, bit ); */
    return(set);
}


/* Makes a byte-by-byte copy of the "from" bitfield */
Bitfield *Bitfield_copy(Bitfield *from)
{
    int i;

    if ( !from )
        return(NULL);

    Bitfield *new = Bitfield_new(from->bitsNeeded);
    if ( new )
    {
        for ( i = 0; i*8 < from->bitsNeeded; ++i )
            new->bitfield[i] = from->bitfield[i];
        return(new);
    }
    else
        return(NULL);
}


void Bitfield_clear(Bitfield *this)
{
    int size = (this->bitsNeeded+7) / 8;
    memset(this->bitfield, 0, size);
}