On 10/29/05, Mike Kluev <email@hidden> wrote:
> On Fri, 28 Oct 2005 17:07:17 Lawrence Sanbourne <email@hidden> wrote:
>
> > On Oct 28, 2005, at 4:54 PM, Laurence Harris wrote:
> >
> >> No. You're going to have to allocate memory somehow as you add more
> >> items to
> >> the array anyway.
> >
> > But with a C array I have to reallocate the entire array, rather than
> > just being able to add entries to the end of it as I go, as with a
> > linked list.
>
> True, but see below.
And I did....
> >>> Do you think it's worth it to make my own simple linked list
> >>> struct?
> >>
> >> I wouldn't, not if I wanted the advantages of an array. A linked
> >> list is a very different beast and is best for different operations
> >> than those at which an array excels.
> >> ...
> >> You get the advantages of contiguous memory, the easy of use of vectors,
>
> Why do you think there is an advantage of using continuous memory and
> vectors in this case (iterating directory structure)? I don't see the
> need for random access here. Yes, arrays are typically considered
> easier than linked lists, but there are cons as well.
Note that you're commenting on Laurence Harris's words, not mine.
I agree, there's no need for random access, and that's why I proposed
a linked list. The extra space needed for the links is trivial; STL
vectors would definitely use more memory. They also have O(1) access
time, but this access time is likely to be slower than accessing array
or a linked list that you're in the middle of traversing [both O(1) as
well, but faster time-wise].
> > Since I'm just iterating straight through this collection, a linked
> > list would be fine.
>
> Yes, but see below.
>
> > I didn't know about PtrAndHand! Very cool. Do you think it would be
> > more efficient to use a linked list since this will never require
> > relocating allocated memory (no doubt a costly operation)?
>
> WinAPI's FindFirst just allocate the whole directory structure in one
> handle making a "snapshot" and the subsequent FindNexts just read from
> this handle. This has the advantage of atomic (consistent) result: you
> won't get inconsistent result if the directory changing while you
> iterating over it. You may try doing the same by allocating memory for
> all items and making a single GetBulkInfo call, thus eliminating the
> need for reallocate or using linked list structures. Though, the
> problem with this is that the number of files in the directory might
> change after you've called FSGetCatalogInfo on the parent (to know
> its valence = number of sub items in it) and before you call
> FSGetCatalogInfoBulk to grab that many items.
Not all filesystems support valence, so that's a bit tough.
I'm unconcerned about getting inconsistent results if the directory
changes while iterating over it. For my application, the directories
are so small that this is very unlikely. And for larger directories,
it just doesn't seem worth the extra memory footprint.
Larry
--
Larry Sanbourne
email@hidden
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Carbon-dev mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/carbon-dev/email@hidden
This email sent to email@hidden
