Programming

It likely does return the SAME pointer every-time (and if it doesn't it's likely freeing the pointer it returned the previous time). What changes is the data within the region to which the pointer points, the data "inside" the pointer if you will.
Because you're now complying with the contract proposed by readdir.
Even if you didn't realloc, you'd have the same problem. Nothing is "corrupting" anything after you realloc. It's the fact that as we both said above, the next time you call readdir (which so happens to coincide with the realloc call) the data from the previous call is overwritten.

Also...your incrementing the size with <<= 1 may be a little more...extreme than you'd like. I hope you know exactly why you're doing that. The array size you'll be allocating will grow quite quickly. If there just so happen to be 257 entries in the directory you'll jump your array to 512 entries to hold them...you may prefer to jump in additive steps rather than exponential...but that's just my humble opinion. Even better still, use a linked list and there will be no wastage.

Never more than twice as much memory as is currently used. It'll be sane enough unless there's frankly insane numbers of directory entries. Reducing the number of times you call malloc() for tiny things cuts down on memory fragmentation, and once the readdir() loop finishes he's free to shrink it, too.

Ever try calling qsort() on a linked list? I swear, the amount of time some programs take to sort things is simply obscene, and could've been avoided if they'd kept it in a numerically-addressable form.

)) I am totaly with Corona688.
There is good video, in my opinion, on STL at channel9.msdn.com
starting with 17th minute he explains why multiplying is better then addition in memory allocation.
Sorting with qsort is the next what i am going to do with this array.

---------- Post updated at 02:51 AM ---------- Previous update was at 02:49 AM ----------

C9 Lectures: Stephan T. Lavavej - Standard Template Library (STL), 1 of n | Going Deep | Channel 9

I'm not convinced on the fragmentation "issue". It may speed things up because you call malloc fewer times, but you'd need to know how your malloc works to know if fragmentation will be an issue. Since most malloc implementations use pools for various sizes anyway, I don't see calling realloc with smaller jumps as bad. Once you call it with a large enough amount to matter then you're in the large pool and either filling in gaps or pushing out the break point.

Though...I suppose on your side, calling malloc with large sizes typically does nothing anyway until the pages are touched...so...it's not as if your calling malloc and asking for a gig (on most operating systems anyway) is going to hurt unless you start actually putting data into the pages "given" to your process when it (inevitably) calls brk.

Either way...it's a blanket statement that one is better than the other. If you had a process that was multi-threaded and read ten million items in with ten threads would you ask for it exponentially in each thread? If you did you would probably regret it, because you'd likely reach the memory limits of a 32 bit process and your mallocs would start failing and you'd have to back down to an additive method at some point.

Anyway, maybe I need to "think on it" some more, but for now I remain unconvinced.

P.S. I'd watch that video...but I don't have Silverlight installed on my Linux machine.

A bit of fragmentation doesn't hurt malloc() much. A small percentage of wasted space? Boo hoo. Unless it's truly horrific you'd never notice or care.

The cost of fragmentation for repeated realloc() is exponentially-growing wasted CPU time as your existing data leapfrogs through every available heap hole in order of size. I think that's worth minimizing.

If you knew the sizes of your heap pools, you could aim large enough to probably be at the end of a pool but small enough to not spill into the next one. We don't, but exponential growth is a decent approximation.

To a point, anyway. For ludicrous sizes I'll admit a cap might be good. I think that kind of situation needs careful tuning no matter what allocation method you pick.

I might use large fixed-size blocks of memory anonymously mmap()-ed in, one to a thread. That'd let you parcel out fractions of address space pretty precisely without exhausting your memory map or wasting memory. If you knew a little about your address space you could pick an entire contiguous region for them and MAP_FIXED things into place to prevent your address space from growing motheaten.

You could even extend that to accommodate more items than you can hold in your address space by making the mappings file-backed... if you fill a mapping, just truncate() the file one chunk larger and move your map further into the file. This'd also prevent you from exhausting system memory and swap. To sort it, you could qsort in chunks then merge the chunks.