/* ********************************************************** * Copyright 2012 VMware, Inc. All rights reserved. * **********************************************************/ /* * @VMKAPIMOD_LICENSE@ */ /* *********************************************************************** * BitVector */ /** * * \addtogroup Lib * @{ * \defgroup vmk_BitVector Bit Vector Manipulation * * Utility interfaces for managing a Bit Vector. * \par Example - Using VMK_BITVECTOR_ITERATE or VMK_BITVECTOR_ITERATE_AND_CLEAR * and VMK_BITVECTOR_ENDITERATE * * \code * { * vmk_uint32 n; * VMK_BITVECTOR_ITERATE(_bv,n) { * printf("%d is in set\n",n); * } * VMK_BITVECTOR_ENDITERATE() * } * \endcode * * @{ *********************************************************************** */ #ifndef _VMKAPI_BITVECTOR_H_ #define _VMKAPI_BITVECTOR_H_ /** \cond never */ #ifndef VMK_HEADER_INCLUDED_FROM_VMKAPI_H #error This vmkapi file should never be included directly but only via vmkapi.h #endif /** \endcond never */ /** * \brief Incomplete Abstract Data type allocated to be larger than * sizeof(vmk_BitVector). Should only be allocated by * vmk_BitVectorAlloc. * Clients should only use the returned pointer. */ typedef struct vmk_BitVector { vmk_uint32 n; vmk_uint32 nwords; vmk_uint32 vector[1]; } vmk_BitVector; /* ******************************************************************************* * vmk_BitVectorSize -- */ /** * * \brief Size of vmk_BitVector for a given number of bits * * \param[in] n Number of bits to size for * * \retval size calculation of a vmk_BitVector * ******************************************************************************* */ #define vmk_BitVectorSize(n) \ (sizeof(vmk_uint32) /* n */ + \ sizeof(vmk_uint32) /* nwords */ + \ ((n + 31) / 32) * sizeof(vmk_uint32)) /* n bits rounded up to words */ /* ******************************************************************************* * vmk_BitVectorAllocWithTimeout -- */ /** * * \brief Allocate a bitvector with timeout * * \param[in] heap vmk_HeapID to allocate the vmk_BitVector from * \param[in] n Total number of bits to allocate for * \param[in] timeoutMs vmk_BitVector to set a bit * * \note If timeoutMS is not 0 then the allocation may block if the * heap needs to expand to accomodate the request. * * \retval vmk_BitVector pointer or NULL. * ******************************************************************************* */ vmk_BitVector* vmk_BitVectorAllocWithTimeout(vmk_HeapID heap, vmk_uint32 n, vmk_uint32 timeoutMs); /* ******************************************************************************* * vmk_BitVectorAlloc -- */ /** * * \brief Allocate a bitvector * * \param[in] heap vmk_HeapID to allocate the vmk_BitVector from * \param[in] n Total number of bits to allocate for * * \retval vmk_BitVector pointer or NULL. * ******************************************************************************* */ vmk_BitVector* vmk_BitVectorAlloc(vmk_HeapID heap, vmk_uint32 n); /* ******************************************************************************* * vmk_BitVectorDuplicate -- */ /** * * \brief Allocate a vmk_BitVector and initialise it from another vmk_BitVector * * \param[in] heap vmk_HeapID to allocate the vmk_BitVector from * \param[in] src Source vmk_BitVector to copy into the new vmk_BitVector * * \retval new vmk_BitVector pointer * ******************************************************************************* */ vmk_BitVector* vmk_BitVectorDuplicate(vmk_HeapID heap, const vmk_BitVector *src); /* ******************************************************************************* * vmk_BitVectorFree -- */ /** * * \brief Free a vmk_BitVector * * \param[in] heap vmk_HeapID to free the vmk_BitVector to * \param[in] bv vmk_BitVector to free * * \retval If the previous value of this bit was zero then zero is returned * otherwise non-zero is returned. * ******************************************************************************* */ void vmk_BitVectorFree(vmk_HeapID heap, vmk_BitVector *bv); /* ******************************************************************************* * vmk_BitVectorSet -- */ /** * * \brief Set a bit in a vmk_BitVector * * \param[in] bv vmk_BitVector to set a bit * \param[in] n Bit to set * ******************************************************************************* */ static inline void vmk_BitVectorSet(vmk_BitVector *bv, vmk_uint32 n) { VMK_ASSERT(n < bv->n); asm volatile("btsl %1, (%0)" :: "r" (bv->vector), "r" (n) : "cc", "memory"); } /* ******************************************************************************* * vmk_BitVectorClear -- */ /** * * \brief Clear a bit in a vmk_BitVector * * \param[in] bv vmk_BitVector to clear a bit * \param[in] n Bit to set * ******************************************************************************* */ static inline void vmk_BitVectorClear(vmk_BitVector *bv, vmk_uint32 n) { VMK_ASSERT(n < bv->n); asm volatile("btrl %1, (%0)" :: "r" (bv->vector), "r" (n) : "cc", "memory"); } /* ******************************************************************************* * vmk_BitVectorTest -- */ /** * * \brief Test if a bit in a vmk_BitVector is set * * \param[in] bv vmk_BitVector to check * \param[in] n Bit to check * * \retval If this bit is set, non-zero is returned. * ******************************************************************************* */ static inline int vmk_BitVectorTest(const vmk_BitVector *bv, vmk_uint32 n) { VMK_ASSERT(n < bv->n); { vmk_uint32 tmp; asm("btl %2, (%1); " "sbbl %0, %0" : "=r" (tmp) : "r" (bv->vector), "r" (n) : "cc"); return tmp; } } /* ******************************************************************************* * vmk_BitVectorAtomicTestAndSet -- */ /** * * \brief Atomically read bit n and set it * * \param[in] bv vmk_BitVector to set a bit * \param[in] n Bit to set * * \retval If the previous value of this bit was zero then zero is returned * otherwise non-zero is returned. * ******************************************************************************* */ static inline int vmk_BitVectorAtomicTestAndSet(const vmk_BitVector *bv, vmk_uint32 n) { VMK_ASSERT(n < bv->n); { vmk_uint32 tmp; asm volatile("lock; btsl %2, (%1); " "sbbl %0, %0" : "=r" (tmp) : "r" (bv->vector), "r" (n) : "cc", "memory"); return tmp; } } /* ******************************************************************************* * vmk_BitVectorAtomicTestAndClear -- */ /** * * \brief Atomically read bit n and clear it * * \param[in] bv vmk_BitVector to operate on * \param[in] n Bit to clear * * \retval If the previous value of this bit was zero then zero is returned * otherwise non-zero is returned. * ******************************************************************************* */ static inline int vmk_BitVectorAtomicTestAndClear(const vmk_BitVector *bv, vmk_uint32 n) { VMK_ASSERT(n < bv->n); { vmk_uint32 tmp; asm volatile("lock; btrl %2, (%1); " "sbbl %0, %0" : "=r" (tmp) : "r" (bv->vector), "r" (n) : "cc", "memory"); return tmp; } } /* ******************************************************************************* * vmk_BitVectorZap -- */ /** * * \brief Removes all entries from the set * * \param[in] bv vmk_BitVector to zap * ******************************************************************************* */ static inline void vmk_BitVectorZap(vmk_BitVector *bv) { vmk_Memset(bv->vector, 0, bv->nwords * sizeof(bv->vector[0])); } /* ******************************************************************************* * vmk_BitVectorFill -- */ /** * * \brief Set all bits in a vmk_BitVector * * \param[in] bv vmk_BitVector to operate on * ******************************************************************************* */ static inline void vmk_BitVectorFill(vmk_BitVector *bv) { vmk_Memset(bv->vector, 0xff, bv->nwords * sizeof(bv->vector[0])); } /* ******************************************************************************* * vmk_BitVectorGetRef -- */ /** * * \brief Get a pointer to a particular byte in vmk_BitVector * * \param[in] bv vmk_BitVector to look inside * \param[in] start Starting byte return * \param[in] nbytes Number of bytes expected to be used * * \note nbytes is only checked in debug builds * * \retval Pointer to a vmk_unit8. * ******************************************************************************* */ static inline vmk_uint8 * vmk_BitVectorGetRef(const vmk_BitVector *bv, vmk_uint32 start, vmk_uint32 nbytes) { vmk_uint8 *ptr = (vmk_uint8 *)bv->vector; (void)nbytes; VMK_ASSERT((start + nbytes) <= bv->nwords * sizeof(bv->vector[0])); return &ptr[start]; } /* ******************************************************************************* * vmk_BitVectorNumBitsSet -- */ /** * * \brief Return the number of set bits in this vmk_BitVector * * \param[in] bv vmk_BitVector to count * * \retval number of bits set in this vmk_BitVector * ******************************************************************************* */ vmk_uint32 vmk_BitVectorNumBitsSet(const vmk_BitVector *bv); /* ******************************************************************************* * vmk_BitVectorIsZero -- */ /** * * \brief Check if a vmk_BitVector has no bits set * * \param[in] bv vmk_BitVector to check * * \retval non-zero if any bit is set in the vmk_BitVector * ******************************************************************************* */ vmk_uint32 vmk_BitVectorIsZero(const vmk_BitVector *bv); /* ******************************************************************************* * vmk_BitVectorNextBit -- */ /** * * \brief Find next bit set in a vmk_BitVector * * \param[in] bv vmk_BitVector to check * \param[in] start Bit to start searching from * \param[in] state VMK_TRUE if looking for set bits * \param[out] pos Filled in with index of the next bit * * \retval VMK_TRUE if a bit was found * * \note The value of "pos" must not be used if VMK_FALSE is returned. * ******************************************************************************* */ vmk_Bool vmk_BitVectorNextBit(const vmk_BitVector *bv, vmk_uint32 start, vmk_Bool state, vmk_uint32 *pos); /* ******************************************************************************* * vmk_BitVectorPrevBit -- */ /** * * \brief Find previous bit set in a vmk_BitVector, searching backwards * * \param[in] bv vmk_BitVector to check * \param[in] start Bit to start searching from * \param[in] state VMK_TRUE if looking for set bits * \param[out] pos Filled in with index of the next bit * * \retval VMK_TRUE if a bit was found * * \note BitVectors are implemented as an array of vmk_uint32 which affects * byte ordering on little endian architectures, such as x86. * * \note The value of "pos" must not be used if VMK_FALSE is returned. * ******************************************************************************* */ vmk_Bool vmk_BitVectorPrevBit(const vmk_BitVector *bv, vmk_uint32 start, vmk_Bool state, vmk_uint32 *pos); /* ******************************************************************************* * vmk_BitVectorGetExtent -- */ /** * * \brief Find sequence of bits in a vmk_BitVector * * \param[in] bv vmk_BitVector to check * \param[in] start Bit to start searching from * \param[out] set Is start bit set or not * \param[out] length Filled in with index of the next bit * * \note BitVectors are implemented as an array of vmk_uint32 which affects * byte ordering on little endian architectures, such as x86. * ******************************************************************************* */ void vmk_BitVectorGetExtent(const vmk_BitVector *bv, vmk_uint32 start, vmk_Bool *set, vmk_uint32 *length); /* ******************************************************************************* * vmk_BitVectorNextExtent -- */ /** * * \brief Find next sequence of bits in a vmk_BitVector * * \param[in] bv vmk_BitVector to check * \param[in] startSearch Bit to start searching from * \param[in] set VMK_TRUE if looking for set bits * \param[out] startRun Start index of extend found * \param[out] length Length of extent found * * \retval VMK_TRUE if a bit was found * * \note BitVectors are implemented as an array of vmk_uint32 which affects * byte ordering on little endian architectures, such as x86. * * \note The values of "startRun" and "length" must not be used if VMK_FALSE * is returned. * ******************************************************************************* */ vmk_Bool vmk_BitVectorNextExtent(const vmk_BitVector *bv, vmk_uint32 startSearch, vmk_Bool set, vmk_uint32 *startRun, vmk_uint32 *length); /* ******************************************************************************* * vmk_BitVectorSetExtent -- */ /** * * \brief Set an extent of a bitvector to a particular state * * \param[in] bv vmk_BitVector to set a bit * \param[in] startRun Bit to start setting from * \param[in] length Number of bits to set * \param[in] state VMK_TRUE if setting to 1 * * \retval If setting to 1, returns a positive count number of bits set, * otherwise returns a negative count of the number of bits set. * ******************************************************************************* */ int vmk_BitVectorSetExtent(vmk_BitVector *bv, vmk_uint32 startRun, vmk_uint32 length, vmk_Bool state); /* ******************************************************************************* * vmk_BitVectorSetExtentFast -- */ /** * * \brief Set an extent of a bitvector to 1 * * \param[in] bv vmk_BitVector to set a bit * \param[in] startRun Bit to start setting from * \param[in] length Number of bits to set * ******************************************************************************* */ void vmk_BitVectorSetExtentFast(vmk_BitVector *bv, vmk_uint32 startRun, vmk_uint32 length); /* ******************************************************************************* * vmk_BitVectorMerge -- */ /** * * \brief Merge two sets of vmk_BitVector * * \param[in] src vmk_BitVector merged into dest * \param[in,out] dest vmk_BitVector modified by src * * \retval number of bits merged from src to dest that were not previously set. * ******************************************************************************* */ vmk_uint32 vmk_BitVectorMerge(vmk_BitVector *src, vmk_BitVector *dest); /* ******************************************************************************* * vmk_BitVectorMergeAtOffset -- */ /** * * \brief Merge two sets of vmk_BitVector from specific offset * * This function merges bits from the start of one vmk_BitVector into another, * starting the merge at a specific offset in the destination vector. Bits set * in the source vector that would go beyond the size of dest are ignored. * * \param[in] src vmk_BitVector merged into dest * \param[in,out] dest vmk_BitVector modified by src * \param[in] offset Bit position to write bits from src into * ******************************************************************************* */ void vmk_BitVectorMergeAtOffset(vmk_BitVector *src, vmk_BitVector *dest, vmk_uint32 offset); /* ******************************************************************************* * vmk_BitVectorMaxSize -- */ /** * * \brief Returns the maximum number of bits that can be held in a vmk_BitVector * * \retval maximum number of bits that can be held in a vmk_BitVector * ******************************************************************************* */ vmk_uint32 vmk_BitVectorMaxSize(void); /* ******************************************************************************* * VMK_BITVECTOR_ITERATE -- */ /** * * \brief Macro to iterate a vmk_BitVector * * \param[in] _bv vmk_BitVector to iterate across * \param[in] _n Variable set to each valid bit each iteration * * \retval If the previous value of this bit was zero then zero is returned * otherwise non-zero is returned. * ******************************************************************************* */ #define VMK_BITVECTOR_ITERATE(_bv,_n) { \ vmk_uint32 _index; \ for (_index=0;_index <(_bv)->nwords;_index++) { \ vmk_uint32 _off,_vals; \ _vals = (_bv)->vector[_index]; \ while(_vals) { \ __asm ("bsfl %1,%0\n\t" \ "btrl %0,%1" \ : "=r" (_off), "+g" (_vals) \ : : "cc" ); \ _n = (_index * 32) + _off; \ if (_n >= (_bv)->n) { \ break; \ } \ /* ******************************************************************************* * VMK_BITVECTOR_ITERATE_AND_CLEAR -- */ /** * * \brief Macro to iterate a vmk_BitVector, clearing it as well * * \param[in] _bv vmk_BitVector to iterate across * \param[in] _n Variable set to each valid bit each iteration * * \retval If the previous value of this bit was zero then zero is returned * otherwise non-zero is returned. * * \note The state of the vmk_BitVector during the iteration is undefined * ******************************************************************************* */ #define VMK_BITVECTOR_ITERATE_AND_CLEAR(_bv,_n) { \ vmk_uint32 _index; \ for (_index=0;_index <(_bv)->nwords;_index++) { \ vmk_uint32 _off,_vals; \ _vals = (_bv)->vector[_index]; \ (_bv)->vector[_index] = 0; \ while(_vals) { \ __asm ("bsfl %1,%0\n\t" \ "btrl %0,%1" \ : "=r" (_off), "+g" (_vals) \ : : "cc"); \ _n = (_index * 32) + _off; \ if (_n >= (_bv)->n) { \ break; \ } \ /* ******************************************************************************* * VMK_BITVECTOR_ENDITERATE -- */ /** * * \brief Macro to end a iteration zone * * Can be used with either VMK_BITVECTOR_ITERATE() or * VMK_BITVECTOR_ITERATE_AND_CLEAR() * ******************************************************************************* */ #define VMK_BITVECTOR_ENDITERATE() }}} #endif /* _VMKAPI_BITVECTOR_H_ */ /** @} */ /** @} */