Why is there no reallocation functionality in C++ allocators?
From:
http://www.sgi.com/tech/stl/alloc.html
This is probably the most questionable
design decision. It would have
probably been a bit more useful to
provide a version of reallocate that
either changed the size of the
existing object without copying or
returned NULL. This would have made it
directly useful for objects with copy
constructors. It would also have
avoided unnecessary copying in cases
in which the original object had not
been completely filled in.Unfortunately, this would have
prohibited use of realloc from the C
library. This in turn would have added
complexity to many allocator
implementations, and would have made
interaction with memory-debugging
tools more difficult. Thus we decided
against this alternative.
Pointer being reallocated wasn't allocated
Insufficient allocation - by 1.
A string of length N needs N+1 char. Cast not needed in C.
// cpr = (char *)malloc(sizeof(char)*strlen("winter-is-coming"));
cpr = malloc(strlen("winter-is-coming") + 1);
// Robust code would check for allocation success
if (cpr == NULL) {
return EXIT_FAILURE;
}
strcpy(cpr,"winter-is-coming");
Code can fail to return a good indication of the number of splits from split(). Consider char ** split("", .-) for example. Also then printf("%s\n",result[0]); is UB.
Other problems may exist.
How do I use use std::allocator in place of realloc?
Let's say I'm writing a custom vector using the std::allocator to wrap new and delete.
In the general case (excluding specializations for PODs), I don't think you could use realloc in any case. An arbitrary object, constructed at a specific memory location, might have internal pointers pointing to very specific addresses in relation to the address in which it was constructed. Simply moving it around (in the byte-copying sense) could break invariants.
Thus the alternative you mention is in general necessary. You would have to allocate a new array, move (or possibly even copy!) the objects to the new location, then deallocate the old array. Of course, this includes more than a single stage that can fail - another reason why you can't really reallocate in the general case. Perhaps this is the reason that allocators never had this functionality in the first case - for array-based containers, you can't really use them in general (although you might be able to use them for POD specializations).
Memory allocation/reallocation question
Here's a minimum working version (with C++ keywords for lots of identifiers -- I kinda apologize, but it looked fun when I started and I couldn't stop or go back midway through) which also runs on ideone ( http://ideone.com/iMByR )
#include <stdio.h>
#include <stdlib.h>
struct protected {
int this;
int (*catch)(int, int);
int friend;
};
int catch(int mutable, int virtual) {
return mutable + virtual;
}
struct protected *add_one(struct protected **private,
int *explicit, int using,
int (*catch)(int, int), int friend) {
struct protected *new;
new = realloc(*private, (*explicit + 1) * sizeof *new);
if (new) {
*private = new;
(*private)[*explicit].this = using;
(*private)[*explicit].catch = catch;
(*private)[*explicit].friend = friend;
(*explicit)++;
}
return new;
}
/* create an array of structs using dynamic memory */
/* keep adding elements to it, and growing it as needed */
int main(void) {
int using;
/* explicit contains the number of elements in the try array */
int explicit = 0;
struct protected *try = NULL;
/* create and grow */
for (using = 0; using < 7; using++) {
if (add_one(&try, &explicit, using + 1, catch, 0) == NULL) {
fprintf(stderr, "failure at loop %d\n", using);
exit(EXIT_FAILURE);
}
}
/* verify */
for (using = 0; using < explicit; using++) {
printf("%d: %d\n", using, try[using].this);
}
free(try);
return 0;
}
Reallocation/allocation of memory in c
I always hated realloc. If you are ok to avoid it, here's what I suggest :
Some points about your code, regardless of the problem :
- in C it is better to declare all the variables at the start of any function. If possible, never declare a variable in middle of the code.
- You can declare variable inside
forblock though. However it doesn't work in all version of C. Depends on the compiler. - Unless you will deploy this code on some device with really limited memory, you don't necessary have to use
unsigned short. Classic integers would do. - It is recommended to check if every malloc went well. And if not, to do the necessary actions to avoid crash.
Code :
#include <stdio.h>
#include <stdlib.h>
int min(int a, int b) {
return (a < b) ? a : b;
}
void updateDimensions(int*** currentArray, unsigned short currentRowsNb, unsgined short currentColumnsNb, unsigned short newRowsNb, unsigned short newColumnsNb) {
int i;
int j;
int error;
int** res;
if(*currentArray != NULL && (newRowsNb != currentRowsNb || newColumnsNb != currentColumnsNb)) {
error = 0;
/* Memory allocation */
res = (int**)malloc(newRowsNb* sizeof(int*));
if(res != NULL) {
for(i=0 ; i < newRowsNb; i++) {
res[i] = (int*)malloc(newColumnsNb* sizeof(int));
if(res[i] == NULL) {
error = 1;
fprintf(stderr, "allocation error"); // Optional
while(--i >= 0)
free(res[i]);
free(res);
}
}
} else {
fprintf(stderr, "Allocation error);
error = 1;
}
/* End of memory allocation */
if(!error) {
/* Copy of the array */
for(i=0 ; i < min(currentRowsNb, newRowsNb) ; i++)
for(j=0 ; j < min(currentColumnsNb, newColumnsNb) ; j++)
res[i][j] = (*currentArray)[i][j];
/* End of copy */
/* Free current array */
for(i=0 ; i < currentNrRows ; i++)
free((*currentArray)[i]);
free(*currentArray);
/* End of free */
*currentArray = res; // Assign new array to current one.
}
}
}
unsigned short maxim(unsigned short A[100]) {
unsigned short max = 0;
unsigned short i;
for(i = 0 ; i < 100 ; i++)
if(A[i] > max)
max = A[i];
return max;
}
void main() {
/* Variable declaration */
unsigned short i;
unsigned short j;
unsigned short k;
unsigned short ok;
unsigned short max;
unsigned short maxA;
unsigned short nrRows;
unsigned short my_bool;
unsigned short nrColomns;
unsigned short A[100];
int swap;
int newNrRows;
int newNrColumns;
int tempInt;
int **V;
FILE *pFile;
/* Variable initialization */
pFile = fopen("test.txt", "r");
if(pFile == NULL)
return;
fscanf(pFile, "%d", &nrRows);
fscanf(pFile, "%d", &nrColomns);
max = 0;
my_bool = 1;
for(i=0 ; i < 100 ; i++)
A[i] = '\0';
/* Memory Allocation */
V = (int**)malloc(nrRows * sizeof(int*)); /* Number of lines */
if(V == NULL) {
fprintf(stderr, "Allocation error"); // Writes in the error output (optional)
return;
}
for (i = 0; i < nrRows; ++i)
V[i] = (int*)malloc(nrColomns * sizeof(int)); /* Number of colomns */
/* If allocation error */
if(v[i] == NULL) {
fprintf(stderr, "Allocation error"); // Optional
/* The following is mandatory */
while(--i > 0) { // Free all cell already allocated
free(A[i]);
}
free(A);
return;
}
}
/* End of memory allocation */
/* Read the elements */
for (i = 0; i < nrRows; ++i)
for (j = 0; j < nrColomns; ++j)
fscanf(pFile, "%d", &V[i][j]); // That assume you only have digit (0 to 9) in your file.
/* If you have a delimiter between numbers (here i'll take ';' as example, use this */
fscanf(pFile, "%[^;]%*d", &v[i][j]);
/* If you have many delimiters (here ';', ' ' and '\n' as example) */
fscanf(pFile, "%[^;\n ]%*d", &v[i][j]);
/* End of reading
/* Find max + array */
for (i = 0; i < nrRows; ++i)
for (j = 0; j < nrColumns; ++j) {
/* How many times each value between [0 and 100) is found inside the matrix */
A[V[i][j]]++;
/* Find the biggest element */
if (V[i][j] > max)
max = V[i][j];
}
/* Memory Reallocation */
maxA = maxim(A);
if (maxA > nrColomns) {
newNrColumns = maxA;
ok++;
}
if (max + 1 > nrRows) {
newNrColumns = max + 1;
ok++;
}
if (ok != 0) {
updateDimensions(&V, nrRows, nrColumns, newNrRows, newNrColumns);
nrRows = newNrRows;
nrColumns = newNrColumns;
}
/* Rearrange Values */
while (my_bool != 0) {
my_bool = 0;
for (i = 0; i < nrRows; ++i) {
for (j = 0; j < nrColomns; ++j) {
if (V[i][j] != i) {
/* Swap elements */
k = 0;
while (k < nrColomns) {
if (V[V[i][j]][k] != V[i][j]) {
my_bool = 1;
/* Do the swapping */
swap = V[V[i][j]][k];
V[V[i][j]][k] = V[i][j];
V[i][j] = swap;
break;
} else {
k++;
}
}
}
}
}
}
/* Extra Reallocation */
if (maxA < nrColomns) {
newNrColumns = maxA;
updateDimension(&V, nrRows, nrColumns, newNrRows, newNrColumns);
}
/* Print Result into file */
fclose(pFile);
pFile = fopen("out.txt", "w");
if(pFile == NULL) {
fprintf(stderr, "Error while openning file");
} else {
fprintf(pFile, "%d %d \n", nrRows, nrColomns);
for (unsigned short i = 0; i < nrRows; ++i) {
for (unsigned short j = 0; j < nrColomns; ++j)
fprintf(pFile, "%d ", V[i][j]);
fprintf(pFile, "\n");
}
fclose(pFile);
}
_getch();
/* Memory Deallocation */
for (i = 0; i < nrRows; ++i)
free(V[i]);
free(V);
}
NB : I did not try to compile this, it might have errors (especially on things like : (*currentArray)[i][j] ). Also, sorry for bad English ^^'
Can alloca() memory be reallocated?
No: that wouldn't work with a stack as commonly implemented. A variable on the stack occupies a fixed range of addresses. The next variable comes immediately after it, so there's no room to grow. Consider a function like this:
void f(int x) {
int i;
float *a = alloca(40 * sizeof(float));
int k;
…
}
The stack after the function prologue looks something like this:
----------------+-----+-----+-----+-------------------+-----+---------------------
... | ret | x | i | a | k | ...
----------------+-----+-----+-----+-------------------+-----+---------------------
^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^
previous frames f's frame free space at the top
There's no room to grow a.
I'm showing a highly simplified example: in the real world, variables end up in registers, variables can be reordered even if they do end up on the stack, etc. But only one variable can be the last one on the stack with room to grow.
So if realloca existed, it could only be applied to the variable that's at the top of the stack. (Or else it would have to move everything else that's on top of it, but that would require updating all existing pointers to those, which is not possible in general.) This would be a very limited mechanism, so support for this feature would have a very small benefit. Supporting it would have a significant cost, because compilers are normally free to put things on the stack in the order they want: this feature would require a new mechanism to let the compiler know that one specific variable must go to the top.
It's possible that some C implementation somewhere has realloca, but it's unlikely given the cost/benefit ratio.
Of course realloca can easily be implemented if alloca does not use a stack allocation strategy. But allocating on the stack is the whole point of alloca. If you want resizable objects, you need a memory management structure with a heap interface, and that's what malloc is for.
As a practical matter, there are several possible approaches to dynamic memory management in a library.
The most common approach is to call malloc, realloc and free when you need them. That's what they're for.
In some environments, it's useful to support custom allocators. You can give the user of the library the option to pass pointers to alternative implementations of malloc, realloc and free. It's useful when you want to write a portable library that needs to be used by code that is itself fully portable. Most of the time, though, users who want to use custom allocators can do it by linking their own malloc and friends. And even that is rarely useful.
If you need code that can work in an environment without dynamic allocation (such as safety-critical environments), then you should not use alloca either. alloca is worse than malloc because it causes unpredictable stack usage and can lead to a stack overflow which won't be detected at all, or which will only be detected by a program crash. If you need a variable (or large) amount of temporary memory in a function, have the user pass a suitably-sized buffer to you.
/** [documentation of the function] …
* working_buffer must point to an array of floats of 3*n elements.
*/
void f(size_t n, float *working_buffer);
Better, if you have the code size budget, pass the array size and verify it.
/** [documentation of the function] …
* working_buffer must point to an array of floats of 3*n elements.
*/
int f(size_t n, float *working_buffer, size_t working_buffer_length)
{
if (working_buffer_length < 3 * n) return -EINVAL;
…
}
Related Topics
Fatal Error: "No Target Architecture" in Visual Studio
What Are Unevaluated Contexts in C++
Passing Functor as Function Pointer
How to Make G++ Preprocessor Output a Newline in a MACro
How to Convert a Struct Tm (Expressed in Utc) to Time_T Type
Disambiguate Overloaded Member Function Pointer Being Passed as Template Parameter
Possible Problems with Nominmax on Visual C++
Is It Counter-Productive to Pass Primitive Types by Reference
C++ Equivalent to Designated Initializers
Does Constraint Subsumption Only Apply to Concepts
Unresolved External Symbol Lnk2019
Why Does Storing References (Not Pointers) in Containers in C++ Not Work
Typeid' Versus 'Typeof' in C++
Class Type Non-Type Template Parameter Initialization Does Not Compile