BufferTop* buffertop_copy(BufferTop* bufferTop)
{
- BufferTop* bufferTopCopy = _buffertop_new(
- bufferTop->heap->dataSize, bufferTop->capacity,
- bufferTop->heap->hType, bufferTop->heap->arity);
- heap_destroy(bufferTopCopy->heap); //TODO: bad style...
+ BufferTop* bufferTopCopy = (BufferTop*) safe_malloc(sizeof (BufferTop));
+ bufferTopCopy->capacity = bufferTop->capacity;
+ bufferTopCopy->bType = bufferTop->bType;
bufferTopCopy->heap = heap_copy(bufferTop->heap);
return bufferTopCopy;
}
{
// Copy the buffer, and then use the copy to build the list
BufferTop* bufferTopCopy = buffertop_copy(bufferTop);
- List* bufferInList = _list_new(bufferTop->heap->array->dataSize);
+ List* bufferInList = _list_new(bufferTop->heap->items->dataSize);
while (!buffertop_empty(bufferTopCopy))
{
- void* topItem = buffertop_first_raw(bufferTopCopy)->item;
+ void* topItem = _heap_top(bufferTopCopy->heap).item;
// NOTE: list_insert_front(), to reverse (wrong) items order
// ==> in the returned list, top element is at head.
_list_insert_front(bufferInList, topItem);
void _buffertop_tryadd(BufferTop* bufferTop, void* item, Real value)
{
- if (heap_size(bufferTop->heap) >= bufferTop->capacity &&
- ((bufferTop->bType == MIN_T &&
- value >= ((ItemValue*) (bufferTop->heap->array->datas[0]))->value)
- ||
- (bufferTop->bType == MAX_T &&
- value <= ((ItemValue*) (bufferTop->heap->array->datas[0]))->value)))
- {
- // Shortcut : if value "worse" than top->value and buffer is full, skip
- return;
+ if (heap_size(bufferTop->heap) >= bufferTop->capacity) {
+ Real topValue = *((Real*) (bufferTop->heap->values->datas));
+ if (
+ (bufferTop->bType == MIN_T && value >= topValue) ||
+ (bufferTop->bType == MAX_T && value <= topValue)
+ ) {
+ // Shortcut : if value "worse" than top->value and buffer is full, skip
+ return;
+ }
}
// Insertion somewhere in the item-values heap
heap_pop(bufferTop->heap);
}
-ItemValue* buffertop_first_raw(BufferTop* bufferTop)
+ItemValue _buffertop_first(BufferTop* bufferTop)
{
- return heap_top_raw(bufferTop->heap);
+ return _heap_top(bufferTop->heap);
}
void buffertop_pop(BufferTop* bufferTop)
typedef struct BufferTop {
UInt capacity; ///< Buffer capacity (in items count).
OrderType bType; ///< Type of buffer: keep max or min items (MAX_T or MIN_T).
- Heap* heap; ///< Item-ValueS are internally organized into a heap.
+ Heap* heap; ///< Items + values are internally organized into a heap.
} BufferTop;
/**
/**
* @brief Return the top ("worst among best") ItemValue inside current buffer.
*/
-ItemValue* buffertop_first_raw(
+ItemValue _buffertop_first(
BufferTop* bufferTop ///< "this" pointer.
);
* @param bufferTop "this" pointer.
* @param item_ Variable to be assigned.
*
- * Usage: void buffertop_first(BufferTop* bufferTop, void item)
+ * Usage: void buffertop_first(BufferTop* bufferTop, void item_)
*/
#define buffertop_first(bufferTop, item_) \
{ \
- void* pItem = buffertop_first_raw(bufferTop)->item; \
- item_ = *((typeof(&item_))pItem); \
+ ItemValue iv = _buffertop_first(bufferTop); \
+ item_ = *((typeof(item_)*)(iv.item)); \
}
/**
Heap* _heap_new(size_t dataSize, OrderType hType, UInt arity)
{
- Heap* heap = (Heap*)safe_malloc(sizeof(Heap));
+ Heap* heap = (Heap*) safe_malloc(sizeof(Heap));
heap->arity = arity;
heap->hType = hType;
- heap->dataSize = dataSize;
- heap->array = _vector_new(sizeof(ItemValue));
+ heap->items = _vector_new(dataSize);
+ heap->values = _vector_new(sizeof(Real));
return heap;
}
Heap* heap_copy(Heap* heap)
{
- Heap* heapCopy = _heap_new(heap->dataSize, heap->hType, heap->arity);
- // HACK: vector_copy is not enough,
- // since we also have to allocate ItemValue(->item)
- heapCopy->array->size = heap->array->size;
- heapCopy->array->capacity = heap->array->capacity;
- heapCopy->array->datas =
- (void**)safe_malloc(heap->array->capacity*sizeof(void*));
- for (UInt i = 0; i < heap->array->size; i++)
- {
- heapCopy->array->datas[i] = safe_malloc(sizeof(ItemValue));
- ItemValue itemValueCopy = (ItemValue){
- .item=safe_malloc(heap->dataSize),
- .value=((ItemValue*)(heap->array->datas[i]))->value};
- memcpy(
- itemValueCopy.item,
- ((ItemValue*)(heap->array->datas[i]))->item,
- heap->dataSize);
- memcpy(heapCopy->array->datas[i], &itemValueCopy, sizeof(ItemValue));
- }
+ Heap* heapCopy = (Heap*) safe_malloc(sizeof(Heap));
+ heapCopy->arity = heap->arity;
+ heapCopy->hType = heap->hType;
+ heapCopy->items = vector_copy(heap->items);
+ heapCopy->values = vector_copy(heap->values);
return heapCopy;
}
bool heap_empty(Heap* heap)
{
- return vector_empty(heap->array);
+ return vector_empty(heap->items);
}
UInt heap_size(Heap* heap)
{
- return vector_size(heap->array);
+ return vector_size(heap->items);
}
// NOTE: [perf] in two following methods, full heap[k] exchanges are
void _heap_bubble_up(Heap* heap, UInt startIndex)
{
+ if (startIndex == 0)
+ // Nothing to do in this case
+ return;
UInt currentIndex = startIndex;
- ItemValue* startItemValue = heap->array->datas[startIndex];
+ void* startItem = _vector_get(heap->items, startIndex);
+ Real startValue = *((Real*)(_vector_get(heap->values, startIndex)));
+ bool startItemReallocated = false;
while (true)
{
- // get parent
- UInt nextIndex = currentIndex / heap->arity;
- Real nextValue = ((ItemValue*)(heap->array->datas[nextIndex]))->value;
- // compare to parent (if applicable)
- if (currentIndex == 0 ||
- (heap->hType == MIN_T && startItemValue->value >= nextValue) ||
- (heap->hType == MAX_T && startItemValue->value <= nextValue))
+ bool land = (currentIndex == 0), //at root: can't go up
+ applyExchange = true;
+ if (!land)
+ {
+ // Get parent and compare to it
+ UInt nextIndex = (currentIndex - 1) / heap->arity;
+ Real nextValue = *((Real*)(_vector_get(heap->values, nextIndex)));
+ land = (
+ (heap->hType == MIN_T && startValue >= nextValue) ||
+ (heap->hType == MAX_T && startValue <= nextValue)
+ );
+ if (!land)
+ {
+ // Move one level up: the parent goes one level down
+ if (currentIndex == startIndex)
+ {
+ // Save startItem (because *startItem is about to be changed)
+ void* newStartItem = safe_malloc(heap->items->dataSize);
+ memcpy(newStartItem, startItem, heap->items->dataSize);
+ startItem = newStartItem;
+ startItemReallocated = true;
+ }
+ void* nextItem = _vector_get(heap->items, nextIndex);
+ _vector_set(heap->items, currentIndex, nextItem);
+ _vector_set(heap->values, currentIndex, &nextValue);
+ currentIndex = nextIndex;
+ continue;
+ }
+ // At correct relative place: will now land
+ if (currentIndex == startIndex)
+ applyExchange = false;
+ }
+ if (applyExchange)
{
- // moving element has landed: apply final affectation
- heap->array->datas[currentIndex] = startItemValue;
- break;
+ _vector_set(heap->items, currentIndex, startItem);
+ _vector_set(heap->values, currentIndex, &startValue);
}
- // move one level up: the parent goes one level down
- heap->array->datas[currentIndex] = heap->array->datas[nextIndex];
- currentIndex = nextIndex;
+ break;
}
+ if (startItemReallocated)
+ safe_free(startItem);
}
void _heap_bubble_down(Heap* heap, UInt startIndex)
{
+ if (startIndex * heap->arity + 1 >= heap->items->size)
+ // Nothing to do: already in a leaf
+ return;
UInt currentIndex = startIndex;
- ItemValue* startItemValue = heap->array->datas[startIndex];
+ void* startItem = _vector_get(heap->items, startIndex);
+ Real startValue = *((Real*)(_vector_get(heap->values, startIndex)));
+ bool startItemReallocated = false;
while (true)
{
- if (currentIndex * heap->arity >= heap->array->size)
+ bool land = (currentIndex * heap->arity + 1 >= heap->items->size),
+ applyExchange = true;
+ if (!land)
{
- // moving element has landed (in a leaf): apply final affectation
- heap->array->datas[currentIndex] = startItemValue;
- break;
- }
- // find top child (min or max)
- UInt topChildIndex;
- Real topChildValue = (heap->hType == MIN_T ? INFINITY : -INFINITY);
- for (UInt i = 0; i < heap->arity; i++)
- {
- UInt childIndex = i + currentIndex * heap->arity;
- if (childIndex >= heap->array->size)
- break;
- Real childValue = ((ItemValue*)(heap->array->datas[childIndex]))->value;
- if ((heap->hType == MIN_T && childValue < topChildValue) ||
- (heap->hType == MAX_T && childValue > topChildValue))
+ // Find top child (min or max)
+ UInt topChildIndex;
+ Real topChildValue = (heap->hType == MIN_T ? INFINITY : -INFINITY);
+ for (UInt i = 1; i <= heap->arity; i++)
{
- topChildIndex = childIndex;
- topChildValue = childValue;
+ UInt childIndex = currentIndex * heap->arity + i;
+ if (childIndex >= heap->items->size)
+ break;
+ Real childValue = *((Real*)(_vector_get(heap->values, childIndex)));
+ if (
+ (heap->hType == MIN_T && childValue < topChildValue) ||
+ (heap->hType == MAX_T && childValue > topChildValue)
+ ) {
+ topChildIndex = childIndex;
+ topChildValue = childValue;
+ }
}
+ // Compare to top child
+ land = (
+ (heap->hType == MIN_T && startValue <= topChildValue) ||
+ (heap->hType == MAX_T && startValue >= topChildValue)
+ );
+ if (!land)
+ {
+ // Move one level down: the child goes one level up
+ if (currentIndex == startIndex)
+ {
+ // Save startItem (because *startItem is about to be changed)
+ void* newStartItem = safe_malloc(heap->items->dataSize);
+ memcpy(newStartItem, startItem, heap->items->dataSize);
+ startItem = newStartItem;
+ startItemReallocated = true;
+ }
+ void* topChildItem = _vector_get(heap->items, topChildIndex);
+ _vector_set(heap->items, currentIndex, topChildItem);
+ _vector_set(heap->values, currentIndex, &topChildValue);
+ currentIndex = topChildIndex;
+ continue;
+ }
+ // At correct relative place: will now land
+ if (currentIndex == startIndex)
+ applyExchange = false;
}
- // compare to top child
- if ((heap->hType == MIN_T && startItemValue->value > topChildValue) ||
- (heap->hType == MAX_T && startItemValue->value < topChildValue))
- {
- // move one level down: the child goes one level up
- heap->array->datas[currentIndex] = heap->array->datas[topChildIndex];
- }
- else
+ if (applyExchange)
{
- // moving element has landed: apply final affectation
- heap->array->datas[currentIndex] = startItemValue;
- break;
+ // Moving element has landed (in a leaf): apply final affectation
+ _vector_set(heap->items, currentIndex, startItem);
+ _vector_set(heap->values, currentIndex, &startValue);
}
- currentIndex = topChildIndex;
+ break;
}
+ if (startItemReallocated)
+ safe_free(startItem);
}
void _heap_insert(Heap* heap, void* item, Real value)
{
- ItemValue itemValue =
- (ItemValue){.item=safe_malloc(heap->dataSize), .value=value};
- memcpy(itemValue.item, item, heap->dataSize);
- _vector_push(heap->array, &itemValue);
- _heap_bubble_up(heap, heap->array->size-1);
+ _vector_push(heap->items, item);
+ _vector_push(heap->values, &value);
+ _heap_bubble_up(heap, heap->items->size - 1);
}
-void _heap_modify(Heap* heap, UInt index, Real newValue)
+Int _heap_get_index(Heap* heap, void* item)
{
- double oldValue = ((ItemValue*)(heap->array->datas[index]))->value;
- ((ItemValue*)(heap->array->datas[index]))->value = newValue;
- if ((heap->hType == MIN_T && newValue > oldValue) ||
- (heap->hType == MAX_T && newValue < oldValue))
+ for (Int index = 0; index < heap->items->size; index++)
{
+ if (
+ memcmp(
+ heap->items->datas + index * heap->items->dataSize,
+ item,
+ heap->items->dataSize
+ ) == 0
+ ) {
+ return index;
+ }
+ }
+ return -1;
+}
+
+void _heap_modify(Heap* heap, void* item, Real newValue)
+{
+ // First, find index of the item:
+ const Int index = _heap_get_index(heap, item);
+ if (index < 0)
+ // Element not found
+ return;
+ Real oldValue = *((Real*)_vector_get(heap->values, index));
+ _vector_set(heap->values, index, &newValue);
+ if (
+ (heap->hType == MIN_T && newValue > oldValue) ||
+ (heap->hType == MAX_T && newValue < oldValue)
+ ) {
_heap_bubble_down(heap, index);
}
else
_heap_bubble_up(heap, index);
}
-void _heap_remove(Heap* heap, UInt index)
+void _heap_remove_at_index(Heap* heap, Int index)
{
- safe_free(((ItemValue*)(heap->array->datas[index]))->item);
- ItemValue* tmp = heap->array->datas[index];
- heap->array->datas[index] = heap->array->datas[heap_size(heap)-1];
- heap->array->datas[heap_size(heap)-1] = tmp;
- vector_pop(heap->array);
- if (heap->array->size > 0)
+ const bool removeLast = (index == heap->items->size - 1);
+ if (!removeLast)
+ {
+ _vector_set(
+ heap->items,
+ index,
+ _vector_get(heap->items, heap->items->size - 1));
+ _vector_set(
+ heap->values,
+ index,
+ _vector_get(heap->values, heap->values->size - 1));
+ }
+ vector_pop(heap->items);
+ vector_pop(heap->values);
+ if (!removeLast && heap->items->size > 0)
_heap_bubble_down(heap, index);
}
-ItemValue* heap_top_raw(Heap* heap)
+void _heap_remove(Heap* heap, void* item)
+{
+ // First, find index of the item:
+ const Int index = _heap_get_index(heap, item);
+ if (index >= 0)
+ _heap_remove_at_index(heap, index);
+}
+
+ItemValue _heap_top(Heap* heap)
{
- return (ItemValue*)(heap->array->datas[0]);
+ ItemValue top;
+ top.item = _vector_get(heap->items, 0);
+ vector_get(heap->values, 0, top.value);
+ return top;
}
void heap_pop(Heap* heap)
{
- _heap_remove(heap, 0);
+ _heap_remove_at_index(heap, 0);
}
void heap_clear(Heap* heap)
{
- for (UInt i = 0; i < heap->array->size; i++)
- // Extra memory releases which wouldn't be done in vector_clear()
- safe_free(((ItemValue*)(heap->array->datas[i]))->item);
- vector_clear(heap->array);
+ vector_clear(heap->items);
+ vector_clear(heap->values);
}
void heap_destroy(Heap* heap)
{
- heap_clear(heap);
- safe_free(heap->array);
+ vector_destroy(heap->items);
+ vector_destroy(heap->values);
safe_free(heap);
}
* @brief Generic d-ary heap.
*/
typedef struct Heap {
- size_t dataSize; ///< Size of a heap item in bytes.
OrderType hType; ///< Type of heap: max first (MAX_T) or min first (MIN_T).
UInt arity; ///< Arity of the underlying tree.
- Vector* array; ///< Vector of ItemValue* (internal representation).
+ Vector* items; ///< Vector of items (any type).
+ Vector* values; ///< Vector of items values (real numbers).
} Heap;
/**
*/
void _heap_modify(
Heap* heap, ///< "this" pointer.
- UInt index, ///< Index of the item to modify.
+ void* item, ///< Pointer to item to modify.
Real newValue ///< New value for the item.
);
/**
* @brief Change the value of an item inside the heap.
* @param heap "this" pointer.
- * @param item_ Item to modify.
+ * @param item Item to modify.
* @param newValue New value for the item.
* @note If several similar items are present, only the first is affected.
*
- * Usage: void heap_modify(Heap* heap, void item_, Real newValue)
- *
- * WARNING: does not work if items are not basic type nor pointers.
+ * Usage: void heap_modify(Heap* heap, void item, Real newValue)
*/
-#define heap_modify(heap, item_, newValue) \
+#define heap_modify(heap, item, newValue) \
{ \
- UInt index = 0; \
- typeof(item_) item__ = item_; \
- for (; index<heap->array->size; index++) \
- { \
- void* pItem = ((ItemValue*)(heap->array->datas[index]))->item; \
- if (*((typeof(&item__))pItem) == item__) break; \
- } \
- _heap_modify(heap, index, newValue); \
+ typeof(item) item_ = item; \
+ _heap_modify(heap, &item_, newValue); \
}
/**
*/
void _heap_remove(
Heap* heap, ///< "this" pointer.
- UInt index ///< Index of the item to remove.
+ void* item ///< Pointer to item to remove.
);
/**
* @brief Remove an item-value inside the heap.
* @param heap "this" pointer.
- * @param item_ Item to remove.
+ * @param item Item to remove.
* @note If several similar items are present, only the first is deleted.
*
- * Usage: void heap_remove(Heap* heap, void item_)
- *
- * WARNING: does not work if items are not basic type nor pointers.
+ * Usage: void heap_remove(Heap* heap, void item)
*/
-#define heap_remove(heap, item_) \
+#define heap_remove(heap, item) \
{ \
- UInt index = 0; \
- typeof(item_) item__ = item_; \
- for (; index<heap->array->size; index++) \
- { \
- void* pItem = ((ItemValue*)(heap->array->datas[index]))->item; \
- if (*((typeof(&item__))pItem) == item__) break; \
- } \
- _heap_remove(heap, index); \
+ typeof(item) item_ = item; \
+ _heap_remove(heap, &item_); \
}
/**
* @brief Return what is at the beginning of the heap.
*/
-ItemValue* heap_top_raw(
+ItemValue _heap_top(
Heap* heap ///< "this" pointer.
);
/**
- * @brief Return what is at the beginning of the heap.
+ * @brief Get the top heap element in 'item'.
* @param heap "this" pointer.
- * @param item_ Item to be assigned.
+ * @param item_ Item to affect.
*
* Usage: void heap_top(Heap* heap, void item_)
*/
#define heap_top(heap, item_) \
{ \
- void* pItem = heap_top_raw(heap)->item; \
- item_ = *((typeof(&item_))pItem); \
+ ItemValue iv = _heap_top(heap); \
+ item_ = *((typeof(item_)*) iv.item); \
}
/**
ListCell* toTrash = listI->current;
switch (direction)
{
- case FORWARD:
- listI->current = listI->current->next;
- break;
- case BACKWARD:
- listI->current = listI->current->prev;
- break;
+ case FORWARD:
+ listI->current = listI->current->next;
+ break;
+ case BACKWARD:
+ listI->current = listI->current->prev;
+ break;
}
list_remove(listI->list, toTrash);
}
{
PriorityQueue* priorityQueue =
(PriorityQueue*) safe_malloc(sizeof (PriorityQueue));
- Heap* heap = _heap_new(dataSize, pType, arity);
- priorityQueue->heap = heap;
+ priorityQueue->heap = _heap_new(dataSize, pType, arity);
return priorityQueue;
}
PriorityQueue* priorityqueue_copy(PriorityQueue* priorityQueue)
{
- PriorityQueue* priorityQueueCopy = _priorityqueue_new(
- priorityQueue->heap->array->dataSize,
- priorityQueue->heap->hType, priorityQueue->heap->arity);
- heap_destroy(priorityQueueCopy->heap); //TODO: bad style...
+ PriorityQueue* priorityQueueCopy =
+ (PriorityQueue*) safe_malloc(sizeof (PriorityQueue));
priorityQueueCopy->heap = heap_copy(priorityQueue->heap);
return priorityQueueCopy;
}
return heap_size(priorityQueue->heap);
}
-ItemValue* priorityqueue_peek_raw(PriorityQueue* priorityQueue)
+ItemValue _priorityqueue_peek(PriorityQueue* priorityQueue)
{
- return heap_top_raw(priorityQueue->heap);
+ return _heap_top(priorityQueue->heap);
}
void priorityqueue_pop(PriorityQueue* priorityQueue)
/**
* @brief Return what is at the beginning of the queue.
- * @return An ItemValue* 'iv' with iv->item = data, and iv->value its priority.
+ * @return An ItemValue* 'iv' with iv.item = data, and iv.value its priority.
*/
-ItemValue* priorityqueue_peek_raw(
+ItemValue _priorityqueue_peek(
PriorityQueue* priorityQueue ///< "this" pointer.
);
cellCopy = (SetCell*) safe_malloc(sizeof(SetCell));
cellCopy->item = safe_malloc(set->dataSize);
memcpy(cellCopy->item, cell->item, set->dataSize);
- if (prev == NULL) setCopy->head[i] = cellCopy;
- else prev->next = cellCopy;
+ if (prev == NULL)
+ setCopy->head[i] = cellCopy;
+ else
+ prev->next = cellCopy;
prev = cellCopy;
cell = cell->next;
}
TreeIteratorMode mode = treeI->mode;
switch (mode)
{
- case IN_DEPTH:
- if (!tree_is_leaf(treeI->current))
- {
- // easy case: just descend deeper in the tree
- treeI->current = treeI->current->firstChild;
- return;
- }
- // leaf: while no next sibling is available, move up
- while (treeI->current != NULL && treeI->current->next == NULL)
- treeI->current = treeI->current->parent;
- if (treeI->current != NULL)
- // run goes on from next sibling
- treeI->current = treeI->current->next;
- break;
- case IN_BREADTH:
- if (treeI->current->next != NULL)
- {
- // easy case : just move to the next sibling
- treeI->current = treeI->current->next;
- return;
- }
- // try to go to next "cousin" on same level
- if (treeI->current->parent != NULL && treeI->current->parent->next != NULL)
- {
- TreeNode* treeNodeParent = treeI->current->parent->next;
- while (treeNodeParent != NULL && tree_is_leaf(treeNodeParent))
- treeNodeParent = treeNodeParent->next;
- if (treeNodeParent != NULL)
+ case IN_DEPTH:
+ if (!tree_is_leaf(treeI->current))
{
- treeI->current = treeNodeParent->firstChild;
+ // easy case: just descend deeper in the tree
+ treeI->current = treeI->current->firstChild;
return;
}
- }
- // try to go to next level
- while (treeI->current->prev != NULL)
- treeI->current = treeI->current->prev;
- while (treeI->current != NULL && tree_is_leaf(treeI->current))
- treeI->current = treeI->current->next;
- if (treeI->current != NULL)
- treeI->current = treeI->current->firstChild;
- break;
+ // leaf: while no next sibling is available, move up
+ while (treeI->current != NULL && treeI->current->next == NULL)
+ treeI->current = treeI->current->parent;
+ if (treeI->current != NULL)
+ // run goes on from next sibling
+ treeI->current = treeI->current->next;
+ break;
+ case IN_BREADTH:
+ if (treeI->current->next != NULL)
+ {
+ // easy case : just move to the next sibling
+ treeI->current = treeI->current->next;
+ return;
+ }
+ // try to go to next "cousin" on same level
+ if (
+ treeI->current->parent != NULL &&
+ treeI->current->parent->next != NULL
+ ) {
+ TreeNode* treeNodeParent = treeI->current->parent->next;
+ while (treeNodeParent != NULL && tree_is_leaf(treeNodeParent))
+ treeNodeParent = treeNodeParent->next;
+ if (treeNodeParent != NULL)
+ {
+ treeI->current = treeNodeParent->firstChild;
+ return;
+ }
+ }
+ // try to go to next level
+ while (treeI->current->prev != NULL)
+ treeI->current = treeI->current->prev;
+ while (treeI->current != NULL && tree_is_leaf(treeI->current))
+ treeI->current = treeI->current->next;
+ if (treeI->current != NULL)
+ treeI->current = treeI->current->firstChild;
+ break;
}
}
Vector* vectorCopy = _vector_new(vector->dataSize);
vectorCopy->size = vector->size;
vectorCopy->capacity = vector->capacity;
- vectorCopy->datas = (void**) safe_malloc(vector->capacity * sizeof (void*));
- for (UInt i = 0; i < vector->size; i++)
- {
- vectorCopy->datas[i] = safe_malloc(vector->dataSize);
- memcpy(vectorCopy->datas[i], vector->datas[i], vector->dataSize);
- }
+ vectorCopy->datas = (void*) safe_malloc(vector->capacity * vector->dataSize);
+ memcpy(vectorCopy->datas, vector->datas, vector->size * vector->dataSize);
return vectorCopy;
}
void _vector_realloc(Vector* vector, UInt newCapacity)
{
- void** rellocatedDatas = (void**) safe_malloc(newCapacity * sizeof (void*));
- for (UInt i = 0; i < vector->size; i++)
- {
- rellocatedDatas[i] = (void*) safe_malloc(vector->dataSize);
- memcpy(rellocatedDatas[i], vector->datas[i], vector->dataSize);
- safe_free(vector->datas[i]);
- }
+ void* rellocatedDatas = (void*) safe_malloc(newCapacity * vector->dataSize);
+ memcpy(rellocatedDatas, vector->datas, vector->size * vector->dataSize);
safe_free(vector->datas);
vector->datas = rellocatedDatas;
vector->capacity = newCapacity;
void _vector_push(Vector* vector, void* data)
{
- void* pData = safe_malloc(vector->dataSize);
- memcpy(pData, data, vector->dataSize);
if (vector->size >= vector->capacity)
{
UInt increasedCapacity = vector->capacity > 0 ? 2 * vector->capacity : 1;
_vector_realloc(vector, increasedCapacity);
}
- vector->datas[vector->size] = pData;
+ memcpy(
+ vector->datas + vector->size * vector->dataSize,
+ data,
+ vector->dataSize);
vector->size++;
}
void vector_pop(Vector* vector)
{
- safe_free(vector->datas[vector_size(vector) - 1]);
vector->size--;
if (vector_size(vector) <= (vector->capacity >> 1))
_vector_realloc(vector, vector->capacity >> 1);
void* _vector_get(Vector* vector, UInt index)
{
- return vector->datas[index];
+ return vector->datas + index * vector->dataSize;
}
void _vector_set(Vector* vector, UInt index, void* data)
{
- memcpy(vector->datas[index], data, vector->dataSize);
+ memcpy(vector->datas + index * vector->dataSize, data, vector->dataSize);
}
void vector_clear(Vector* vector)
{
- for (UInt i = 0; i < vector->size; i++)
- safe_free(vector->datas[i]);
safe_free(vector->datas);
_vector_init(vector, vector->dataSize);
}
void vectorI_reset_end(VectorIterator* vectorI)
{
- vectorI->current = vectorI->vector->datas + vectorI->vector->size - 1;
+ vectorI->current = vectorI->vector->datas +
+ (vectorI->vector->size - 1) * vectorI->vector->dataSize;
}
bool vectorI_has_data(VectorIterator* vectorI)
{
- return (vectorI->current >= vectorI->vector->datas &&
- vectorI->current < vectorI->vector->datas + vectorI->vector->size);
+ return (
+ vectorI->current >= vectorI->vector->datas &&
+ vectorI->current <
+ vectorI->vector->datas +
+ vectorI->vector->size * vectorI->vector->dataSize
+ );
}
void* _vectorI_get(VectorIterator* vectorI)
{
- return *(vectorI->current);
+ return vectorI->current;
}
void _vectorI_set(VectorIterator* vectorI, void* data)
{
- *(vectorI->current) = data;
+ memcpy(vectorI->current, data, vectorI->vector->dataSize);
}
void vectorI_move_next(VectorIterator* vectorI)
{
- vectorI->current++;
+ vectorI->current += vectorI->vector->dataSize;
}
void vectorI_move_prev(VectorIterator* vectorI)
{
- vectorI->current--;
+ vectorI->current -= vectorI->vector->dataSize;
}
void vectorI_destroy(VectorIterator* vectorI)
* @brief Generic resizable array.
*/
typedef struct Vector {
- void** datas; ///< Data array of fixed length (reallocated if needed).
+ void* datas; ///< Data array of fixed length (reallocated if needed).
size_t dataSize; ///< Size in bytes of a vector element.
UInt size; ///< Count elements in the vector.
UInt capacity; ///< Current maximal capacity; always larger than size.
*/
typedef struct VectorIterator {
Vector* vector; ///< Vector to be iterated.
- void** current; ///< Current vector element.
+ void* current; ///< Current vector element.
} VectorIterator;
/**
projects / cgds.git / commitdiff