3 ms·
> I use the standard library function realloc. Realloc may automatically copy the range to a new memory block if the old block cannot be expanded, and when tha
by kbenson 10y ago
> I use the standard library function realloc.
Realloc may automatically copy the range to a new memory block if the old block cannot be expanded, and when that happens the old range is freed. Any other pointers you had to items in that original array may become invalid every time realloc is called, and if it's automated by your dynamic array code, that could conceivably be any time you push an item onto that array.
This is the waterbed theory of complexity. You can push complexity down in one part, but that just causes it to pop up somewhere else. You can make array size management easier, but the cost is that when it needs to deal with array sizing it's abstracted away to the point where you can't be sure when it happens and when you need to fix problems it might cause, or you can deal with it up front and manually when needed and then when you are manually dealing with the size changes you should remember that the memory might be freed and you may need to deal with that. GC languages deal with this by having all the information to know exactly how to fix all the references needed, and Rust deals with it by requiring you to not have two references to the memory in that circumstance.
- lacampbell 10y agoI am still perplexed why you think by using a dynamic array of chars for a buffer, it somehow involves me storing copies of the malloc'd memory anywhere. You can simply access data by copying it: https://ideone.com/OObuAt https://ideone.com/OObuAt Note that it still prints 42 despite the allocated memory being freed. Line 7 copies the data at a specified index into x - x has no references to the malloc'd memory.
- kbenson 10y ago> I am still perplexed why you think by using a dynamic array of chars for a buffer Because I'm not limiting the case to just core types. You don't only ever need arrays of chars, ints, doubles, floats, etc. Sometimes you need arrays of structs. As a simplistic example, perhaps you have a large array of structs, and you want to iterate through them and add all the items that match your criteria to a shorter array of matches, which will be pointers to the real data. Adding a single item to the original array could cause realloc to invalidate every pointer in the array of matches. Of course there are ways around this, but someone starting work on the code might not necessarily expect that adding an item to an array would cause pointers elsewhere in the code to become invalid, unless they look at the implementation of your array code to understand what it's doing.
- lacampbell 10y agoSo basically, your argument boils down to "well what if the person who implements the dynamic array doesn't know C properly and provides an API that exposes the internal realloc'd memory?". Because if not, I have no idea what kind of insane dynamic array implementation you have in mind. There is no way you should be able to access pointers to the internal memory from the API of a dynamic array. Here's how it works - if your array is of malloc'd structs, then when you access the element, you get back a malloc'd struct. At no point can you access the actual memory, only copies of the values contained at a given index. So yes, I suppose if your bounds checked dynamic array was implemented by a complete novice or someone that doesn't know C, your hypothetical scenario could happen. None of this changes the fact that it's easy for a competent C programmer (do I really need to specify this?) to completely avoid buffer overflows in his own code, which is the only thing I have argued.
- kbenson 10y agoWe seem to be talking past each other. I created a bit of sample code ot show exactly what I'm talking about, it's at https://gist.github.com/kbenson/fbc585d6a6144a2a9f1ef340b9135a2e https://gist.github.com/kbenson/fbc585d6a6144a2a9f1ef340b913.... The basic idea is that sometimes you might want a pointer to an array item, if that item is complex, not just a copy of it, as there's no need to be wasteful if it's a fairly large struct. Any pointers to that array might be invalidated if realloc is called on it. Knowing exactly when that happens means you can note that it might be invalid, and do something about it, but if it can happen any time you add items to the array, that means you need to check for whether it was reallocated every time, or assume it's always invalidated whenever you push an item on the array. In the example here, I'm determining the struct with the smallest num field. As I keep allocating space to the array (which I'm doing explicitly here), I'm doing the incorrect thing, which is assuming I can continue to use the pointer, which may no longer be valid and just checking if any of the new items are smaller than the existing smallest. I should be recomputing from scratch. It's obvious when I'm calling realloc, but if I was just pushing new items to the array, it would not be obvious at what point it reallocated to a new location in memory unless I specifically checked. What's happened in that case is we've traded the complexity of explicitly controlling memory allocation of arrays for the complexity of either not allowing pointers to array items or having to keep track of the array location with a separate pointer and checking that they are still the same prior to using any pointers to array items we've stored.