[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

SV: Progress Update



>>done, the job of the DynHashTable is finished. Then the HashTable needs to
>>sort the array (it now uses qsort()), and then index it (ie, create a hash
>>look-up table).
>
>>Combined, this is O(n).
>
>? qsort is O(n log(n))
>
Well, yes, but then qsort() is not the only thing happening. The indexing
needs to examine the hash value of each entry in the entry array. This is,
of course, O(n), and thus, the whole thing is, combined O(n).

>>Hmm... Wouldn't situations in which there are overlapping sub-directories
>>get nasty? I mean, if there is an a/b/c and then you mount a b at a, and
>>this b contains a c? (ie, there is already a/b/c, and you mount a
directory
>>called b at a, and this b directory contains a c).
>
>That's a different thing. I meant just mounting where no collisions happen
>(the current VFS code supports this).
>
The system I outlined still works pretty well.

>Allowing overriding of pak parts by other paks is however also a feature
>very nice for updates - no need to patch the Paks, just tell the game to
>also mount the update Paks (only containing the modified files).
>
Yes. We've talked about this before.

>But on the other hand changes in the game data are quite rare with updates,
>so this feature might be unneccessary. Dunno. We'll go without it for now
>and perhaps add it later. Perhaps.
>
That's probably the best course of action.

>Well, and the code for importing stuff from pp::internal to pp has to be
>added etc. But I guess you're right. It's not *that* much, partly because
>for PFile the code is either only in pp::internal (everything except the
>API functions) or in global space (the API functions). The picture is
>different with PSound however.
>
I thougth everything was put into ::pp::internal in C++ (including the API).
I'm not sure what way I like best. Of course, pp::ppFunc() looks a bit
weird, though.

>>First, I thougth having a header that included all external stuff form
>>::pp::internal to ::pp was the best way to go. Now, I'm more for simply,
at
>>the bottom of each header file, including the external stuff that was
>>defined in that header.
>
>Agreed. Also my preference.
>
Then I think that should be part of the, well, coding docs? Well, some docs,
anyway... :)

>>We could also simply use typedefs, so even though stuff hasn't really been
>>changed, it will look like that to new code. That's what I do to get
>>Directory to compile.
>
>Right.
>
Perhaps we should temporarily put that into PenguinPlay.h ?

>Perceps for the API reference (and internal function references for those
>wanting to help us - and for ourselves) and DocBook for tutorial / design
>discussion / background info / ...
>
Nice. I'll have a look at DocBook. I think I'll write a little something
about how to decide wheter or not to sue an allocator, and, if one is used,
which one is used.

>"Never, Ever Add A Toplevel Directory To CVS Without Clear Approval Of The
>Other PP Members !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"
>
That's not allowed?! Ooops! :)

>"PenguinPlay.h defines these custom types for portability: ..."
>"For debugging the following macros are provided:..."
>"The basic exceptions defined automatically should cover most things: ..."
>"Why telling the others of your progress from time to time is a good thing"
>etc
>
Ahh, ok. I see how that's nice to have.

>>I don't! I want to view them normally.
>
>Ah, ok. The ones I write are always also available in a ton of nice formats
>on ftpspace and as HTML via the site (not linked yet though - look at
>/penguinplay/libpplay/doc/ for now)
>
Ahh, yes. I was just curious on how to do it, as PPlay docs aren't the only
thing in .sgml I have trouble viewing. Funny thing is that MS Explorer will
happily display a .sgml file if I view it form the web. A bit wierd.

>You should be able to use almost all of the code from the existing one. It
>has quite few tree specifics.
>
I'll look into that.

>>The HashTable doesn't know about URL, or anything else. It shouldn't.
>>Directory will take care of this. HashTable just returns an entry that
>>matches a given key, if any.
>
>Good. <looking at the code> This isn't as fast as it could though - the URL
>code provides you with a string (the key) *plus* it's length *for free*.
>Actually the length is even required for processing because the string
>isn't neccessarily null-terminated. So some specialized GetEntry () method
>would be good.
>
Well, there was a reason I did all of this in templates... :)

Well, a KEY parameter of this type, and a few changes in MISC, should do the
trick.

struct Key
{
	const char* m_pURL;
	ppSizeT m_len;
};

The point is that all that is needed is to change a few lines in MISC, and
you'r set.

This is extremely slightly ineffecient. If the URL string pointer and the
length could be stored in a member-struct/class of the URL class. That way,
a reference can be used as KEY instead, and then only 4 byte is copied,
instead of 8, as is the case in the implementation mentioned above.

This all requiures minimal changes, and these are all changes that can be
done in a few minutes, and without changing the HashTable class.

>So here's the new plan:
>
>You take the PFile code, make it namespacy, and adapt the Directory stuff
>for the HashTable. After that compilation should be possible.
>
Ok. Can I download the current version of PFile and expect it not to change
untill I finish the namespace things? (for the things that are not already
namespaced)

>During that time I do the header update, add the missing DOS-style path
>support to the URL code and after that if neccessary help you with the
>other stuff (especially the ppf_PakFile* things are quite some work because
>the Pak format and the way Paks are written change).
>
>Ok?
>
Yeah. I think perhaps it would be a good idea to have a preprocessor option
of either supporting only dos-style paths, unix-style paths, or both.

We could also implement it so that all paths must be unix-style, and then we
convert to dos-style strings if on a windows platform, and we need to call
the operating system with a path.

>>if (hashTable.IsEmpty())
>>	// do something
>
>-----------------------------------
>	ppInt8 IsEmpty()
>		{return (ppInt8)(m_pHashTable);}
>-----------------------------------
>
>With that implementation your example if () thing evaluates to true if the
>HashTable is *not* empty (IsEmpty () returns 0 (== false) if the thing is
>empty). That means a negation is needed. And so the step to the conversion
>to bool isn't big. Besides that a compiler should be able to optimize the
>following pretty well:
>
Well, yes, that was one of the things I changed in the altered HashTable I
talked about in the previous mail.

>because bool values are internally just perfectly normal ints
>
Actually, its only 1 byte.

>>>* Although C++ doesn't require it, methods that may throw std::bad_alloc
>>>should tell the user of that by using a proper exception declaration
>>>(void MyMethod (...) throw (std::bad_alloc))
>>>
>>MS VC++ doesn't support this (and throws warnings all the time about it.
>
>exception declarations in general?
>That's weird. AFAIK they've been in the C++ spec for quite some time now.
>
Well, MS VC++ 5.0 *is* getting a bit old. The warning is about the fact that
MS VC++ 5.0 doesn't support this, as this was not standardised at the time
MS VC++ 5.0 was finished. It's no biggie, though, as the warning can be
turned off by code (#pragma), and it compiles fine.