Hi,
maybe you remember me, some time ago I asked about how to store an
integer value into a void*, and I learned that doing pointer
arithmetic yeilding a pointer outside of an object (except the one-
after-last thingy) is undefined behaviour.
Actually I was trying to associate a function pointer with a key,
through an AVL tree that managed void* data. Function pointers can't
be stored in void* (that is, the standard does not garantee it works),
so I stored them in a dynamic array and that was the index in said
array that I wanted to store in the void* of the tree.
My frist thought was actually to store into the tree pointers to array
elements, instead of their index. The problem is, the array being
dynamic, realloc() might change its location, and then all the
pointers in my tree become invalid.
So I thought about putting in my tree pointers to array elements, and
then when realloc() changes the base, correct all the nodes of the
tree accordingly. Something like that:
fnptr* oldbase = base_of_dynamic_fnptr_array;
increase_dynamic_array_size();
fnptr* newbase = base_of_dynamic_fnptr_array;
if (oldbase != newbase)
for (void** storage_location in the tree for all nodes) {
fnptr* oldptr = *storage_location;
int index = oldptr - oldbase;
*storage_location = newbase + index; }
From what I googled this is the usual way of dealing with pointers to
elements inside a realloc()ed array, and I think it works just fine on
many platforms.
But is this garanteed to work? According to my (poor) understanding of
the standard, if realloc() returns the original pointer, then oldbase
and newbase are both valid pointers which compare equal, so there is
no problem. But if realloc() changes the location of the dynamic
array, oldbase becomes an invalid pointer. I think in that case
oldbase is garanteed to compare unequal with newbase, which is a valid
pointer, but using it to compute "index" is undefined, right?
And if the above code is not garanteed to work by the standard, is
there any portable way of handling dynamic arrays moved by realloc()?
(besides never using pointers to elements inside a dynamic array) 6 2279 li********@gmail.com wrote, On 18/04/08 16:33:
Hi,
maybe you remember me, some time ago I asked about how to store an
integer value into a void*, and I learned that doing pointer
arithmetic yeilding a pointer outside of an object (except the one-
after-last thingy) is undefined behaviour.
I remember there was a discussion about this.
Actually I was trying to associate a function pointer with a key,
through an AVL tree that managed void* data. Function pointers can't
be stored in void* (that is, the standard does not garantee it works),
Well, the C standard does not. However, if you limit yourself to a
suitable subset of C implementations you might find another standard
that does. For instance, I believe that the Posix standard provides this
guarantee, so it is possible. Note that as you are going beyond what the
C standard guarantees you need to select which implementations you are
interested in and select a method common to them.
so I stored them in a dynamic array and that was the index in said
array that I wanted to store in the void* of the tree.
My frist thought was actually to store into the tree pointers to array
elements, instead of their index. The problem is, the array being
dynamic, realloc() might change its location, and then all the
pointers in my tree become invalid.
OK, you have avoided the first trap.
So I thought about putting in my tree pointers to array elements, and
then when realloc() changes the base, correct all the nodes of the
tree accordingly. Something like that:
fnptr* oldbase = base_of_dynamic_fnptr_array;
increase_dynamic_array_size();
fnptr* newbase = base_of_dynamic_fnptr_array;
if (oldbase != newbase)
for (void** storage_location in the tree for all nodes) {
fnptr* oldptr = *storage_location;
int index = oldptr - oldbase;
*storage_location = newbase + index; }
From what I googled this is the usual way of dealing with pointers to
elements inside a realloc()ed array, and I think it works just fine on
many platforms.
But is this garanteed to work?
No.
According to my (poor) understanding of
the standard, if realloc() returns the original pointer, then oldbase
and newbase are both valid pointers which compare equal, so there is
no problem.
Correct.
But if realloc() changes the location of the dynamic
array, oldbase becomes an invalid pointer. I think in that case
oldbase is garanteed to compare unequal with newbase, which is a valid
pointer, but using it to compute "index" is undefined, right?
No, it is *not* guaranteed to compare unequal. Just evaluating it
invokes undefined behaviour and so could crash your program.
And if the above code is not garanteed to work by the standard, is
there any portable way of handling dynamic arrays moved by realloc()?
(besides never using pointers to elements inside a dynamic array)
The way to deal with it is to use indices rather than pointers.
Actually, for your problem as you need something beyond what the C
standard guarantees I would be inclined to rely on the guarantees of
Posix and the behaviour of Windows and just store the function pointers
in the void* if that would cover all the required platforms. Then the
code is far simpler.
--
Flash Gordon
In article <l4************@news.flash-gordon.me.uk>
Flash Gordon <sp**@flash-gordon.me.ukwrote:
>Actually, for your problem as you need something beyond what the C standard guarantees I would be inclined to rely on the guarantees of Posix and the behaviour of Windows and just store the function pointers in the void* if that would cover all the required platforms. Then the code is far simpler.
I tend to agree with Flash Gordon here: the engineering tradeoff
between "greater portability" and "simpler but non-portable code"
seems to be weighted towards the "simpler but non-portable" version.
You might also want to attempt, as much as possible anyway, to
isolate the non-portable code to a replaceable module, so that
in the future, when the code is moved to a machine on which the
old non-portable method fails, a new method can be substituted
with minimal pain. (The new method can either continue to be
non-portable, or chosen to be portable, depending on the newest
set of engineering tradeoffs.)
The other "obvious" option is to modify the AVL tree code, so
that the "payload" part of the tree is a union:
union avl_tree_value_union {
void *value_if_data_pointer;
void (*value_if_func_ptr)(void);
int value_if_int;
};
(which is in fact portable, but requires modifying the AVL tree
code).
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: gmail (figure it out) http://web.torek.net/torek/index.html
Flash Gordon writes:
>li********@gmail.com wrote, On 18/04/08 16:33:
>According to my (poor) understanding of the standard, if realloc() returns the original pointer, then oldbase and newbase are both valid pointers which compare equal, so there is no problem.
Correct.
No. The realloc definition does not acknowledge any original pointer.
It just says realloc deallocates the old & returns a new object.
Comparing oldbase with anything yields undefined behavior, so how do you
know realloc returned the original pointer anyway? The compiler can
catch you at it.
E.g. if it knows that some variable contains the now-indeterminate
oldbase value, it may overwrite that variable. (Well, unless the
program can detect that the bit pattern in the variable changed, I guess
- by reading the variable as character data.)
A more esoteric variant I seem to remember seeing in comp.<lang/std>.c:
If malloc/realloc can affect page maps rather than moving memory around,
the new pointer could even have the same bit representation as the old
pointer - and yet be a different pointer. And realloc need then not
ensure that the value (old pointer + pagesize) still refers to the
corresponding (new pointer + pagesize).
--
Hallvard
Hallvard B Furuseth wrote, On 20/04/08 17:49:
Flash Gordon writes:
>li********@gmail.com wrote, On 18/04/08 16:33:
>>According to my (poor) understanding of the standard, if realloc() returns the original pointer, then oldbase and newbase are both valid pointers which compare equal, so there is no problem.
Correct.
No. The realloc definition does not acknowledge any original pointer.
It just says realloc deallocates the old & returns a new object.
Comparing oldbase with anything yields undefined behavior, so how do you
know realloc returned the original pointer anyway?
You can use memcmp. Of course, it might give false negatives. However,
if the bit pattern is the same I don't see any way for it not to still
be valid.
The compiler can
catch you at it.
E.g. if it knows that some variable contains the now-indeterminate
oldbase value, it may overwrite that variable. (Well, unless the
program can detect that the bit pattern in the variable changed, I guess
- by reading the variable as character data.)
Which the program is allowed to do :-)
A more esoteric variant I seem to remember seeing in comp.<lang/std>.c:
If malloc/realloc can affect page maps rather than moving memory around,
the new pointer could even have the same bit representation as the old
pointer - and yet be a different pointer. And realloc need then not
ensure that the value (old pointer + pagesize) still refers to the
corresponding (new pointer + pagesize).
If the bit patterns of old pointer and new pointer are the same it is
difficult to see how old pointer can fail to point at the correct place.
However, the OP was explicitly talking about if the original pointer was
returned not a pointer that happened to have the same bit pattern!
I agree that there is no sensible way to check of the old pointer and
new pointer are the same and it is pointless to try.
--
Flash Gordon
Flash Gordon writes:
>Hallvard B Furuseth wrote, On 20/04/08 17:49:
>>Flash Gordon writes:
>>>li********@gmail.com wrote, On 18/04/08 16:33:
According to my (poor) understanding of the standard, if realloc() returns the original pointer, then oldbase and newbase are both valid pointers which compare equal, so there is no problem. Correct.
No. The realloc definition does not acknowledge any original pointer. It just says realloc deallocates the old & returns a new object. Comparing oldbase with anything yields undefined behavior, so how do you know realloc returned the original pointer anyway?
You can use memcmp. Of course, it might give false negatives.
And as I said below, it can give false positives too.
However, if the bit pattern is the same I don't see any way for it not
to still be valid.
What's "valid"? What does "the pointers are the same" mean? The
standard doesn't define any of this, so you have to define it first.
>The compiler can catch you at it. E.g. if it knows that some variable contains the now-indeterminate oldbase value, it may overwrite that variable. (Well, unless the program can detect that the bit pattern in the variable changed, I guess - by reading the variable as character data.)
Which the program is allowed to do :-)
Sure, but most programs don't. And while you can use memcmp and thus
freeze the bit pattern or something, it's still hard to decide just what
that means in theory. In practice it may well make sense to decide you
don't support too esoteric architectures.
After a memcmp the old pointer value and pointers computed from it
remain invalid when used as pointers, but you could use them anyway if
you are sure you've successfully protected them from the compiler (and
compilers are getting smarter all the time). Preferably you'd instead
use the new pointer and just make a note that it matches the old one,
but that doesn't help old pointers computed from the original old one.
>A more esoteric variant I seem to remember seeing in comp.<lang/std>.c: If malloc/realloc can affect page maps rather than moving memory around, the new pointer could even have the same bit representation as the old pointer - and yet be a different pointer. And realloc need then not ensure that the value (old pointer + pagesize) still refers to the corresponding (new pointer + pagesize).
If the bit patterns of old pointer and new pointer are the same it is
difficult to see how old pointer can fail to point at the correct place.
However, the OP was explicitly talking about if the original pointer was
returned not a pointer that happened to have the same bit pattern!
Yes. That's why I said it can adjust page maps. And an address range
viewed as integeres need not be a sequence of contiguous numbers.
Realloc can grow a malloced area by affecting the OS's mapping of
virtual memory to physical memory. If it needs a new page to be put at
the end of an address range, it just asks the OS to put insert a page
there and tell it the page number. Pointer arithmetic which crosses
page boundaries will need help from the virtual memory page maps.
And - since realloc invalidates all pointers into the malloced address
range, realloc might be a good time to normalize the page maps of that
address range, or something like that. Then even if the bit pattern of
a pointer to the start of the address range remains the same, the bit
pattern of the value (start of alloced area + some offset) can change.
I don't remember if that was the actual example (probably it wasn't),
but it is possible and stuff like that has been done.
I agree that there is no sensible way to check of the old pointer and
new pointer are the same and it is pointless to try.
--
Hallvard
I wrote:
Yes. That's why I said it can adjust page maps. And an address range
viewed as integeres need not be a sequence of contiguous numbers.
Realloc can grow a malloced area by affecting the OS's mapping of
virtual memory to physical memory. If it needs a new page to be put at
the end of an address range, it just asks the OS to put insert a page
there and tell it the page number. Pointer arithmetic which crosses
page boundaries will need help from the virtual memory page maps.
If this wasn't clear: The point of the nonlinear address space is, then
there need be no such concept as an unused area between two malloced
address ranges, so "there is not enough room after the malloced area"
cannot happen. As with a physical folder, you can always insert a new
page after any particular page. Until the folder bursts, anyway.
--
Hallvard This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Terence |
last post by:
I need some clarification with pointer arithmetics on void *.
Example 1:
========
char s;
char *ptr = s;
ptr += 1;
// I assume ptr is increased by 1 byte, pointing to the 2nd element in the...
|
by: Jonas |
last post by:
Hi,
I'm 99 % sure that Standard C guarantees to do a memory move inside
realloc() in case the new, returned memory block (address) is different than
the original one. Can any C expert confirm...
|
by: Walter Roberson |
last post by:
If realloc() finds it necessary to move the memory block, then
does it free() the previously allocated block?
The C89 standard has some reference to undefined behaviour if one
realloc()'s memory...
|
by: Jonathan Shan |
last post by:
Hello all,
I am trying to run a program which has dynamic array of type struct.
The program works until the line which uses realloc function to
allocate more memory.
I have tried to reproduce...
|
by: subramanian |
last post by:
I have taken the following prototype from K & R.
void *realloc(void *p, size_t size);
Suppose p was earlier allocated by malloc. Suppose I am calling realloc
with larger size value.
If...
|
by: Robert Seacord |
last post by:
The C standard doesn't say anything about what happens when you call
realloc with a size argument of 0. Both glibc and openbsd appear to
return a valid pointer to a zero-sized object.. e.g. the...
|
by: anirbid.banerjee |
last post by:
#include <stdlib.h>
#include <stdio.h>
int main(){
char *ptr = "hello";
ptr = (char *)realloc (ptr,(size_t) 10 * sizeof (char ));
printf ("\n %s", ptr);
return 0;
}...
|
by: Kenneth Brody |
last post by:
I looked at my copy of n1124, and I didn't see anything about this
particular situation...
What happens if you realloc() to a size of zero?
Implementations are allowed to return NULL on...
|
by: Francois Grieu |
last post by:
When running the following code under MinGW, I get
realloc(p,0) returned NULL
Is that a non-conformance?
TIA,
Francois Grieu
#include <stdio.h>
#include <stdlib.h>
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
| |