bitfield.h

openPBS的开放源代码

/* $Id: bitfield.h,v 1.1.6.1 2000/08/09 00:18:37 hender Exp $ */

/*
*         OpenPBS (Portable Batch System) v2.3 Software License
* 
* Copyright (c) 1999-2000 Veridian Information Solutions, Inc.
* All rights reserved.
* 
* ---------------------------------------------------------------------------
* For a license to use or redistribute the OpenPBS software under conditions
* other than those described below, or to purchase support for this software,
* please contact Veridian Systems, PBS Products Department ("Licensor") at:
* 
*    www.OpenPBS.org  [phone]                  [e-mail]
*                        877 902-4PBS (US toll-free)
* ---------------------------------------------------------------------------
* 
* This license covers use of the OpenPBS v2.3 software (the "Software") at
* your site or location, and, for certain users, redistribution of the
* Software to other sites and locations.  Use and redistribution of
* OpenPBS v2.3 in source and binary forms, with or without modification,
* are permitted provided that all of the following conditions are met.
* After December 31, 2001, only conditions 3-6 must be met:
* 
* 1. Commercial and/or non-commercial use of the Software is permitted
*    provided a current software registration is on file at www.OpenPBS.org.
*    If use of this software contributes to a publication, product, or
*    service, proper attribution must be given; see www.OpenPBS.org/credit.html
* 
* 2. Redistribution in any form is only permitted for non-commercial,
*    non-profit purposes.  There can be no charge for the Software or any
*    software incorporating the Software.  Further, there can be no
*    expectation of revenue generated as a consequence of redistributing
*    the Software.
* 
* 3. Any Redistribution of source code must retain the above copyright notice
*    and the acknowledgment contained in paragraph 6, this list of conditions
*    and the disclaimer contained in paragraph 7.
* 
* 4. Any Redistribution in binary form must reproduce the above copyright
*    notice and the acknowledgment contained in paragraph 6, this list of
*    conditions and the disclaimer contained in paragraph 7 in the
*    documentation and/or other materials provided with the distribution.
* 
* 5. Redistributions in any form must be accompanied by information on how to
*    obtain complete source code for the OpenPBS software and any
*    modifications and/or additions to the OpenPBS software.  The source code
*    must either be included in the distribution or be available for no more
*    than the cost of distribution plus a nominal fee, and all modifications
*    and additions to the Software must be freely redistributable by any party
*    (including Licensor) without restriction.
* 
* 6. All advertising materials mentioning features or use of the Software must
*    display the following acknowledgment:
* 
*     "This product includes software developed by NASA Ames Research Center,
*     Lawrence Livermore National Laboratory, and Veridian Information 
*     Solutions, Inc.
*     Visit www.OpenPBS.org for OpenPBS software support,
*     products, and information."
* 
* 7. DISCLAIMER OF WARRANTY
* 
* THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND. ANY EXPRESS
* OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT
* ARE EXPRESSLY DISCLAIMED.
* 
* IN NO EVENT SHALL VERIDIAN CORPORATION, ITS AFFILIATED COMPANIES, OR THE
* U.S. GOVERNMENT OR ANY OF ITS AGENCIES BE LIABLE FOR ANY DIRECT OR 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.
* 
* This license will be governed by the laws of the Commonwealth of Virginia,
* without reference to its choice of law rules.
*/

#if PE_MASK != 0

/*
 *
 * Definition of interface for dealing with arbitrarily large numbers of
 * contiguous bits.  Size of the bitfield is declared at compile time with
 * the BITFIELD_SIZE #define (default is 128 bits).
 * 
 * Macros/inlines all take pointers to a Bitfield, and provide :
 * 
 * Macro BITFIELD_CLRALL(Bitfield *p)
 * Macro BITFIELD_SETALL(Bitfield *p)
 * 	Clear or set all bits in a Bitfield.
 * 
 * Macro BITFIELD_SET_LSB(Bitfield *p)
 * Macro BITFIELD_CLR_LSB(Bitfield *p)
 * Macro BITFIELD_SET_MSB(Bitfield *p)
 * Macro BITFIELD_CLR_MSB(Bitfield *p)
 *	Set the least or most significant bit of a Bitfield.
 * 
 * Macro BITFIELD_LSB_ISONE(Bitfield *p)
 * Macro BITFIELD_MSB_ISONE(Bitfield *p)
 * 	Equals non-zero if the least or most significant bit of the Bitfield
 * 	    is set, or zero otherwise.
 *
 * Macro BITFIELD_SETB(Bitfield *p, int bit)
 * Macro BITFIELD_CLRB(Bitfield *p, int bit)
 * Macro BITFIELD_TSTB(Bitfield *p, int bit)
 * 	Set, clear, or test the bit at position 'bit' in the Bitfield '*p'.
 * 	BITFIELD_TSTB() is non-zero if the bit at position 'bit' is set, or
 *	     zero if it is clear.
 * 
 * Inline BITFIELD_IS_ZERO(Bitfield *p)
 * Inline BITFIELD_IS_ONES(Bitfield *p)
 * 	Return non-zero if the bitfield is composed of all zeros or ones,
 *	     or zero if the bitfield is non-homogeneous.
 * 
 * Inline BITFIELD_IS_NONZERO(Bitfield *p)
 *	Returns non-zero if the bitfield contains at least one set bit.
 *
 * Inline BITFIELD_NUM_ONES(Bitfield *p)
 *	Returns number of '1' bits in the bitfield.
 * 
 * Inline BITFIELD_MS_ONE(Bitfield *p)
 * Inline BITFIELD_LS_ONE(Bitfield *p)
 *	Returns bit position number of least or most significant 1-bit in
 *	the Bitfield.
 * 
 * Inline BITFIELD_EQ(Bitfield *p, Bitfield *q)
 * Inline BITFIELD_NOTEQ(Bitfield *p, Bitfield *q)
 *	Return non-zero if Bitfields '*p' and '*q' are (not) equal.
 * 
 * Inline BITFIELD_SETM(Bitfield *p, Bitfield *mask)
 * Inline BITFIELD_CLRM(Bitfield *p, Bitfield *mask)
 * Inline BITFIELD_ANDM(Bitfield *p, Bitfield *mask)
 * Inline BITFIELD_TSTM(Bitfield *p, Bitfield *mask)
 * Inline BITFIELD_TSTALLM(Bitfield *p, Bitfield *mask)
 *	Apply the specified 'mask' to the given bitfield 'p':
 *	SETM() sets bits in 'p' for any bits set in 'mask' ('p |= mask').
 *	CLRM() clears bits in 'p' for any bits set in 'mask' ('p &=~ mask').
 *	ANDM() logical-and's 'mask' into 'p' ('p &= mask');
 *	TSTM() returns non-zero if *any* bits set in 'mask' are set in 'p'.
 *	TSTMALL() returns non-zero if *all* bits set in 'mask' are also set 
 *		in 'p'.
 * 
 * Inline BITFIELD_CPY(Bitfield *p, Bitfield *q)
 * Inline BITFIELD_CPYNOTM(Bitfield *p, Bitfield *q)
 *	Copy the (inverse of) bitfield 'q' into 'p'.
 * 
 * Inline BITFIELD_ORNOTM(Bitfield *p, Bitfield *q)
 * 	Set any bits in 'p' where the corresponding bit in 'q' is clear.
 * 	    (p |= ~q)
 * 
 * Inline BITFIELD_SHIFTL(Bitfield *p)
 * Inline BITFIELD_SHIFTR(Bitfield *p)
 * 	Shift the bits in Bitfield 'p' one bit to the right or left.
 */

#ifndef	BITFIELD_H_
#define	BITFIELD_H_

/* The size of bitfields being used.  Default to 128 bits. */
#ifndef BITFIELD_SIZE
#define	BITFIELD_SIZE		544
#endif	/* !BITFIELD_SIZE */

#include <assert.h>
#define BITFIELD_BPW		((int)(sizeof (unsigned long long) * 8))
#define BITFIELD_SHIFT(bit)	((bit) / BITFIELD_BPW)
#define BITFIELD_OFFSET(bit)	((bit) & (BITFIELD_BPW - 1))
#define	BITFIELD_WORDS		(BITFIELD_SHIFT(BITFIELD_SIZE))

typedef struct bitfield {
	unsigned long long _bits[BITFIELD_WORDS];
} Bitfield;

#if defined(sgi)
#  define INLINE __inline 
#else
#  define INLINE
#endif

/* Operate on least significant bit of a bitfield. */

#define	BITFIELD_LSB_ISONE(p) \
    ((p)->_bits[0] & 1ULL)

#define	BITFIELD_SET_LSB(p) \
    ((p)->_bits[0] |= 1ULL)

#define	BITFIELD_CLR_LSB(p) \
    ((p)->_bits[0] &= ~(1ULL))


/* Operate on most significant bit of a bitfield. */

#define BITFIELD_MSB_ISONE(p) \
    ((p)->_bits[BITFIELD_SHIFT(BITFIELD_SIZE-1)] & (1ULL << (BITFIELD_BPW-1)))

#define BITFIELD_SET_MSB(p) \
    ((p)->_bits[BITFIELD_SHIFT(BITFIELD_SIZE-1)] |= (1ULL << (BITFIELD_BPW-1)))

#define BITFIELD_CLR_MSB(p) \
    ((p)->_bits[BITFIELD_SHIFT(BITFIELD_SIZE-1)] &= ~(1ULL << (BITFIELD_BPW-1)))


/* Operate on arbitrary bits within the bitfield. */

#define BITFIELD_SETB(p,bit)	(((bit) >= 0 && (bit) < BITFIELD_SIZE) ? \
    (p)->_bits[BITFIELD_SHIFT(bit)] |= (1ULL << BITFIELD_OFFSET(bit)) : 0)

#define BITFIELD_CLRB(p,bit)	(((bit) >= 0 && (bit) < BITFIELD_SIZE) ? \
    (p)->_bits[BITFIELD_SHIFT(bit)] &= ~(1ULL << BITFIELD_OFFSET(bit)) : 0)

#define BITFIELD_TSTB(p,bit)	(((bit) >= 0 && (bit) < BITFIELD_SIZE) ? \
    ((p)->_bits[BITFIELD_SHIFT(bit)] & (1ULL << BITFIELD_OFFSET(bit))) : 0)


/* Clear or set all the bits in the bitfield. */

#define BITFIELD_CLRALL(p)	{					\
	int w;								\
	assert(p != NULL);						\
	for (w = 0; w < BITFIELD_WORDS; w++)				\
		(p)->_bits[w] = 0ULL;					\
}

#define BITFIELD_SETALL(p)	{					\
	int w;								\
	assert(p != NULL);						\
	for (w = 0; w < BITFIELD_WORDS; w++)				\
		(p)->_bits[w] = ~(0ULL);				\
}


/* Comparison functions for two bitfield. */

INLINE int BITFIELD_IS_ZERO(Bitfield *p)		{
	int w;
	assert(p != NULL);
	for (w = 0; w < BITFIELD_WORDS; w++)
		if ((p)->_bits[w])
			return 0;
	return 1;
}

INLINE int BITFIELD_IS_ONES(Bitfield *p)		{
	int w;
	assert(p != NULL);
	for (w = 0; w < BITFIELD_WORDS; w++)
		if ((p)->_bits[w] != ~(0ULL))
			return 0;
	return 1;
}

INLINE int BITFIELD_IS_NONZERO(Bitfield *p)		{
	int w;
	assert(p != NULL);
	for (w = 0; w < BITFIELD_WORDS; w++)
		if ((p)->_bits[w])
			return 1;
	return 0;
}

INLINE int BITFIELD_NUM_ONES(Bitfield *p)		{
	int w, cnt;
	unsigned long long n;
	assert(p != NULL);

	cnt = 0;
	for (w = 0; w < BITFIELD_WORDS; w++)
		for (n = (p)->_bits[w]; n != 0ULL; cnt++)
			n &= (n - 1);

	return (cnt);
}

INLINE int BITFIELD_LS_ONE(Bitfield *p)			{
	int w, bit;
	unsigned long long n, x;
	assert(p != NULL);

	bit = 0;
	for (w = 0; w < BITFIELD_WORDS; w++) {
		n = (p)->_bits[w];

		/* Look for the first non-zero word. */
		if (n != 0ULL)
			break;
			
		bit += BITFIELD_BPW;
	}

	/* No non-zero words found in the bitfield. */
	if (w == BITFIELD_WORDS)
		return (-1);

	/* Slide a single bit left, looking for the non-zero bit. */
	for (x = 1ULL; !(n & x); bit ++)
		x <<= 1;

	return (bit);
}

INLINE int BITFIELD_MS_ONE(Bitfield *p)			{
	int w, bit;
	unsigned long long n, x;
	assert(p != NULL);

	bit = BITFIELD_SIZE - 1;
	for (w = BITFIELD_WORDS - 1; w >= 0; w--) {
		n = (p)->_bits[w];

		/* Look for the first non-zero word. */
		if (n != 0ULL)
			break;
			
		bit -= BITFIELD_BPW;
	}

	/* No non-zero words found in the bitfield. */
	if (w < 0)
		return (-1);

	/* Slide a single bit right, looking for the non-zero bit. */
	for (x = 1ULL << BITFIELD_BPW - 1; !(n & x); bit--)
		x >>= 1;

	return (bit);
}

INLINE int BITFIELD_EQ(Bitfield *p, Bitfield *q)	{
	int w;
	assert(p != NULL && q != NULL);
	for (w = 0; w < BITFIELD_WORDS; w++)
		if ((p)->_bits[w] != (q)->_bits[w])
			return 0;
	return 1;
}

INLINE int BITFIELD_NOTEQ(Bitfield *p, Bitfield *q)	{
	int w;
	assert(p != NULL && q != NULL);
	for (w = 0; w < BITFIELD_WORDS; w++)
		if ((p)->_bits[w] != (q)->_bits[w])
			return 1;
	return 0;
}


/* Logical manipulation functions for applying one bitfield to another. */

INLINE int BITFIELD_SETM(Bitfield *p, Bitfield *mask)	{
	int w;
	assert(p != NULL && mask != NULL);
	for (w = 0; w < BITFIELD_WORDS; w++)
		(p)->_bits[w] |= (mask)->_bits[w];
	return 0;
}

INLINE int BITFIELD_CLRM(Bitfield *p, Bitfield *mask)	{
	int w;
	assert(p != NULL && mask != NULL);
	for (w = 0; w < BITFIELD_WORDS; w++)
		(p)->_bits[w] &= ~((mask)->_bits[w]);
	return 0;
}

INLINE int BITFIELD_ANDM(Bitfield *p, Bitfield *mask)	{
	int w;
	assert(p != NULL && mask != NULL);
	for (w = 0; w < BITFIELD_WORDS; w++)
		(p)->_bits[w] &= (mask)->_bits[w];
	return 0;
}

INLINE int BITFIELD_TSTM(Bitfield *p, Bitfield *mask)	{
	int w;
	assert(p != NULL && mask != NULL);
	for (w = 0; w < BITFIELD_WORDS; w++)
		if ((p)->_bits[w] & (mask)->_bits[w])
			return 1;
	return 0;
}

INLINE int BITFIELD_TSTALLM(Bitfield *p, Bitfield *mask) {
	int w;
	assert(p != NULL && mask != NULL);
	for (w = 0; w < BITFIELD_WORDS; w++)
		if (((p)->_bits[w] & (mask)->_bits[w]) != (mask)->_bits[w])
			return 0;
	return 1;
}

INLINE int BITFIELD_CPY(Bitfield *p, Bitfield *q)	{
	int w;
	assert(p != NULL && q != NULL);
	for (w = 0; w < BITFIELD_WORDS; w++)
		(p)->_bits[w] = (q)->_bits[w];
	return 0;
}

INLINE int BITFIELD_CPYNOTM(Bitfield *p, Bitfield *q)	{
	int w;
	assert(p != NULL && q != NULL);
	for (w = 0; w < BITFIELD_WORDS; w++)
		(p)->_bits[w] = ~((q)->_bits[w]);
	return 0;
}

INLINE int BITFIELD_ORNOTM(Bitfield *p, Bitfield *q)	{
	int w;
	assert(p != NULL && q != NULL);
	for (w = 0; w < BITFIELD_WORDS; w++)
		(p)->_bits[w] |= ~((q)->_bits[w]);
	return 0;
}


/* Logical shift left and shift right for bitfield. */

INLINE int BITFIELD_SHIFTL(Bitfield *p)			{
	int w, upper;
	assert(p != NULL);
	
	for (w = 0; w < BITFIELD_WORDS - 1; w++) {
		upper = (p->_bits[w] & (1ULL << (BITFIELD_BPW - 1))) ? 1 : 0;
		p->_bits[w] <<= 1;
		p->_bits[w + 1] <<= 1;
		p->_bits[w + 1] |= upper;
	}
	return 0;
}

INLINE int BITFIELD_SHIFTR(Bitfield *p)			{
	int w, lower;
	assert(p != NULL);
	
	for (w = BITFIELD_WORDS - 1; w > 0; w--) {
		lower = p->_bits[w] & 1ULL;
		p->_bits[w] >>= 1;
		p->_bits[w - 1] >>= 1;
		p->_bits[w - 1] |= (lower ? (1ULL << (BITFIELD_BPW - 1)) : 0);
	}
	return 0;
}

#endif	/* BITFIELD_H_ */
#endif /* PE_MASK */