You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
578 lines
17 KiB
578 lines
17 KiB
4 months ago
|
#ifndef _DEPOOLSET_H
|
||
|
|
#define _DEPOOLSET_H
|
||
|
|
/*-------------------------------------------------------------------------
|
||
|
|
* drawElements Memory Pool Library
|
||
|
|
* --------------------------------
|
||
|
|
*
|
||
|
|
* Copyright 2014 The Android Open Source Project
|
||
|
|
*
|
||
|
|
* 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.
|
||
|
|
*
|
||
|
|
*//*!
|
||
|
|
* \file
|
||
|
|
* \brief Memory pool set class.
|
||
|
|
*//*--------------------------------------------------------------------*/
|
||
|
|
|
||
|
|
#include "deDefs.h"
|
||
|
|
#include "deMemPool.h"
|
||
|
|
#include "dePoolArray.h"
|
||
|
|
#include "deInt32.h"
|
||
|
|
|
||
|
|
#include <string.h> /* memset() */
|
||
|
|
|
||
|
|
enum
|
||
|
|
{
|
||
|
|
DE_SET_ELEMENTS_PER_SLOT = 4
|
||
|
|
};
|
||
|
|
|
||
|
|
DE_BEGIN_EXTERN_C
|
||
|
|
|
||
|
|
void dePoolSet_selfTest (void);
|
||
|
|
|
||
|
|
DE_END_EXTERN_C
|
||
|
|
|
||
|
|
/*--------------------------------------------------------------------*//*!
|
||
|
|
* \brief Declare a template pool set class interface.
|
||
|
|
* \param TYPENAME Type name of the declared set.
|
||
|
|
* \param KEYTYPE Type of the key.
|
||
|
|
*
|
||
|
|
* This macro declares the interface for a set. For the implementation of
|
||
|
|
* the set, see DE_IMPLEMENT_POOL_HASH. Usually this macro is put into the
|
||
|
|
* header file and the implementation macro is put in some .c file.
|
||
|
|
*
|
||
|
|
* \todo [petri] Detailed description.
|
||
|
|
*
|
||
|
|
* The functions for operating the set are:
|
||
|
|
* \todo [petri] Figure out how to comment these in Doxygen-style.
|
||
|
|
*
|
||
|
|
* \code
|
||
|
|
* Set* Set_create (deMemPool* pool);
|
||
|
|
* int Set_getNumElements (const Set* array);
|
||
|
|
* deBool Set_exists (const Set* array, Key key);
|
||
|
|
* deBool Set_insert (Set* array, Key key);
|
||
|
|
* void Set_delete (Set* array, Key key);
|
||
|
|
* \endcode
|
||
|
|
*//*--------------------------------------------------------------------*/
|
||
|
|
#define DE_DECLARE_POOL_SET(TYPENAME, KEYTYPE) \
|
||
|
|
\
|
||
|
|
typedef struct TYPENAME##Slot_s TYPENAME##Slot; \
|
||
|
|
\
|
||
|
|
struct TYPENAME##Slot_s \
|
||
|
|
{ \
|
||
|
|
int numUsed; \
|
||
|
|
TYPENAME##Slot* nextSlot; \
|
||
|
|
KEYTYPE keys[DE_SET_ELEMENTS_PER_SLOT]; \
|
||
|
|
}; \
|
||
|
|
\
|
||
|
|
typedef struct TYPENAME##_s \
|
||
|
|
{ \
|
||
|
|
deMemPool* pool; \
|
||
|
|
int numElements; \
|
||
|
|
\
|
||
|
|
int slotTableSize; \
|
||
|
|
TYPENAME##Slot** slotTable; \
|
||
|
|
TYPENAME##Slot* slotFreeList; \
|
||
|
|
} TYPENAME; /* NOLINT(TYPENAME) */ \
|
||
|
|
\
|
||
|
|
typedef struct TYPENAME##Iter_s \
|
||
|
|
{ \
|
||
|
|
const TYPENAME* hash; \
|
||
|
|
int curSlotIndex; \
|
||
|
|
const TYPENAME##Slot* curSlot; \
|
||
|
|
int curElemIndex; \
|
||
|
|
} TYPENAME##Iter; \
|
||
|
|
\
|
||
|
|
TYPENAME* TYPENAME##_create (deMemPool* pool); \
|
||
|
|
void TYPENAME##_reset (DE_PTR_TYPE(TYPENAME) set); \
|
||
|
|
deBool TYPENAME##_reserve (DE_PTR_TYPE(TYPENAME) set, int capacity); \
|
||
|
|
deBool TYPENAME##_exists (const TYPENAME* set, KEYTYPE key); \
|
||
|
|
deBool TYPENAME##_insert (DE_PTR_TYPE(TYPENAME) set, KEYTYPE key); \
|
||
|
|
void TYPENAME##_delete (DE_PTR_TYPE(TYPENAME) set, KEYTYPE key); \
|
||
|
|
\
|
||
|
|
DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* set) DE_UNUSED_FUNCTION; \
|
||
|
|
DE_INLINE void TYPENAME##Iter_init (const TYPENAME* hash, TYPENAME##Iter* iter) DE_UNUSED_FUNCTION; \
|
||
|
|
DE_INLINE deBool TYPENAME##Iter_hasItem (const TYPENAME##Iter* iter) DE_UNUSED_FUNCTION; \
|
||
|
|
DE_INLINE void TYPENAME##Iter_next (TYPENAME##Iter* iter) DE_UNUSED_FUNCTION; \
|
||
|
|
DE_INLINE KEYTYPE TYPENAME##Iter_getKey (const TYPENAME##Iter* iter) DE_UNUSED_FUNCTION; \
|
||
|
|
DE_INLINE deBool TYPENAME##_safeInsert (DE_PTR_TYPE(TYPENAME) set, KEYTYPE key) DE_UNUSED_FUNCTION; \
|
||
|
|
DE_INLINE void TYPENAME##_safeDelete (DE_PTR_TYPE(TYPENAME) set, KEYTYPE key) DE_UNUSED_FUNCTION; \
|
||
|
|
\
|
||
|
|
DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* set) \
|
||
|
|
{ \
|
||
|
|
return set->numElements; \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
DE_INLINE void TYPENAME##Iter_init (const TYPENAME* hash, TYPENAME##Iter* iter) \
|
||
|
|
{ \
|
||
|
|
iter->hash = hash; \
|
||
|
|
iter->curSlotIndex = 0; \
|
||
|
|
iter->curSlot = DE_NULL; \
|
||
|
|
iter->curElemIndex = 0; \
|
||
|
|
if (TYPENAME##_getNumElements(hash) > 0) \
|
||
|
|
{ \
|
||
|
|
int slotTableSize = hash->slotTableSize; \
|
||
|
|
int slotNdx = 0; \
|
||
|
|
while (slotNdx < slotTableSize) \
|
||
|
|
{ \
|
||
|
|
if (hash->slotTable[slotNdx]) \
|
||
|
|
break; \
|
||
|
|
slotNdx++; \
|
||
|
|
} \
|
||
|
|
DE_ASSERT(slotNdx < slotTableSize); \
|
||
|
|
iter->curSlotIndex = slotNdx; \
|
||
|
|
iter->curSlot = hash->slotTable[slotNdx]; \
|
||
|
|
DE_ASSERT(iter->curSlot); \
|
||
|
|
} \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
DE_INLINE deBool TYPENAME##Iter_hasItem (const TYPENAME##Iter* iter) \
|
||
|
|
{ \
|
||
|
|
return (iter->curSlot != DE_NULL); \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
DE_INLINE void TYPENAME##Iter_next (TYPENAME##Iter* iter) \
|
||
|
|
{ \
|
||
|
|
DE_ASSERT(TYPENAME##Iter_hasItem(iter)); \
|
||
|
|
if (++iter->curElemIndex == iter->curSlot->numUsed) \
|
||
|
|
{ \
|
||
|
|
iter->curElemIndex = 0; \
|
||
|
|
if (iter->curSlot->nextSlot) \
|
||
|
|
{ \
|
||
|
|
iter->curSlot = iter->curSlot->nextSlot; \
|
||
|
|
} \
|
||
|
|
else \
|
||
|
|
{ \
|
||
|
|
const TYPENAME* hash = iter->hash; \
|
||
|
|
int curSlotIndex = iter->curSlotIndex; \
|
||
|
|
int slotTableSize = hash->slotTableSize; \
|
||
|
|
while (++curSlotIndex < slotTableSize) \
|
||
|
|
{ \
|
||
|
|
if (hash->slotTable[curSlotIndex]) \
|
||
|
|
break; \
|
||
|
|
} \
|
||
|
|
iter->curSlotIndex = curSlotIndex; \
|
||
|
|
if (curSlotIndex < slotTableSize) \
|
||
|
|
iter->curSlot = hash->slotTable[curSlotIndex]; \
|
||
|
|
else \
|
||
|
|
iter->curSlot = DE_NULL; \
|
||
|
|
} \
|
||
|
|
} \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
DE_INLINE KEYTYPE TYPENAME##Iter_getKey (const TYPENAME##Iter* iter) \
|
||
|
|
{ \
|
||
|
|
DE_ASSERT(TYPENAME##Iter_hasItem(iter)); \
|
||
|
|
return iter->curSlot->keys[iter->curElemIndex]; \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
DE_INLINE deBool TYPENAME##_safeInsert (DE_PTR_TYPE(TYPENAME) set, KEYTYPE key) \
|
||
|
|
{ \
|
||
|
|
DE_ASSERT(set); \
|
||
|
|
if (TYPENAME##_exists(set, key)) \
|
||
|
|
return DE_TRUE; \
|
||
|
|
return TYPENAME##_insert(set, key); \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
DE_INLINE void TYPENAME##_safeDelete (DE_PTR_TYPE(TYPENAME) set, KEYTYPE key) \
|
||
|
|
{ \
|
||
|
|
DE_ASSERT(set); \
|
||
|
|
if (TYPENAME##_exists(set, key)) \
|
||
|
|
TYPENAME##_delete(set, key); \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
struct TYPENAME##Dummy_s { int dummy; }
|
||
|
|
|
||
|
|
/*--------------------------------------------------------------------*//*!
|
||
|
|
* \brief Implement a template pool set class.
|
||
|
|
* \param TYPENAME Type name of the declared set.
|
||
|
|
* \param KEYTYPE Type of the key.
|
||
|
|
* \param HASHFUNC Function used for hashing the key.
|
||
|
|
* \param CMPFUNC Function used for exact matching of the keys.
|
||
|
|
*
|
||
|
|
* This macro has implements the set declared with DE_DECLARE_POOL_SET.
|
||
|
|
* Usually this macro should be used from a .c file, since the macro expands
|
||
|
|
* into multiple functions. The TYPENAME and KEYTYPE parameters
|
||
|
|
* must match those of the declare macro.
|
||
|
|
*//*--------------------------------------------------------------------*/
|
||
|
|
#define DE_IMPLEMENT_POOL_SET(TYPENAME, KEYTYPE, HASHFUNC, CMPFUNC) \
|
||
|
|
\
|
||
|
|
DE_PTR_TYPE(TYPENAME) TYPENAME##_create (deMemPool* pool) \
|
||
|
|
{ \
|
||
|
|
/* Alloc struct. */ \
|
||
|
|
DE_PTR_TYPE(TYPENAME) set = DE_POOL_NEW(pool, TYPENAME); \
|
||
|
|
if (!set) \
|
||
|
|
return DE_NULL; \
|
||
|
|
\
|
||
|
|
/* Init array. */ \
|
||
|
|
memset(set, 0, sizeof(TYPENAME)); \
|
||
|
|
set->pool = pool; \
|
||
|
|
\
|
||
|
|
return set; \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
void TYPENAME##_reset (DE_PTR_TYPE(TYPENAME) set) \
|
||
|
|
{ \
|
||
|
|
int slotNdx; \
|
||
|
|
for (slotNdx = 0; slotNdx < set->slotTableSize; slotNdx++) \
|
||
|
|
{ \
|
||
|
|
TYPENAME##Slot* slot = set->slotTable[slotNdx]; \
|
||
|
|
while (slot) \
|
||
|
|
{ \
|
||
|
|
TYPENAME##Slot* nextSlot = slot->nextSlot; \
|
||
|
|
slot->nextSlot = set->slotFreeList; \
|
||
|
|
set->slotFreeList = slot; \
|
||
|
|
slot->numUsed = 0; \
|
||
|
|
slot = nextSlot; \
|
||
|
|
} \
|
||
|
|
set->slotTable[slotNdx] = DE_NULL; \
|
||
|
|
} \
|
||
|
|
set->numElements = 0; \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
TYPENAME##Slot* TYPENAME##_allocSlot (DE_PTR_TYPE(TYPENAME) set) \
|
||
|
|
{ \
|
||
|
|
TYPENAME##Slot* slot; \
|
||
|
|
if (set->slotFreeList) \
|
||
|
|
{ \
|
||
|
|
slot = set->slotFreeList; \
|
||
|
|
set->slotFreeList = set->slotFreeList->nextSlot; \
|
||
|
|
} \
|
||
|
|
else \
|
||
|
|
slot = (TYPENAME##Slot*)deMemPool_alloc(set->pool, sizeof(TYPENAME##Slot) * DE_SET_ELEMENTS_PER_SLOT); \
|
||
|
|
\
|
||
|
|
if (slot) \
|
||
|
|
{ \
|
||
|
|
slot->nextSlot = DE_NULL; \
|
||
|
|
slot->numUsed = 0; \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
return slot; \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
deBool TYPENAME##_rehash (DE_PTR_TYPE(TYPENAME) set, int newSlotTableSize) \
|
||
|
|
{ \
|
||
|
|
DE_ASSERT(deIsPowerOfTwo32(newSlotTableSize) && newSlotTableSize > 0); \
|
||
|
|
if (newSlotTableSize > set->slotTableSize) \
|
||
|
|
{ \
|
||
|
|
TYPENAME##Slot** oldSlotTable = set->slotTable; \
|
||
|
|
TYPENAME##Slot** newSlotTable = (TYPENAME##Slot**)deMemPool_alloc(set->pool, sizeof(TYPENAME##Slot*) * (size_t)newSlotTableSize); \
|
||
|
|
int oldSlotTableSize = set->slotTableSize; \
|
||
|
|
int slotNdx; \
|
||
|
|
\
|
||
|
|
if (!newSlotTable) \
|
||
|
|
return DE_FALSE; \
|
||
|
|
\
|
||
|
|
for (slotNdx = 0; slotNdx < oldSlotTableSize; slotNdx++) \
|
||
|
|
newSlotTable[slotNdx] = oldSlotTable[slotNdx]; \
|
||
|
|
\
|
||
|
|
for (slotNdx = oldSlotTableSize; slotNdx < newSlotTableSize; slotNdx++) \
|
||
|
|
newSlotTable[slotNdx] = DE_NULL; \
|
||
|
|
\
|
||
|
|
set->slotTableSize = newSlotTableSize; \
|
||
|
|
set->slotTable = newSlotTable; \
|
||
|
|
\
|
||
|
|
for (slotNdx = 0; slotNdx < oldSlotTableSize; slotNdx++) \
|
||
|
|
{ \
|
||
|
|
TYPENAME##Slot* slot = oldSlotTable[slotNdx]; \
|
||
|
|
newSlotTable[slotNdx] = DE_NULL; \
|
||
|
|
while (slot) \
|
||
|
|
{ \
|
||
|
|
int elemNdx; \
|
||
|
|
for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \
|
||
|
|
{ \
|
||
|
|
set->numElements--; \
|
||
|
|
if (!TYPENAME##_insert(set, slot->keys[elemNdx])) \
|
||
|
|
return DE_FALSE; \
|
||
|
|
} \
|
||
|
|
slot = slot->nextSlot; \
|
||
|
|
} \
|
||
|
|
} \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
return DE_TRUE; \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
deBool TYPENAME##_exists (const TYPENAME* set, KEYTYPE key) \
|
||
|
|
{ \
|
||
|
|
if (set->numElements > 0) \
|
||
|
|
{ \
|
||
|
|
int slotNdx = (int)(HASHFUNC(key) & (deUint32)(set->slotTableSize - 1)); \
|
||
|
|
TYPENAME##Slot* slot = set->slotTable[slotNdx]; \
|
||
|
|
DE_ASSERT(deInBounds32(slotNdx, 0, set->slotTableSize)); \
|
||
|
|
\
|
||
|
|
while (slot) \
|
||
|
|
{ \
|
||
|
|
int elemNdx; \
|
||
|
|
for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \
|
||
|
|
{ \
|
||
|
|
if (CMPFUNC(slot->keys[elemNdx], key)) \
|
||
|
|
return DE_TRUE; \
|
||
|
|
} \
|
||
|
|
slot = slot->nextSlot; \
|
||
|
|
} \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
return DE_FALSE; \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
deBool TYPENAME##_insert (DE_PTR_TYPE(TYPENAME) set, KEYTYPE key) \
|
||
|
|
{ \
|
||
|
|
int slotNdx; \
|
||
|
|
TYPENAME##Slot* slot; \
|
||
|
|
\
|
||
|
|
DE_ASSERT(set); \
|
||
|
|
DE_ASSERT(!TYPENAME##_exists(set, key)); \
|
||
|
|
\
|
||
|
|
if ((set->numElements + 1) >= set->slotTableSize * DE_SET_ELEMENTS_PER_SLOT) \
|
||
|
|
if (!TYPENAME##_rehash(set, deMax32(4, 2*set->slotTableSize))) \
|
||
|
|
return DE_FALSE; \
|
||
|
|
\
|
||
|
|
slotNdx = (int)(HASHFUNC(key) & (deUint32)(set->slotTableSize - 1)); \
|
||
|
|
DE_ASSERT(slotNdx >= 0 && slotNdx < set->slotTableSize); \
|
||
|
|
slot = set->slotTable[slotNdx]; \
|
||
|
|
\
|
||
|
|
if (!slot) \
|
||
|
|
{ \
|
||
|
|
slot = TYPENAME##_allocSlot(set); \
|
||
|
|
if (!slot) return DE_FALSE; \
|
||
|
|
set->slotTable[slotNdx] = slot; \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
for (;;) \
|
||
|
|
{ \
|
||
|
|
if (slot->numUsed == DE_SET_ELEMENTS_PER_SLOT) \
|
||
|
|
{ \
|
||
|
|
if (slot->nextSlot) \
|
||
|
|
slot = slot->nextSlot; \
|
||
|
|
else \
|
||
|
|
{ \
|
||
|
|
TYPENAME##Slot* nextSlot = TYPENAME##_allocSlot(set); \
|
||
|
|
if (!nextSlot) return DE_FALSE; \
|
||
|
|
slot->nextSlot = nextSlot; \
|
||
|
|
slot = nextSlot; \
|
||
|
|
} \
|
||
|
|
} \
|
||
|
|
else \
|
||
|
|
{ \
|
||
|
|
slot->keys[slot->numUsed] = key; \
|
||
|
|
slot->numUsed++; \
|
||
|
|
set->numElements++; \
|
||
|
|
return DE_TRUE; \
|
||
|
|
} \
|
||
|
|
} \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
void TYPENAME##_delete (DE_PTR_TYPE(TYPENAME) set, KEYTYPE key) \
|
||
|
|
{ \
|
||
|
|
int slotNdx; \
|
||
|
|
TYPENAME##Slot* slot; \
|
||
|
|
TYPENAME##Slot* prevSlot = DE_NULL; \
|
||
|
|
\
|
||
|
|
DE_ASSERT(set->numElements > 0); \
|
||
|
|
slotNdx = (int)(HASHFUNC(key) & (deUint32)(set->slotTableSize - 1)); \
|
||
|
|
DE_ASSERT(slotNdx >= 0 && slotNdx < set->slotTableSize); \
|
||
|
|
slot = set->slotTable[slotNdx]; \
|
||
|
|
DE_ASSERT(slot); \
|
||
|
|
\
|
||
|
|
for (;;) \
|
||
|
|
{ \
|
||
|
|
int elemNdx; \
|
||
|
|
DE_ASSERT(slot->numUsed > 0); \
|
||
|
|
for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \
|
||
|
|
{ \
|
||
|
|
if (CMPFUNC(key, slot->keys[elemNdx])) \
|
||
|
|
{ \
|
||
|
|
TYPENAME##Slot* lastSlot = slot; \
|
||
|
|
while (lastSlot->nextSlot) \
|
||
|
|
{ \
|
||
|
|
prevSlot = lastSlot; \
|
||
|
|
lastSlot = lastSlot->nextSlot; \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
slot->keys[elemNdx] = lastSlot->keys[lastSlot->numUsed-1]; \
|
||
|
|
lastSlot->numUsed--; \
|
||
|
|
\
|
||
|
|
if (lastSlot->numUsed == 0) \
|
||
|
|
{ \
|
||
|
|
if (prevSlot) \
|
||
|
|
prevSlot->nextSlot = DE_NULL; \
|
||
|
|
else \
|
||
|
|
set->slotTable[slotNdx] = DE_NULL; \
|
||
|
|
\
|
||
|
|
lastSlot->nextSlot = set->slotFreeList; \
|
||
|
|
set->slotFreeList = lastSlot; \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
set->numElements--; \
|
||
|
|
return; \
|
||
|
|
} \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
prevSlot = slot; \
|
||
|
|
slot = slot->nextSlot; \
|
||
|
|
DE_ASSERT(slot); \
|
||
|
|
} \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
struct TYPENAME##Dummy2_s { int dummy; }
|
||
|
|
|
||
|
|
/* Copy-to-array templates. */
|
||
|
|
|
||
|
|
#define DE_DECLARE_POOL_SET_TO_ARRAY(SETTYPENAME, ARRAYTYPENAME) \
|
||
|
|
deBool SETTYPENAME##_copyToArray(const SETTYPENAME* set, DE_PTR_TYPE(ARRAYTYPENAME) array); \
|
||
|
|
struct SETTYPENAME##_##ARRAYTYPENAME##_declare_dummy { int dummy; }
|
||
|
|
|
||
|
|
#define DE_IMPLEMENT_POOL_SET_TO_ARRAY(SETTYPENAME, ARRAYTYPENAME) \
|
||
|
|
deBool SETTYPENAME##_copyToArray(const SETTYPENAME* set, DE_PTR_TYPE(ARRAYTYPENAME) array) \
|
||
|
|
{ \
|
||
|
|
int numElements = set->numElements; \
|
||
|
|
int arrayNdx = 0; \
|
||
|
|
int slotNdx; \
|
||
|
|
\
|
||
|
|
if (!ARRAYTYPENAME##_setSize(array, numElements)) \
|
||
|
|
return DE_FALSE; \
|
||
|
|
\
|
||
|
|
for (slotNdx = 0; slotNdx < set->slotTableSize; slotNdx++) \
|
||
|
|
{ \
|
||
|
|
const SETTYPENAME##Slot* slot = set->slotTable[slotNdx]; \
|
||
|
|
while (slot) \
|
||
|
|
{ \
|
||
|
|
int elemNdx; \
|
||
|
|
for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \
|
||
|
|
ARRAYTYPENAME##_set(array, arrayNdx++, slot->keys[elemNdx]); \
|
||
|
|
slot = slot->nextSlot; \
|
||
|
|
} \
|
||
|
|
} \
|
||
|
|
DE_ASSERT(arrayNdx == numElements); \
|
||
|
|
return DE_TRUE; \
|
||
|
|
} \
|
||
|
|
struct SETTYPENAME##_##ARRAYTYPENAME##_implement_dummy { int dummy; }
|
||
|
|
|
||
|
|
/*--------------------------------------------------------------------*//*!
|
||
|
|
* \brief Declare set-wise operations for a set template.
|
||
|
|
* \param TYPENAME Type name of the declared set.
|
||
|
|
* \param KEYTYPE Type of the key.
|
||
|
|
*
|
||
|
|
* This macro declares union and intersection operations for a set.
|
||
|
|
* For implementation see DE_IMPLEMENT_POOL_SET_UNION_INTERSECT.
|
||
|
|
*
|
||
|
|
* \todo [petri] Detailed description.
|
||
|
|
*
|
||
|
|
* The functions for operating the set are:
|
||
|
|
* \todo [petri] Figure out how to comment these in Doxygen-style.
|
||
|
|
*
|
||
|
|
* \code
|
||
|
|
* deBool Set_union (Set* to, const Set* a, const Set* b);
|
||
|
|
* deBool Set_unionInplace (Set* a, const Set* b);
|
||
|
|
* deBool Set_intersect (Set* to, const Set* a, const Set* b);
|
||
|
|
* void Set_intersectInplace (Set* a, const Set* b);
|
||
|
|
* deBool Set_difference (Set* to, const Set* a, const Set* b);
|
||
|
|
* void Set_differenceInplace (Set* a, const Set* b);
|
||
|
|
* \endcode
|
||
|
|
*//*--------------------------------------------------------------------*/
|
||
|
|
#define DE_DECLARE_POOL_SET_SETWISE_OPERATIONS(TYPENAME) \
|
||
|
|
deBool TYPENAME##_union (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b); \
|
||
|
|
deBool TYPENAME##_unionInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b); \
|
||
|
|
deBool TYPENAME##_intersect (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b); \
|
||
|
|
void TYPENAME##_intersectInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b); \
|
||
|
|
deBool TYPENAME##_difference (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b); \
|
||
|
|
void TYPENAME##_differenceInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b); \
|
||
|
|
struct TYPENAME##SetwiseDeclareDummy_s { int dummy; }
|
||
|
|
|
||
|
|
#define DE_IMPLEMENT_POOL_SET_SETWISE_OPERATIONS(TYPENAME, KEYTYPE) \
|
||
|
|
deBool TYPENAME##_union (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b) \
|
||
|
|
{ \
|
||
|
|
TYPENAME##_reset(to); \
|
||
|
|
if (!TYPENAME##_unionInplace(to, a)) \
|
||
|
|
return DE_FALSE; \
|
||
|
|
if (!TYPENAME##_unionInplace(to, b)) \
|
||
|
|
return DE_FALSE; \
|
||
|
|
return DE_TRUE; \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
deBool TYPENAME##_unionInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b) \
|
||
|
|
{ \
|
||
|
|
TYPENAME##Iter iter; \
|
||
|
|
for (TYPENAME##Iter_init(b, &iter); \
|
||
|
|
TYPENAME##Iter_hasItem(&iter); \
|
||
|
|
TYPENAME##Iter_next(&iter)) \
|
||
|
|
{ \
|
||
|
|
KEYTYPE key = TYPENAME##Iter_getKey(&iter); \
|
||
|
|
if (!TYPENAME##_exists(a, key)) \
|
||
|
|
{ \
|
||
|
|
if (!TYPENAME##_insert(a, key)) \
|
||
|
|
return DE_FALSE; \
|
||
|
|
} \
|
||
|
|
} \
|
||
|
|
return DE_TRUE; \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
deBool TYPENAME##_intersect (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b) \
|
||
|
|
{ \
|
||
|
|
TYPENAME##Iter iter; \
|
||
|
|
TYPENAME##_reset(to); \
|
||
|
|
for (TYPENAME##Iter_init(a, &iter); \
|
||
|
|
TYPENAME##Iter_hasItem(&iter); \
|
||
|
|
TYPENAME##Iter_next(&iter)) \
|
||
|
|
{ \
|
||
|
|
KEYTYPE key = TYPENAME##Iter_getKey(&iter); \
|
||
|
|
if (TYPENAME##_exists(b, key)) \
|
||
|
|
{ \
|
||
|
|
if (!TYPENAME##_insert(to, key)) \
|
||
|
|
return DE_FALSE; \
|
||
|
|
} \
|
||
|
|
} \
|
||
|
|
return DE_TRUE; \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
void TYPENAME##_intersectInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b) \
|
||
|
|
{ \
|
||
|
|
DE_UNREF(a && b); \
|
||
|
|
DE_FATAL("Not implemented."); \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
deBool TYPENAME##_difference (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b) \
|
||
|
|
{ \
|
||
|
|
TYPENAME##Iter iter; \
|
||
|
|
TYPENAME##_reset(to); \
|
||
|
|
for (TYPENAME##Iter_init(a, &iter); \
|
||
|
|
TYPENAME##Iter_hasItem(&iter); \
|
||
|
|
TYPENAME##Iter_next(&iter)) \
|
||
|
|
{ \
|
||
|
|
KEYTYPE key = TYPENAME##Iter_getKey(&iter); \
|
||
|
|
if (!TYPENAME##_exists(b, key)) \
|
||
|
|
{ \
|
||
|
|
if (!TYPENAME##_insert(to, key)) \
|
||
|
|
return DE_FALSE; \
|
||
|
|
} \
|
||
|
|
} \
|
||
|
|
return DE_TRUE; \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
void TYPENAME##_differenceInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b) \
|
||
|
|
{ \
|
||
|
|
TYPENAME##Iter iter; \
|
||
|
|
for (TYPENAME##Iter_init(b, &iter); \
|
||
|
|
TYPENAME##Iter_hasItem(&iter); \
|
||
|
|
TYPENAME##Iter_next(&iter)) \
|
||
|
|
{ \
|
||
|
|
KEYTYPE key = TYPENAME##Iter_getKey(&iter); \
|
||
|
|
if (TYPENAME##_exists(a, key)) \
|
||
|
|
TYPENAME##_delete(a, key); \
|
||
|
|
} \
|
||
|
|
} \
|
||
|
|
\
|
||
|
|
struct TYPENAME##UnionIntersectImplementDummy_s { int dummy; }
|
||
|
|
|
||
|
|
#endif /* _DEPOOLSET_H */
|