diff options
Diffstat (limited to 'libparc/parc/algol/parc_BitVector.c')
| -rwxr-xr-x | libparc/parc/algol/parc_BitVector.c | 409 |
1 files changed, 409 insertions, 0 deletions
diff --git a/libparc/parc/algol/parc_BitVector.c b/libparc/parc/algol/parc_BitVector.c new file mode 100755 index 00000000..578fd102 --- /dev/null +++ b/libparc/parc/algol/parc_BitVector.c @@ -0,0 +1,409 @@ +/* + * Copyright (c) 2017 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + */ +#include <config.h> + +#include <LongBow/runtime.h> + +#include <parc/algol/parc_Object.h> +#include <parc/algol/parc_BitVector.h> +#include <parc/algol/parc_Memory.h> + +#define BITS_PER_BYTE 8 +#define DEFAULT_BITARRAY_SIZE 1 +#define MAX_BIT_VECTOR_INDEX 8192 + +struct PARCBitVector { + // the number of bits allocated. + unsigned bitLength; + + // we track the number of "1"s set for fast computation + // <code>parcBitVector_NumberOfBitsSet()</code> + unsigned numberOfBitsSet; + + // optimize case where only one bit is set. + unsigned firstBitSet; + + // our backing memory. + uint8_t *bitArray; + + // Fill value to be used when extending a vector + int fillValue; +}; + +static void +_destroy(PARCBitVector **parcBitVector) +{ + parcMemory_Deallocate(&((*parcBitVector)->bitArray)); +} + +parcObject_ExtendPARCObject(PARCBitVector, _destroy, parcBitVector_Copy, NULL, NULL, NULL, NULL, NULL); + +parcObject_ImplementAcquire(parcBitVector, PARCBitVector); + +parcObject_ImplementRelease(parcBitVector, PARCBitVector); + +PARCBitVector * +parcBitVector_Create(void) +{ + PARCBitVector *parcBitVector = parcObject_CreateInstance(PARCBitVector); + assertNotNull(parcBitVector, "parcObject_CreateInstance returned NULL"); + + parcBitVector->bitArray = parcMemory_AllocateAndClear(DEFAULT_BITARRAY_SIZE); + assertNotNull(parcBitVector->bitArray, "parcMemory_AllocateAndClear(%d) returned NULL", DEFAULT_BITARRAY_SIZE); + parcBitVector->bitLength = DEFAULT_BITARRAY_SIZE * BITS_PER_BYTE; + parcBitVector->numberOfBitsSet = 0; + parcBitVector->firstBitSet = -1; + parcBitVector->fillValue = 0; + + return parcBitVector; +} + +PARCBitVector * +parcBitVector_Copy(const PARCBitVector *source) +{ + PARCBitVector *parcBitVector = parcObject_CreateInstance(PARCBitVector); + assertNotNull(parcBitVector, "parcObject_CreateInstance returned NULL"); + + size_t byteLength = source->bitLength / BITS_PER_BYTE; + parcBitVector->bitArray = parcMemory_Allocate(byteLength); + memcpy(parcBitVector->bitArray, source->bitArray, byteLength); + parcBitVector->bitLength = source->bitLength; + parcBitVector->numberOfBitsSet = source->numberOfBitsSet; + parcBitVector->firstBitSet = source->firstBitSet; + parcBitVector->fillValue = source->fillValue; + + return parcBitVector; +} + +bool +parcBitVector_Equals(const PARCBitVector *a, const PARCBitVector *b) +{ + bool equal = ((a->numberOfBitsSet == b->numberOfBitsSet) && + (a->firstBitSet == b->firstBitSet)); + + if (equal) { + int byteLength = a->bitLength / BITS_PER_BYTE; + if ((a->bitLength != b->bitLength) && + (b->bitLength < a->bitLength)) { + byteLength = b->bitLength / BITS_PER_BYTE; + } + equal = (memcmp(a->bitArray, b->bitArray, byteLength) == 0); + } + + return equal; +} + +static void +_parc_bit_vector_resize(PARCBitVector *parcBitVector, unsigned bit) +{ + assertNotNull(parcBitVector, "_parc_bit_vector_resize passed a NULL parcBitVector"); + assertTrue(bit < MAX_BIT_VECTOR_INDEX, "_parc_bit_vector_resize passed a bit index that's too large"); + + unsigned neededBits = bit + 1; + if (neededBits > parcBitVector->bitLength) { + int newSize = (neededBits / BITS_PER_BYTE) + ((neededBits % BITS_PER_BYTE) ? 1 : 0); + int oldSize = (parcBitVector->bitLength / BITS_PER_BYTE) + ((parcBitVector->bitLength % BITS_PER_BYTE) ? 1 : 0); + + uint8_t *newArray = parcMemory_Reallocate(parcBitVector->bitArray, newSize); + assertTrue(newArray, "parcMemory_Reallocate(%d) failed", newSize); + // Reallocate does not guarantee that additional memory is zero-filled. + memset((void *) &(newArray[oldSize]), parcBitVector->fillValue, newSize - oldSize); + + parcBitVector->bitArray = newArray; + assertNotNull(newArray, "parcMemory_Reallocate(%d) returned NULL", newSize); + parcBitVector->bitLength = newSize * BITS_PER_BYTE; + } +} + +int +parcBitVector_Get(const PARCBitVector *parcBitVector, unsigned bit) +{ + assertTrue(bit < MAX_BIT_VECTOR_INDEX, "parcBitVector_Set passed a bit index that's too large"); + + if ((parcBitVector == NULL) || (bit >= parcBitVector->bitLength)) { + return -1; + } + + int byte = bit / BITS_PER_BYTE; + int bitInByte = bit % BITS_PER_BYTE; + if ((parcBitVector->bitArray[byte] & (1 << bitInByte))) { + return 1; + } + + return 0; +} + +void +parcBitVector_Set(PARCBitVector *parcBitVector, unsigned bit) +{ + assertNotNull(parcBitVector, "parcBitVector_Set passed a NULL parcBitVector"); + assertTrue(bit < MAX_BIT_VECTOR_INDEX, "parcBitVector_Set passed a bit index that's too huge"); + if (bit >= parcBitVector->bitLength) { + _parc_bit_vector_resize(parcBitVector, bit); + } + int byte = bit / BITS_PER_BYTE; + int bitInByte = bit % BITS_PER_BYTE; + if (!(parcBitVector->bitArray[byte] & (1 << bitInByte))) { + parcBitVector->bitArray[byte] |= (1 << bitInByte); + parcBitVector->numberOfBitsSet++; + } + if ((parcBitVector->firstBitSet == -1) || (bit < parcBitVector->firstBitSet)) { + parcBitVector->firstBitSet = bit; + } +} + +void +parcBitVector_SetVector(PARCBitVector *parcBitVector, const PARCBitVector *bitsToSet) +{ + assertNotNull(parcBitVector, "parcBitVector_SetVector passed a NULL parcBitVector"); + assertNotNull(parcBitVector, "parcBitVector_SetVector passed a NULL vector of bits to set"); + int settingBit = 0; + for (int i = 0; i < bitsToSet->numberOfBitsSet; i++) { + settingBit = parcBitVector_NextBitSet(bitsToSet, settingBit); + assertTrue(settingBit != -1, "Number of bits claimed set inconsistent with bits found"); + parcBitVector_Set(parcBitVector, settingBit); + settingBit++; + } +} + +void +parcBitVector_Reset(PARCBitVector *parcBitVector) +{ + parcBitVector->numberOfBitsSet = 0; + parcBitVector->firstBitSet = -1; + parcBitVector->fillValue = 0; + memset(parcBitVector->bitArray, parcBitVector->fillValue, parcBitVector->bitLength / BITS_PER_BYTE); +} + + +void +parcBitVector_Clear(PARCBitVector *parcBitVector, unsigned bit) +{ + assertNotNull(parcBitVector, "parcBitVector_Clear passed a NULL parcBitVector"); + assertTrue(bit < MAX_BIT_VECTOR_INDEX, "parcBitVector_Clear passed a bit index that's too huge"); + if (bit > parcBitVector->bitLength) { + _parc_bit_vector_resize(parcBitVector, bit); + } + int byte = bit / BITS_PER_BYTE; + int bitInByte = bit % BITS_PER_BYTE; + if (parcBitVector->bitArray[byte] & (1 << bitInByte)) { + parcBitVector->bitArray[byte] &= ~(1 << bitInByte); + parcBitVector->numberOfBitsSet--; + } + if (bit == parcBitVector->firstBitSet) { + parcBitVector->firstBitSet = parcBitVector_NextBitSet(parcBitVector, bit + 1); + } +} + +void +parcBitVector_ClearVector(PARCBitVector *parcBitVector, const PARCBitVector *bitsToClear) +{ + assertNotNull(parcBitVector, "parcBitVector_ClearVector passed a NULL parcBitVector"); + assertNotNull(bitsToClear, "parcBitVector_ClearVector passed a NULL for vector of bitsToClear"); + + // If we're clearing ourself, we just need a reset + if (parcBitVector == bitsToClear) { + parcBitVector_Reset(parcBitVector); + return; + } + + int clearingBit = 0; + for (int i = 0; i < bitsToClear->numberOfBitsSet; i++) { + clearingBit = parcBitVector_NextBitSet(bitsToClear, clearingBit); + // only clear up to the end of the original vector + if (clearingBit >= parcBitVector->bitLength) { + return; + } + if (clearingBit != -1) { + parcBitVector_Clear(parcBitVector, clearingBit); + } + clearingBit++; + } +} + +unsigned +parcBitVector_NumberOfBitsSet(const PARCBitVector *parcBitVector) +{ + return parcBitVector->numberOfBitsSet; +} + +unsigned +parcBitVector_NextBitSet(const PARCBitVector *parcBitVector, unsigned startFrom) +{ + if (startFrom >= parcBitVector->bitLength) { + return -1; + } + if (startFrom <= parcBitVector->firstBitSet) { + return parcBitVector->firstBitSet; + } + int byte = startFrom / BITS_PER_BYTE; + int bitInByte = startFrom % BITS_PER_BYTE; + int allocatedBytes = ((parcBitVector->bitLength) / BITS_PER_BYTE); + for (; byte < allocatedBytes; byte++) { + if (parcBitVector->bitArray[byte]) { + for (; bitInByte < BITS_PER_BYTE; bitInByte++) { + if (parcBitVector->bitArray[byte] & (1 << bitInByte)) { + return (byte * BITS_PER_BYTE) + bitInByte; + } + } + } + bitInByte = 0; + } + return -1; +} + +bool +parcBitVector_Contains(const PARCBitVector *parcBitVector, const PARCBitVector *testVector) +{ + bool result = true; + + int testBit = 0; + for (int i = 0; i < testVector->numberOfBitsSet; i++, testBit++) { + testBit = parcBitVector_NextBitSet(testVector, testBit); + if (parcBitVector_Get(parcBitVector, testBit) != 1) { + result = false; + break; + } + } + + return result; +} + +char * +parcBitVector_ToString(const PARCBitVector *parcBitVector) +{ + char *result = NULL; + + PARCBufferComposer *composer = parcBufferComposer_Create(); + if (composer != NULL) { + int nextBitSet = 0; + parcBufferComposer_Format(composer, "[ "); + for (int index = parcBitVector_NumberOfBitsSet(parcBitVector); index; index--) { + nextBitSet = parcBitVector_NextBitSet(parcBitVector, nextBitSet); + parcBufferComposer_Format(composer, "%d ", nextBitSet); + nextBitSet++; + } + parcBufferComposer_Format(composer, "]"); + PARCBuffer *tempBuffer = parcBufferComposer_ProduceBuffer(composer); + parcBufferComposer_Release(&composer); + + result = parcBuffer_ToString(tempBuffer); + parcBuffer_Release(&tempBuffer); + } + + return result; +} + +PARCBitVector * +parcBitVector_Or(const PARCBitVector *first, const PARCBitVector *second) +{ + PARCBitVector *result = NULL; + + if (first != NULL) { + result = parcBitVector_Copy(first); + if (second != NULL) { + for (int bit = 0; (bit = parcBitVector_NextBitSet(second, bit)) >= 0; bit++) { + parcBitVector_Set(result, bit); + } + } + } else if (second != NULL) { + result = parcBitVector_Copy(second); + } else { // both null, or is empty + result = parcBitVector_Create(); + } + + return result; +} + +PARCBitVector * +parcBitVector_And(const PARCBitVector *first, const PARCBitVector *second) +{ + PARCBitVector *result = parcBitVector_Create(); + + if (second == NULL) { + if (first != NULL) { + return result; + } + } + + if (first != NULL) { + for (int bit = 0; (bit = parcBitVector_NextBitSet(first, bit)) >= 0; bit++) { + if (parcBitVector_Get(second, bit) == 1) { + parcBitVector_Set(result, bit); + } + } + } + + return result; +} + +static PARCBitVector * +_parcBitVector_LeftShiftOnce(PARCBitVector *parcBitVector) +{ + if (parcBitVector != NULL) { + for (int bit = 0; (bit = parcBitVector_NextBitSet(parcBitVector, bit)) >= 0; bit++) { + if (bit > 0) { // The first bit falls off + parcBitVector_Set(parcBitVector, bit - 1); + } + parcBitVector_Clear(parcBitVector, bit); + } + } + + return parcBitVector; +} + +PARCBitVector * +parcBitVector_LeftShift(PARCBitVector *parcBitVector, size_t count) +{ + for (int i = 0; i < count; i++) { + _parcBitVector_LeftShiftOnce(parcBitVector); + } + + return parcBitVector; +} + +static PARCBitVector * +_parcBitVector_RightShiftOnce(PARCBitVector *parcBitVector) +{ + if (parcBitVector != NULL) { + for (int bit = 0; (bit = parcBitVector_NextBitSet(parcBitVector, bit)) >= 0; bit++) { + // Shift the next sequence of one bits into the first zero bit + int nextZero = bit + 1; + while (parcBitVector_Get(parcBitVector, nextZero) == 1) { + nextZero++; + } + parcBitVector_Clear(parcBitVector, bit++); + while (bit <= nextZero) { + parcBitVector_Set(parcBitVector, bit); + bit++; + } + } + } + + return parcBitVector; +} + +PARCBitVector * +parcBitVector_RightShift(PARCBitVector *parcBitVector, size_t count) +{ + for (int i = 0; i < count; i++) { + _parcBitVector_RightShiftOnce(parcBitVector); + } + + return parcBitVector; +} |