I'm developing a custom dynamically scaled array module that aims to minimize the number of realloc calls while maintaining efficient memory usage. The module utilizes a strategy of doubling the allocated size when adding elements and decrease it to enough when removing elements. However, this approach leads to frequent realloc calls during element removal, as demonstrated in the following example:
| Allocated Size | Used Size | Removed Size | New Used Size | Enough Size | Realloc Called | Reallocated Size |
|---|---|---|---|---|---|---|
| 32 | 18 | 2 | 16 | 32 | No | - |
| 32 | 16 | 1 | 15 | 30 | Yes | 30 |
| 30 | 15 | 1 | 14 | 28 | Yes | 28 |
| 28 | 14 | 1 | 13 | 26 | Yes | 26 |
As evident from the example, realloc is invoked almost every time an element is removed. To address this issue, I seek a strategy to minimize realloc calls while adhering to the policy of doubling the allocated size when adding elements and decrease it to enough when removing elements.
Code:
#define DSA_USED_SIZE(dsa) ((dsa->length) * (dsa->elementSize))
typedef struct DSA
{
void *data;
size_t length;
size_t allocatedSize;
size_t elementSize;
} DSA;
// This is called before single or multiple items added.
int dsa_add_size_handle(DSA *dsa, size_t addSize)
{
if (dsa->allocatedSize >= DSA_USED_SIZE(dsa) + addSize)
{
return 1;
}
size_t newSize = 2 * (DSA_USED_SIZE(dsa) + addSize);
void *temp = realloc(dsa->data, newSize);
if (temp == NULL)
{
perror("_dsa_add_size_handle: ");
return 0;
}
dsa->data = temp;
dsa->allocatedSize = newSize;
return 1;
}
// This is called after single or multiple items removed.
int dsa_remove_size_handle(DSA *dsa, size_t removeSize)
{
if (dsa->allocatedSize <= 2 * (DSA_USED_SIZE(dsa) - removeSize))
{
return 1;
}
size_t newSize = 2 * (DSA_USED_SIZE(dsa) - removeSize);
if (newSize == 0)
{
newSize = 2 * dsa->elementSize;
}
void *temp = realloc(dsa->data, newSize);
if (temp == NULL)
{
perror("_dsa_remove_size_handle: ");
return 0;
}
dsa->data = temp;
dsa->allocatedSize = newSize;
return 1;
}