ctrump/common/bitmap.h

Go to the documentation of this file.

/* -*- coding:utf-8 -*- 
 Copyright (c) 2009, Fixstars Corporation
 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 copyright notice,
     this list of conditions and the following disclaimer in the documentation
     and/or other materials provided with the distribution.
 
   * Neither the name of Fixstars Corporation nor the names of its 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 SUCH DAMAGE.
*/

#ifndef CTRUMP_COMMON_BITMAP_H
#define CTRUMP_COMMON_BITMAP_H

#include <strings.h>
#include <string.h>
#include "ctrump/common/dll.h"

#ifdef __cplusplus
extern "C" {
#endif

struct ctrump_mempool;
typedef unsigned int ctrump_bitmap_bits_t;
typedef ctrump_bitmap_bits_t *ctrump_bitmap_t;

#define BITMAP_NUM_BITS (sizeof(ctrump_bitmap_t)*8U)

#define BYTESIZE_OF_BITMAP(n) ((((n)+7U)/8U+sizeof(ctrump_bitmap_bits_t)-1U)&~(sizeof(ctrump_bitmap_bits_t)-1U))

#define WORDSIZE_OF_BITMAP(n) ((((n)+(BITMAP_NUM_BITS-1U))/BITMAP_NUM_BITS))

#define ctrump_bitmap_all_zero(bmp,nelem) memset(bmp, 0, BYTESIZE_OF_BITMAP(nelem))

CTRUMP_EXTDEF void ctrump_bitmap_or(ctrump_bitmap_t dest,
                                    ctrump_bitmap_t src0,
                                    ctrump_bitmap_t src1,
                                    unsigned int length);

CTRUMP_EXTDEF void ctrump_bitmap_nor(ctrump_bitmap_t dest,
                                     ctrump_bitmap_t src0,
                                     ctrump_bitmap_t src1,
                                     unsigned int length);

CTRUMP_EXTDEF void ctrump_bitmap_nand(ctrump_bitmap_t dest,
                                      ctrump_bitmap_t src0,
                                      ctrump_bitmap_t src1,
                                      unsigned int length);

CTRUMP_EXTDEF void ctrump_bitmap_and(ctrump_bitmap_t dest,
                                     ctrump_bitmap_t src0,
                                     ctrump_bitmap_t src1,
                                     unsigned int length);

/* dest = (src0 & ~src1) | src2 */
CTRUMP_EXTDEF void ctrump_bitmap_nand_or(ctrump_bitmap_t dest,
                                         ctrump_bitmap_t src0,
                                         ctrump_bitmap_t src1,
                                         ctrump_bitmap_t src2,
                                         unsigned int length);

CTRUMP_EXTDEF void ctrump_bitmap_copy(ctrump_bitmap_t dest,
                                      ctrump_bitmap_t src,
                                      unsigned int length);

CTRUMP_EXTDEF int ctrump_bitmap_eq(ctrump_bitmap_t x,
                                   ctrump_bitmap_t y,
                                   unsigned int length);

CTRUMP_EXTDEF void ctrump_bitmap_tostr(char *buf,
                                       ctrump_bitmap_t x,
                                       unsigned int length);

CTRUMP_EXTDEF int ctrump_print_bitmap_stderr(ctrump_bitmap_t x, unsigned int length);

CTRUMP_EXTDEF int ctrump_bitmap_popcnt(ctrump_bitmap_t bmp, unsigned int length);

static inline int
ctrump_bitmap_ffs(ctrump_bitmap_t bmp, unsigned int length)
{
    unsigned int n = WORDSIZE_OF_BITMAP(length);
    unsigned int i;
    for (i=0; i<n; i++) {
        if (bmp[i]) {
            unsigned int ret = (__builtin_ffs(bmp[i])-1) + i*BITMAP_NUM_BITS;
            if (ret > length)
                return -1;
            return ret;
        }
    }
    return -1;
}

static inline void
ctrump_bitmap_set(ctrump_bitmap_t bmp, unsigned int idx)
{
    unsigned int wordpos = idx/(sizeof(ctrump_bitmap_bits_t)*8U);
    unsigned int bitpos = idx%(sizeof(ctrump_bitmap_bits_t)*8U);

    bmp[wordpos] |= (1<<bitpos);
}

static inline void
ctrump_bitmap_clear(ctrump_bitmap_t bmp, unsigned int idx)
{
    unsigned int wordpos = idx/(sizeof(ctrump_bitmap_bits_t)*8U);
    unsigned int bitpos = idx%(sizeof(ctrump_bitmap_bits_t)*8U);

    bmp[wordpos] &= ~(1<<bitpos);
}

static inline int
ctrump_bitmap_p(ctrump_bitmap_t bmp, unsigned int idx)
{
    unsigned int wordpos = idx/(sizeof(ctrump_bitmap_bits_t)*8U);
    unsigned int bitpos = idx%(sizeof(ctrump_bitmap_bits_t)*8U);

    return bmp[wordpos]&(1<<bitpos);
}

static inline void
ctrump_bitmap_clear_all(ctrump_bitmap_t bmp, unsigned int length)
{
    unsigned int n = WORDSIZE_OF_BITMAP(length);
    unsigned int i;
    for (i=0; i<n; i++) {
        bmp[i] = (ctrump_bitmap_bits_t)0;
    }
}

static inline void
ctrump_bitmap_set_all(ctrump_bitmap_t bmp, unsigned int length)
{
    unsigned int n = WORDSIZE_OF_BITMAP(length);
    unsigned int i;
    for (i=0; i<n; i++) {
        bmp[i] = ~(ctrump_bitmap_bits_t)0;
    }
}


#define BMP_P ctrump_bitmap_p
#define BMP_SET ctrump_bitmap_set

CTRUMP_EXTDEF ctrump_bitmap_t ctrump_bmp_alloc(unsigned int nbits, struct ctrump_mempool *pool);
CTRUMP_EXTDEF ctrump_bitmap_t ctrump_bmp_zero(unsigned int nbits, struct ctrump_mempool *pool);
CTRUMP_EXTDEF ctrump_bitmap_t ctrump_bmp_fill(unsigned int nbits, struct ctrump_mempool *pool);

#ifdef __cplusplus
}
#endif

#endif /* CTRUMP_COMMON_BITMAP_H */

---