Closed Bug 125849 Opened 23 years ago Closed 23 years ago

Make PLDHashTable instances that are easy to use from C++

Categories

(Core :: XPCOM, defect)

Product:
Core
Component:
XPCOM
Platform:
x86
All
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED FIXED

People

(Reporter: john, Assigned: john)

References

Details

(Whiteboard: [FIX])

Attachments

(2 files, 15 obsolete files)

Patch v1.2
14.54 KB, patch
alecf
: review+
brendan
: superreview+
Details | Diff | Splinter Review
Macro-based hashtable v1.0.7
31.12 KB, patch
Details | Diff | Splinter Review
We need easy to use accessors for PLDHashTable. For me, for now, I just need an easy hashtable for nsAString -> nsISupports*. This is a fairly common case, and would be useful to many people. Patch in a moment.
Attached patch PLDHashTableStringSupports (obsolete) — — Splinter Review
This essentially lets you simply instantiate your hashtable and do Get(), Put() and Remove(). I am using it for the radio button patch, bug 108308, and it is working fine.
Blocks: 108308
Cc'ing myself (what, you think I don't care about C++ users who find C hard to use? :-). /be
Comment on attachment 69819 [details] [diff] [review] PLDHashTableStringSupports First let me say thanks for doing this, because based on your work, I'm going to WONTFIX bug 72722 on the conclusion that nsDHashTable should be used where possible and necessary for perf/footpring, and nsHashtable can continue where its memory effects don't matter. >diff -u -r1.61 Makefile.in >--- xpcom/ds/Makefile.in 24 Jan 2002 06:48:25 -0000 1.61 >+++ xpcom/ds/Makefile.in 16 Feb 2002 05:17:57 -0000 >@@ -72,6 +72,7 @@ > nsTextFormatter.cpp \ > nsTimelineService.cpp \ > nsValueArray.cpp \ >+ PLDHashTables.cpp \ This may seem confusing if you're coming from the pldhash.h direction, but my first reaction is that the name should be nsDHashTable (probably not nsDoubleHashTable, nsDblHashTable, or even nsDoubleHashtable [note lowercase t], although the last is most consistent with (a) Java, (b) xpcom/ds/nsHashtable.h, and (c) prevailing file naming conventions). Gory details: kipp imitated Java's Hashtable InterCaps violation (I suppose avh or someone early in Java's development believed that "hashtable" is one word, not two). But nsHashtable wraps PLHashTable. NSPR1 purveyed PRHashTable along with other PR* things that became PL, for Portable Library/Libc instead of Portable Runtime. Several PL data structures got kicked out to xpcom from nsprpub during Mozilla development. When I created pldhash.[ch], whose primary sources are js/src/jsdhash.[ch], mirrored into xpcom via js/src/plify_jsdhash.sed, I upheld the PL prefix for consistency and tradition's sakes. Comments? Now that I've gone through the history, I'm warming up to nsDoubleHashtable. In any case, I think the nsFoo class naming rules trump PLFoo here. >+// >+// ENTRY StringSupports >+// >+class PLDHashStringSupportsEntry : public PLDHashStringEntry >+{ >+public: >+ PLDHashStringSupportsEntry(const nsAString& aString) : >+ PLDHashStringEntry(aString), mVal(nsnull) >+ { >+ } >+ ~PLDHashStringSupportsEntry() { >+ NS_IF_RELEASE(mVal); >+ } >+ nsISupports* mVal; >+}; Use an nsCOMPtr for mVal, or you'll leak here: >+ >+PR_STATIC_CALLBACK(void) >+PLDHashStringSupportsClearEntry(PLDHashTable *table, PLDHashEntryHdr *entry) >+{ >+ PLDHashStringSupportsEntry *e = NS_STATIC_CAST(PLDHashStringSupportsEntry *, >+ entry); >+ // An entry is being cleared, let the entry its own cleanup. >+ e->~PLDHashStringSupportsEntry(); >+} You'll need to destruct mVal explicitly, or just set it to nsnull (better). >+PRBool isLive = PL_DHashTableInit(&mHashTable, \ >+ &hash_table_ops, nsnull, \ >+ sizeof(_HASHNAME_##Entry), 16); \ >+NS_ENSURE_TRUE(isLive, NS_ERROR_OUT_OF_MEMORY); You want to set mHashTable.ops = nsnull on failed PL_DHashTableInit, and cope with non-null ops on entry, in order to catch double-Inits (this means the ctor must null mHashTable.ops, if you don't use a zero'ing new). >+PLDHashTableStringSupports::~PLDHashTableStringSupports() >+{ >+ PL_DHashTableFinish(&mHashTable); >+} Defend against OOM error on Init by Finishing iff mHashTable.ops. >+nsresult >+PLDHashTableStringSupports::Get(const nsAString& aKey, nsISupports** aResult) >+{ >+ PLDHashStringSupportsEntry * entry = >+ NS_STATIC_CAST(PLDHashStringSupportsEntry *, >+ PL_DHashTableOperate(&mHashTable, &aKey, >+ PL_DHASH_LOOKUP)); >+ if (!PL_DHASH_ENTRY_IS_LIVE(entry)) { Set *aResult = nsnull here, do not assume the caller did that (aResult is not inout). >+ return NS_OK; >+ } >+ >+ *aResult = (nsISupports*)entry->mVal; Why the cast here? >+ NS_IF_ADDREF(*aResult); >+ return NS_OK; >+} >+ >+nsresult >+PLDHashTableStringSupports::Put(const nsAString& aKey, nsISupports* aResult) >+{ >+ PLDHashStringSupportsEntry * entry = >+ NS_STATIC_CAST(PLDHashStringSupportsEntry *, >+ PL_DHashTableOperate(&mHashTable, &aKey, >+ PL_DHASH_ADD)); >+ >+ NS_ENSURE_TRUE(entry, NS_ERROR_OUT_OF_MEMORY); >+ >+ // >+ // If an entry was there, de-add-ref it >+ // >+ NS_IF_RELEASE(entry->mVal); >+ >+ // >+ // Add the entry and add-ref it >+ // >+ entry->mVal = aResult; >+ NS_IF_ADDREF(entry->mVal); This all gets much better if you use nsCOMPtr<nsISupports> for mVal. >+ >+ return NS_OK; >+} >+ >+nsresult >+PLDHashTableStringSupports::Remove(nsAString& aKey) >+{ >+ PL_DHashTableOperate(&mHashTable, &aKey, PL_DHASH_REMOVE); >+ return NS_OK; >+} [snip...] >+class PLDHashTableStringSupports { >+public: >+ PLDHashTableStringSupports(); >+ ~PLDHashTableStringSupports(); >+ >+ /** >+ * Get the value referenced by the key. >+ * Being a getter, this returns a strong reference. >+ * @param aKey the key >+ * @param aResult the return value >+ */ >+ nsresult Get(const nsAString& aKey, nsISupports** aResult); I was wondering whether it pays to use this kind of signature when there is no failure case. Why not return an already_AddRefed<nsISupports> as the result of the function, and do away with the out paramete? Faster, smaller (I hope! dbaron can say) code, more foolproof to boot. >+ >+ /** >+ * Put the value into the hash to be referenced by the key. >+ * @param aKey the key >+ * @param aResult the return value >+ */ >+ nsresult Put(const nsAString& aKey, nsISupports* aResult); Put can fail due to OOM, so this is ok. Mac build-fu is still beyond me, just checking. /be
Attachment #69819 - Flags: needs-work+
Craving dbaron's feedback on cost and worth of already_AddRefed<T> for infallible getters that return a held XPCOM object ref, or nsnull. /be
Returning |already_AddRefed<T>| should be just like returning |T*|, but I haven't actually looked at disassembly to check (although I *think* I remember checking that a binary didn't increase in size when converting to it).
s/just like/just like (for footprint and speed)/
There's something I'm missing here ... > Use an nsCOMPtr for mVal, or you'll leak here: I don't get why this will leak, when we are releasing mVal in the destructor? I'm happy to make it an nsCOMPtr, though. It *will* make the rest of the code simpler, as you pointed out later. I assume nsCOMPtr<> takes up 4 bytes total, right? (If not, then I think we're better off leaving it a normal pointer. The possibility of leaking is contained in this file, and not transferred to clients of PLDHashTableStringSupports.) > You'll need to destruct mVal explicitly, or just set it to nsnull (better). NS_IF_RELEASE in the destructor should handle both of these, and it makes the code more uniform-seeming (destructors are the right place to destroy objects) ... I guess I don't mind doing this either (though I'm more dubious about it), but what's the reason? > Why not return an already_AddRefed<nsISupports> as the result of the function, and do away with the out parameter? Sure. I am just too accustomed to making interfaces IDL-izable, I guess :) Is there any reason we'd ever want to make this class scriptable?
>> Use an nsCOMPtr for mVal, or you'll leak here: > >I don't get why this will leak, when we are releasing mVal in the destructor? Who calls that destructor? Certain not PLDHashStringSpuportsClearEntry, which must do it or there will be leaks. Placement-new requires explicit dtor calls, IIRC. >I'm happy to make it an nsCOMPtr, though. It *will* make the rest of the code >simpler, as you pointed out later. I assume nsCOMPtr<> takes up 4 bytes >total, right? Of course. >> You'll need to destruct mVal explicitly, or just set it to nsnull (better). > >NS_IF_RELEASE in the destructor should handle both of these, and it makes the >code more uniform-seeming (destructors are the right place to destroy objects) >... I guess I don't mind doing this either (though I'm more dubious about it), >but what's the reason? The PLDHashTableOps.clearEntry hook must call the dtor, or leak soup for you! >> Why not return an already_AddRefed<nsISupports> as the result of >the function, and do away with the out parameter? > >Sure. I am just too accustomed to making interfaces IDL-izable, I guess :) See the summary -- "easy to use for C++ users" is the watch-word here. IDL is all about language-neutral definition. We don't need it here. >Is there any reason we'd ever want to make this class scriptable? No, scriptable interfaces should be higher level, and JS and all other scripting languages have even easier to use associative arrays as built-in features, so it'd be redundant. /be
Summary: Make PLDHashTable instances that are easy to use → Make PLDHashTable instances that are easy to use from C++
Keep in mind that using nsCOMPtrs (or objects of any class, for that matter) as members of pldhash entries is potentially dangerous since they may be moved around in memory as the pldhash size changes. From what I can tell, nsCOMPtrs should be fine though (and nsString and nsXPIDLString are fine too AFAICT).
nsCOMPtr can be copied with memcpy, no problemo. If there were a need to copy-construct in a non-byte-copying fashion, the PLDHashTableOps.moveEntry hook awaits! /be
> Who calls that destructor? Certain not PLDHashStringSpuportsClearEntry, which must do it or there will be leaks. The issue in question was that PLDHashStringSupportsClearEntry *does* call the destructor, rather than having the work done in ClearEntry itself. I personally prefer this, as I would rather make destruction happen in the destructor than in an external function. It feels safer and it feels more *right*. This is not unprecedented, BTW. The patterns (and code) I followed to make use of PLDHashTable were the ones in nsDocument. I'll post a new patch later tonight or tomorrow morning, following testing (the version I just now produced with nsCOMPtr<> is not working with my radio buttons).
Sorry, I misread the destructor call, mistaking it for the base class! Duh. The only issue is whether to use an nsCOMPtr or not, and we agree that it wins to use one for conciseness reasons. /be
Attached patch Patch v1.1 (obsolete) — — Splinter Review
Now it's nsDoubleHashtableStringSupports :) Don't you just love long names? I think it is useless to check if (!mHashTable.ops) in Init(). Init() is protected; it can't be called twice. Not only that, but it makes the code messier-looking--you have to preset mHashTable.ops = nsnull in the constructor since it's a struct and doesn't initialize its memory to null. (If we want to make users of nsDoubleHashtable* call Init() from the getgo, then I'm OK with opening it to the public and doing the Init() thing, but right now it's explicit in the design that only the constructor calls Init()--and it's OK with me.) This patch has the if() in it, but if I can remove it I'd like to. Comments?
Attachment #69819 - Attachment is obsolete: true
We should make mKey in this code be some other string type than nsString, sizeof(nsString) == 16, where as sizeof(nsXPIDLString) == 8, so using nsXPIDLString saves us space in the size of the entry structs, which means we can store more data in the entries w/o causing warnings in the pldhash code about things not being as memory efficient as they could be. An other option for string classes is nsSharableString, which is also only 8 bytes large. I don't know if nsXPIDLString is smaller over all (i.e. including buffer handles and data) than nsSharableString, jag or dbaron would probably know.
Comment on attachment 70053 [details] [diff] [review] Patch v1.1 >+++ xpcom/ds/nsDoubleHashtables.cpp 18 Feb 2002 10:19:58 -0000 Is the plural really worth it? nsHashtable.cpp has hosted several impls for years, I say cut the trailing 's' (we shun it in directory names, too -- see mozilla/string, not mozilla/strings). >+// >+// HASH StringSupports >+// >+nsDoubleHashtableStringSupports::nsDoubleHashtableStringSupports() >+{ >+ // MUST init mHashTable.ops to nsnull so that we can detect that the >+ // hashtable has not been initialized. >+ mHashTable.ops = nsnull; >+ Init(); >+}; Ok, I buy your Init-is-protected-so-don't-protect-me-from-myself argument -- but then why have Init at all if it's called in one place only? One reason to make Init public is to let callers check for OOM. Otherwise don't you need to test !ops all over to make a constructed-with-OOM-failure instance safe? >+ >+nsDoubleHashtableStringSupports::~nsDoubleHashtableStringSupports() >+{ >+ if (!mHashTable.ops) { Oops, this needs to test non-null, not null (drop the !). >+ PL_DHashTableFinish(&mHashTable); >+ } >+} jst: alecf is shrinking nsString, IIRC to 12 bytes on most platforms. I'm concerned that nsXPIDLString still new's a separate 2-word buffer handle, making its use here a false economy. /be
Attachment #70053 - Flags: needs-work+
(nsString has already shrunk as small as it will get, which is 12 bytes + a 4 byte vtable pointer, 16 bytes total)
Attached patch Patch v1.2 — — Splinter Review
- rename nsDoubleHashtables.* to nsDoubleHashtable.* - add Mac build files (untested) - Make Init() public and require callers to call it (I'm convinced) - Fix oops pointed out by Brendan
Attachment #70053 - Attachment is obsolete: true
Comment on attachment 70187 [details] [diff] [review] Patch v1.2 Use JS_DHASH_MIN_SIZE instead of hardcoded 16. Consider nsStringSupportsDoubleHashtable, or even nsStringToSupportsDoubleHashtable, instead of the backward-looking nsDoubleHashtableStringSupports (but I know what you're trying to do by "sorting" the key-value anames to the end :-). sr=brendan@mozilla.org /be
Attachment #70187 - Flags: superreview+
Comment on attachment 70187 [details] [diff] [review] Patch v1.2 r=alecf - so glad to see this done.
Attachment #70187 - Flags: review+
Anyone here that can patch and compile to see if this builds on Mac?
checked in (last night)
Status: NEW → RESOLVED
Closed: 23 years ago
Resolution: --- → FIXED
Err, wait, I wanted to leave this open. There are at least two other classes I want to make: (1) string->(string,void*) class (2) void*->(string,isupports,void*) (3) macro-based X->X class (I think it can be done in such a way that (1) and (2) and the string->isupports class can be implemented in terms of it, so people who use it will get all the perf/footprint benefits that string->isupports offers) The main issue right now is deciding how to store the string in the value side of the string class. I would *like* it to return a non-owning pointer to the string for efficiency purposes (I hate string copies but until COW happens we are forced to use it). Maybe nsSharableString would work.
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Oops, returning an nsString* isn't going to work because hashtable entries can be shuffled around. So it's nsSharableString or COW or copy-on-get.
jkeiser: you could have an out nsAString& i.e. Get(sometype key, nsAString& result) then you could later improve the implementation by making the strings share if possible.. jag would have the best suggestion though..
templates are allowed in some cases; could we use them instead of macros? If you hate string copies, why not return the const PRUnichar* or const char*? Those point to memory not embedded within an entry, so they won't move. Right? I hope all those cases have real-world uses in the Mozilla tree -- I'm curious, can you cite lxr links? /be
Or you could return a nsDependent[C]String by value that would re-wrap the string buffer inside the string in the entrie. Then you don't need to worry about the entries moving around in memory.
Returning nsDependent[C]String by value is perfectly fine btw, since creating them is really cheap, no copying, or anything like that. Just thought I'd point that out in case it wasn't as obvious as I thought it was...
Hmm, but that does leave us with no way of flagging a lookup miss, hmm...
brendan: templates? mmm. This template proposal should address the issue. You could do nsDoubleHashtable<nsAString,nsAString,nsDHStringKey,nsString> and if you didn't need to copy the value (and were using it for a short time, you could do mHashtable->GetPtr() to get a pointer to the nsString itself). (If templates don't work, we can use macros.) ===== nsDoubleHashtable<K,V,KS,VS> ===== INTERFACE template<class K, class V, class KS, class VS> class nsDoubleHashtable { public: PRBool Get(K&, V*); PRBool GetPtr(K&, VS**); nsresult Put(K&, V&); nsresult Remove(K&); } K = the key type used in the interface methods (Get/Put). V = the value type used in the interface methods (Get/Put). KS = the key type that will be *stored* (usually a wrapper class) Must implement: - constructor KS(K) - operator==(K) - PLDHashNumber GetHashCode() VS = the value type that will be stored (often == V) Must implement: - constructor VS(V) - cast V(VS) - operator==(V) KS does *not* need to be virtual. In fact, in most cases I expect it to just be a class that wraps K, which means sizeof(KS) == sizeof(K). (So wrapping a class around a PRInt32 key would not hurt you.) V, K and VS can all be primitive types if desired. IMPLEMENTATION We would define the static callback functions for mHashtable in the nsDoubleHashtable (I think that is possible) and define the entry structure containing KS mKey and V mVal outside the nsDoubleHashtable: template <class KS,class VS> struct nsDoubleHashtableEntry { KS mKey; VS mVal; } Get(K&,V*): get the entry, copy into the return value - looks up the entry at K (using GetHashCode() and operator==() underneath) - If it exists, does *V = (V)entry->mVal; - return PR_TRUE|PR_FALSE depending on whether the entry was found GetPtr(K&,VS**): get the entry, copy a *pointer into the entry* into the return value - looks up the entry at K (using GetHashCode() and operator==() underneath) - If it exists, does *VS = &(entry->mVal); - return PR_TRUE|PR_FALSE depending on whether the entry was found - this is for the case that you have a structure with an expensive copy that you are not going to need for long (i.e. don't keep this around forever) Put(K&,V&): - creates an entry at K (if it's not there, it creates one and copies the key in using KS(K)) - entry->mVal = (VS)V; Remove(K&,V&): - removes the entry at K (this will call clear entry, which will use the destructor on KS and VS normally) If it is warranted, it would not be hard to add a VS so you could store a different type than you get. But I'm not yet sure if it's warranted. REASONS This would be usable nearly everywhere we do nsHashtable, not just for single X -> Y but also for X -> (struct containing Y, Z). It's easy to declare. there are only three things 99% of people will have to do to store things in the hashtable (and many will just have to do one): - declare your nsDoubleHashtable<> variable with the proper types - make a key wrapper that implements hashcode (most people use a few standard key types, void*, int and string among them, so they will be able to use key wrappers we provide and skip this step) - make a value struct (for people that want to store multiple things in the hash) It's easy to use. Get() and Put() are pretty damn simple and obvious. It's time-efficient. Only a function call and (generally) a 4-byte return value copy less efficient than using PLDHashtable directly. It's space-efficient. It takes exactly sizeof(KS)+sizeof(VS) per entry (and they are not required to be virtual); and it does not use *any* more memory for the hashtable itself than PLDHashTable. In addition, the only mallocs that happen here are within PLDHashTable itself. The only new we do is placement-new into the PLDHashTable (no malloc required). It works on primitives as well as classes. int -> int would not be hard to do. CONS This makes storing owned pointers less trivial than perhaps it should be; you could probably, however, make a VS wrapper that could handle the operations that need to be done.
Keywords: mozilla1.0+
Keywords: mozilla1.0+
Attached patch Templatized Hashtable Patch (obsolete) — — Splinter Review
Attached patch Templatized Hashtable Patch (obsolete) — — Splinter Review
Attached patch Templatized Hashtable Patch (obsolete) — — Splinter Review
Attached patch Templatized Hashtable Patch (obsolete) — — Splinter Review
This patch is totally working on Linux. To use, you do something like the following: #include "nsDoubleHashtable.h" nsDoubleHashtable<nsAString, nsDHStringKey, PRInt32, PRInt32> hash; hash.Init(); hash.Put(NS_LITERAL_STRING("a"), 10); PRInt32 val; if (hash.Get(NS_LITERAL_STRING("a"), &val) { printf("a=%d\n", val); } nsDoubleHashtable.h defines key types for nsAString (and char*), nsACString (and PRUnichar*), PRInt32, void* and nsISupports*. It defines a special owning reference class for nsISupports* values; any class that can be safely copied can just be used directly (as you see above with PRInt32).
Heh, sorry, that large form sub problem reared its head I think. There is one problem with this patch: namely, PLDHashTable makes the underlying assumption that the key type stored in the entry is the same as the key type being used to query for the entry. Because of this assumption, this patch converts the query type to the key type before lookup, add or remove. In the case of string, this does an unnecessary string copy. The reason PLDHashTable makes this assumption is the GetKey() function and the use of the returned value. GetKey() must return a pointer to a key, and *that is the pointer that will be passed to MatchEntry*. We could convert the key to the query type in GetKey(), but that would cause a leak. If we assume in GetKey that the type is the *storage* key type, then when we do a lookup we have to first convert the query key type to the storage key type. The solution I'm leaning towards now is to actually make the assumption that the query type is the same as the storage type, and let the user provide an external class that calculates the hash code and does the copy and all that other stuff. This only needs to be done for the key; the value can still be stored as a different type than what is passed to Put() and returned in Get(). It might be prudent to make them the same, though. Total things that still need doing: - fix the extra key copy problem - get this working on Windows and Mac - add an Exists() or Contains() method - find proper hash algorithm for PRInt32 and void* - documentation Things that should happen later: - add enumeration capability - make an EmptyDoubleHash class that just stores keys and no values. This could be done with nsDoubleHashtable but I am skeptical of compilers' ability to work with empty classes.
Attachment #76384 - Attachment is obsolete: true
Attachment #76385 - Attachment is obsolete: true
Attachment #76386 - Attachment is obsolete: true
Attached patch Templatized Hashtable v1.1 (obsolete) — — Splinter Review
Added Exists() method.
Attachment #76387 - Attachment is obsolete: true
+ PLDHashNumber GetHashCode() const { return (PRInt32)(nsISupports*)mKey; } is not 64-bit clean -- use NS_PTR_TO_INT32. Also, all known platforms align aggregates on at least a 0 mod 4 boundary, so you could >> 2, and I would cast the left operand of >> to PLDHashNumber first, so you use unsigned right shift. /be
Status: REOPENED → ASSIGNED
Blocks: 95622
Attached patch Macro-based hashtable (obsolete) — — Splinter Review
Unfortunately, on Windows getting the address of a templatized function does not appear to work (unrecognized syntax). So I decided to write a macro-based patch. Then, a conversation between shaver and bz taught me that there are a few really cool things PLDHashTable can do that the templatized design could not (specifically, you can have the entry be a pointer to an object which already contains the key and value, a somewhat common situation). So I decided to make this patch a little bit closer to PLDHashTable itself to allow those things. This patch hinges on the entry struct as PLDHashTable does, but gives you a simple PLDHashTable wrapper class and abstracts away the callbacks. Pros: - hides callbacks entirely - automatic construction / destruction of hashtable; simple declaration - uses PLDHashTable's entry struct model better than nsDoubleHashtable* Cons: - not as simple as nsDoubleHashtable* in the case of a simple mapping of X -> Y, a somewhat common case. This could be built pretty easily, however. See the HASH_BAG macros for such an example (turns the hashtable into a list, essentially, but with hashtable's performance characteristics). (And yes, though we are not using the hash bag macros right now, I know of specific cases where we can use all three of them.)
Attachment #76530 - Attachment is obsolete: true
There are lots of docs in nsDoubleHashtable.h itself, but as a kind of summary, here is the example usage (which I have not compiled): #include "nsDoubleHashtable.h" // Create the entry class that will contain the keys and values // (this one extends a standard key class defined in nsDoubleHashtable.h // to deal with the key hashing, matching and storing). class DictionaryEntry : public PLDHashStringEntry { DictionaryEntry(const void* aKey) : PLDHashStringEntry(const void* aKey) { } ~DictionaryEntry() { } nsString mPronunciation; nsString mDefinition; } // Create the hash wrapper class "Dictionary" DECL_DHASH_WRAPPER(Dictionary, DictionaryEntry, const nsAString&) DEFINE_DHASH_WRAPPER(Dictionary, DictionaryEntry, const nsAString&) int main(void) { // Declare and initialize the hashtable Dictionary d; nsresult rv = d.Init(); if (NS_FAILED(rv)) return 1; // Put an entry DictionaryEntry* a = d.AddEntry(NS_LITERAL_STRING("doomed")); a->mDefinition = NS_LITERAL_STRING("The state you get in when a Mozilla release is pending"); a->mPronunciation = NS_LITERAL_STRING("doom-d"); // Get the entry DictionaryEntry* b = d.GetEntry(NS_LITERAL_STRING("doomed") printf("doomed: %s\n", NS_ConvertUCS2toUTF8(b->mDefinition).get()); // Entries will be automagically cleaned up when the Dictionary object goes away return 0; }
Blocks: 121321
Comment on attachment 83931 [details] [diff] [review] Macro-based hashtable looks good 'cept your comments under "BONUS POINTS" refer to |nsAString& GetDefinition..| while the implementation returns an |nsAString*| - though I also have to add that the |new nsString| seems like overkill to me, and encourages people to be new-happy. some use of nsDependentString would do you fine here, with |const nsAString&| maybe? anyway, its just a comment but it would be nice if it were clearer :) sr=alecf with the comment cleanup
Attachment #83931 - Flags: superreview+
Whiteboard: [FIX]
/* * This file provides two major things to make PLDHashTable easier to use: * - hash class macros for you to define a hashtable * - default key classes to use as superclasses for your entries * - empty maps for string, int and void + * XXXTJW: it would be convenient (and little work) to add CString support */ [snip] * EXAMPLE * * As an example, let's say you wanted to create a dictionary, which would be * a mapping from a string (the word) to the pronunciation and definition of * those words. Let's further say you just had a + * XXXTJW: looks like you stopped short or cut off a line here * [snip] * + * XXXTJW: does this include the destructor? (probably does; just my curiosity) * // Do NOT ADD VIRTUAL METHODS INTO YOUR ENTRY. Everything will break. * class DictionaryEntry : public PLDHashStringEntry { + * + * XXXTJW: I think you meant |: PLDHashStringEntry(aKey)| * DictionaryEntry(const void* aKey) : PLDHashStringEntry(const void* aKey) { } * ~DictionaryEntry() { } [snip] * * // Put an entry * DictionaryEntry* a = d.AddEntry(NS_LITERAL_STRING("doomed")); + * + * XXXTJW: worth mentioning the need to null-check here? Add can return null. * a->mDefinition = NS_LITERAL_STRING("The state you get in when a Mozilla release is pending"); * a->mPronunciation = NS_LITERAL_STRING("doom-d"); * * // Get the entry * DictionaryEntry* b = d.GetEntry(NS_LITERAL_STRING("doomed") + * XXXTJW: Get can also return null if the entry is not in the table + * * printf("doomed: %s\n", NS_ConvertUCS2toUTF8(b->mDefinition).get()); [snip] * nsAString* GetDefinition(nsAString& aWord) { * DictionaryEntry* e = GetEntry(aWord); * if (e) { + * XXXTJW: You might want to mention why this is a bad idea in general, + * XXXTJW: and what must be done when this is done (cleanup) + * XXXTJW: perhaps further, that COW sharable strings will be useful here + * XXXTJW: once they're completely implemented * return new nsString(e->mDefinition); * } else { * return nsnull; * } * } + * XXXTJW: any reason these params aren't const? just wondering * nsresult PutDefinition(nsAString& aWord, nsAString& aDefinition, nsAString& aPronunciation) { * DictionaryEntry* e = AddEntry(aWord); [snip] /* * ENTRY CLASS DEFINITION * * The simplifications of PLDHashTable all hinge upon the idea of an entry * class, which is a class you define, where you store the key and values that + * XXXTJW: "small hash like ><." missing something? * you will place in each hash entry. For a small hash like . You must also [snip] * PRBool MatchEntry(const void* aKey) - return true or false depending on + * XXXTJW: eww. wrap at 80 cols when possible =) * whether the * key pointed to by aKey matches this entry * static PLDHashNumber HashKey(const void* aKey) - hash key * + * XXXTJW: you apparently cut off some information here, too * For example, a hashtable that contained entries that mapped int to String could b * See the default key entry classes for examples. * * NOTES: * - Do NOT ADD VIRTUAL METHODS INTO YOUR ENTRY. Everything will break. + * XXXTJW: it would be useful to mention why (or point at pldhash's impl) */ /* * PRIVATE HASHTABLE MACROS * + * XXXTJW: wrap to 80 cols please * These internal macros can be used to declare the callbacks for an entry class, * but the wrapper class macros call these for you so don't call them. */ [snip] // Initialize hashtable to a certain class. [...] +//XXXTJW: Hardcoded size of 16? why? It would be better to be configurable here // #define DHASH_INIT(HASHTABLE,ENTRY_CLASS,RV) \ [...] PRBool isLive = PL_DHashTableInit(&(HASHTABLE), \ &hash_table_ops, nsnull, \ sizeof(ENTRY_CLASS), 16); \ [snip] * CLASSNAME: the name of the class to declare. * ENTRY_CLASS: the class of the entry struct. * KEY_TYPE: the name of the key type for GetEntry and AddEntry. * * * DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE) [...] +//XXXTJW: I'd prefer it if we'd add |const| to key signatures here instead of +//XXXTJW: expecting that of the user. Partially, this is because I'd like to +//XXXTJW: use |##| and |new| on KEY_TYPE in certain places +//XXXTJW: perhaps there's a better way for me to accomplish that, however #define DECL_DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE) \ class CLASSNAME { \ public: \ CLASSNAME(); \ virtual ~CLASSNAME(); \ nsresult Init(); \ //XXXTJW: (new comment) possibly make get-methods const (const-casting the //XXXTJW: hashtable to operate) ENTRY_CLASS* GetEntry(KEY_TYPE aKey); \ [snip] /* * STANDARD KEY ENTRY CLASSES [...] * PLDHashStringEntry: nsAString + * XXXTJW: nsACString version would be killer * PLDHashInt32Entry: PRInt32 * PLDHashVoidEntry: void* */ // String-key entry [...] const void* GetKey() const { + //XXXTJW: why the cast when it's implicitly casting to void* anyway? return NS_STATIC_CAST(const nsAString*, &mKey); } [...] + //XXXTJW: make this const, since it had better not mutate after creation nsString mKey; }; [snip] + //XXXTJW: might as well make this const, too PRInt32 mKey; }; +//XXXTJW: add protection from platforms where pointers are not 0 mod 4 +//XXXTJW: (#ifdef or similar) //XXXTJW: (new comment) I see why this is irrelevant now // // Void-key entry // +//XXXTJW: use NS_STATIC_CAST in preference to C-style casting in new code +//XXXTJW: I've never seen *(type **)single_ptr_to_type notation before, +//XXXTJW: so I don't know what it's trying to do or whether this is correct class PLDHashVoidEntry : public PLDHashEntryHdr { public: PLDHashVoidEntry(const void* aKey) : mKey(*(const void**)aKey) { } ~PLDHashVoidEntry() { } [snip] * HASH BAGS [...] +//XXXTJW: again, I'm of the opinion that |const| key-type signatures should be +//XXXTJW: put here, since none of these methods (should) change the key +//XXXTJW: I'd also rename |Exists| to |Contains| while we're here #define DECL_HASH_BAG(CLASSNAME,ENTRY_CLASS,KEY_TYPE) \ [...] nsresult Put(KEY_TYPE aKey) { \ return AddEntry(aKey) ? NS_OK : NS_ERROR_OUT_OF_MEMORY; \ } \ PRBool Exists(KEY_TYPE aKey) { \ return GetEntry(aKey) ? PR_TRUE : PR_FALSE; \ } \ };
+ * XXXTJW: it would be convenient (and little work) to add CString support Sure. * a mapping from a string (the word) to the pronunciation and definition of * those words. Let's further say you just had a + * XXXTJW: looks like you stopped short or cut off a line here Typical :) I bounce around a lot when I write things, sometimes I don't finish all the paragraphs I started. Will fix. + * XXXTJW: does this include the destructor? (probably does; just my curiosity) * // Do NOT ADD VIRTUAL METHODS INTO YOUR ENTRY. Everything will break. Yep. Any virtual method will add a 4-byte pointer at the beginning of your entry class, and you don't want that. It screws up pointers and stuff. * class DictionaryEntry : public PLDHashStringEntry { + * + * XXXTJW: I think you meant |: PLDHashStringEntry(aKey)| * DictionaryEntry(const void* aKey) : PLDHashStringEntry(const void* aKey) { } Damn straight. * // Put an entry * DictionaryEntry* a = d.AddEntry(NS_LITERAL_STRING("doomed")); + * + * XXXTJW: worth mentioning the need to null-check here? Add can return null. Sure. * a->mDefinition = NS_LITERAL_STRING("The state you get in when a Mozilla release is pending"); * a->mPronunciation = NS_LITERAL_STRING("doom-d"); * * // Get the entry * DictionaryEntry* b = d.GetEntry(NS_LITERAL_STRING("doomed") + * XXXTJW: Get can also return null if the entry is not in the table + * Yes, but in this case the entry already exists because we added it. + * XXXTJW: You might want to mention why this is a bad idea in general, + * XXXTJW: and what must be done when this is done (cleanup) + * XXXTJW: perhaps further, that COW sharable strings will be useful here + * XXXTJW: once they're completely implemented Sounds good. + * XXXTJW: any reason these params aren't const? just wondering * nsresult PutDefinition(nsAString& aWord, nsAString& aDefinition, nsAString& aPronunciation) { No reason, probably because it was just an example :) I'll fix anyway, no reason not to. + * XXXTJW: "small hash like ><." missing something? * you will place in each hash entry. For a small hash like . You must also * define five methods: Yet again, bad habits bite me in the ass. + * XXXTJW: eww. wrap at 80 cols when possible =) :P usually I do, strange that I missed that. + * XXXTJW: you apparently cut off some information here, too * For example, a hashtable that contained entries that mapped int to String could b Yawohl. * NOTES: * - Do NOT ADD VIRTUAL METHODS INTO YOUR ENTRY. Everything will break. + * XXXTJW: it would be useful to mention why (or point at pldhash's impl) Good idea. +//XXXTJW: Hardcoded size of 16? why? It would be better to be configurable here Good idea. Added static member NumInitialEntries() +//XXXTJW: I'd prefer it if we'd add |const| to key signatures here instead of +//XXXTJW: expecting that of the user. Partially, this is because I'd like to +//XXXTJW: use |##| and |new| on KEY_TYPE in certain places +//XXXTJW: perhaps there's a better way for me to accomplish that, however Another good idea, done. + //XXXTJW: why the cast when it's implicitly casting to void* anyway? To ensure it gets the right pointer. In C++, pointers actually point to a particular portion of the data structure rather than the beginning of the entire object. When you do A* a; B* b = (B*)a; and you print the values of (void*)b and (void*)a, they could be different. In fact, when you hit multiple inheritance a lot of the time they will. This is a safety measure. + //XXXTJW: make this const, since it had better not mutate after creation Sure. +//XXXTJW: add protection from platforms where pointers are not 0 mod 4 +//XXXTJW: (#ifdef or similar) How will the class break for such platforms? It seems like it will work to me. +//XXXTJW: use NS_STATIC_CAST in preference to C-style casting in new code +//XXXTJW: I've never seen *(type **)single_ptr_to_type notation before, +//XXXTJW: so I don't know what it's trying to do or whether this is correct It won't make much more sense in NS_STATIC_CAST :) *(void**)x means that x is natively a void** and we want to find out what the void* is. If key is type T, we pass around T*. In this case T is void*, so we pass around void** underneath and have to cast void* to void** before using it. I'll change to NS_STATIC_CAST, though, this is good idea. +//XXXTJW: again, I'm of the opinion that |const| key-type signatures should be +//XXXTJW: put here, since none of these methods (should) change the key +//XXXTJW: I'd also rename |Exists| to |Contains| while we're here Done.
New patch rolling up all comments so far? /be
As soon as I determine what is up with my tree, yeah. Something is funky with dependencies; I kicked off a clobber build a little while back. I intend to carry alecf's sr to this patch since it includes his comments and most of the changes suggested by Tim are in comments.
Attached patch Macro-based hashtable v1.0.1 (obsolete) — — Splinter Review
Contains: - comment fixes - new NumInitialEntries() method to tell it how many entries to init hashtable with - NS_COM designation on all classes so that they can be exported from dll Tested on Linux and Windows. r= welcome, testing on Mac soon.
Attachment #83931 - Attachment is obsolete: true
Comment on attachment 91615 [details] [diff] [review] Macro-based hashtable v1.0.1 Carrying sr=alecf since we haven't changed *that* much (and his issues are fixed)
Attachment #91615 - Flags: superreview+
It might be more convenient for users if the number of entries to presize the table to was taken in ::Init().
+ * if (myBag.Exists(5)) { Comment needs to track switch from Exists to Contains... /me whines about lack of right-justified to column 79 backslashes continuing non-terminal multiline macro lines. /be
Also, a bag is a multi-set, but it seems to me your BAG macros implement a set. What am I missing? /be
Attached patch Macro-based hashtable v1.0.2 (obsolete) — — Splinter Review
- fixed comment nits from brendan and Tim - removed NumInitialEntries() and made it a parameter to Init() instead (which is *such* a better idea, thanks Tim) - changed bag to set (you are right, Brendan :) ) This should cover everyone's comments.
Attachment #91615 - Attachment is obsolete: true
Attached patch Macro-based hashtable v1.0.3 (obsolete) — — Splinter Review
Same patch but with \'s at column 79 :)
Attachment #92464 - Attachment is obsolete: true
Comment on attachment 92468 [details] [diff] [review] Macro-based hashtable v1.0.3 Carrying sr=alecf, still very little has changed.
Attachment #92468 - Flags: superreview+
Comment on attachment 92468 [details] [diff] [review] Macro-based hashtable v1.0.3 >+ * // Do NOT ADD VIRTUAL METHODS INTO YOUR ENTRY. Everything will break. >+ * // This is because of the 4-byte pointer C++ magically prepends onto your >+ * // entry class. It interacts very unhappily with PLDHashTable. >+ * class DictionaryEntry : public PLDHashStringEntry { >+ * DictionaryEntry(const void* aKey) : PLDHashStringEntry(aKey) { } >+ * ~DictionaryEntry() { } >+ * nsString mPronunciation; >+ * nsString mDefinition; >+ * } Should this be a struct, not a class? Just wondering what the default access is without a public: label. >+ * >+ * (2) Create the hash class >+ * >+ * The final hash class you will use in step 3 is defined by a macros. Faulty plural -- "two macros" or "a macro". >+ * >+ * DECL_DHASH_WRAPPER(Dictionary, DictionaryEntry, const nsAString&) >+ * DEFINE_DHASH_WRAPPER(Dictionary, DictionaryEntry, const nsAString&) Uber-nit: DECL clashes with the spelled-out DEFINE -- why not DECLARE? >+ * >+ * (3) Use the hash class >+ * >+ * Here is a simple main() that might look up a string: >+ * >+ * int main(void) { >+ * Dictionary d; >+ * nsresult rv = d.Init(10); >+ * if (NS_FAILED(rv)) return 1; >+ * >+ * // Put an entry >+ * DictionaryEntry* a = d.AddEntry(NS_LITERAL_STRING("doomed")); >+ * if (!a) return 1; >+ * a->mDefinition = NS_LITERAL_STRING("The state you get in when a Mozilla release is pending"); >+ * a->mPronunciation = NS_LITERAL_STRING("doom-d"); >+ * >+ * // Get the entry >+ * DictionaryEntry* b = d.GetEntry(NS_LITERAL_STRING("doomed")); >+ * printf("doomed: %s\n", NS_ConvertUCS2toUTF8(b->mDefinition).get()); >+ * >+ * // Entries will be automagically cleaned up when the Dictionary object goes away >+ * return 0; >+ * } >+ * >+ * >+ * BONUS POINTS >+ * >+ * You may wish to extend this class and add helper functions like >+ * nsDependentString* GetDefinition(nsAString& aWord). For example: >+ * >+ * class MyDictionary : public Dictionary { >+ * MyDictionary() { } >+ * // Make SURE you have a virtual destructor >+ * virtual ~myDictionary() { } >+ * nsDependentString* GetDefinition(const nsAString& aWord) { >+ * DictionaryEntry* e = GetEntry(aWord); >+ * if (e) { >+ * // We're returning an nsDependentString here, callers need to delete it >+ * // and it doesn't last long, but at least it doesn't create a copy >+ * return new nsDependentString(e->mDefinition.get()); >+ * } else { >+ * return nsnull; >+ * } >+ * } >+ * nsresult PutDefinition(const nsAString& aWord, >+ * const nsAString& aDefinition, >+ * const nsAString& aPronunciation) { >+ * DictionaryEntry* e = AddEntry(aWord); >+ * if (!e) { >+ * return NS_ERROR_OUT_OF_MEMORY; >+ * } >+ * e->mDefinition = aDefinition; >+ * e->mPronunciation = aPronunciation; >+ * return NS_OK; >+ * } >+ * } Need public: here, for sure. >+#define DECL_DHASH_CALLBACKS(ENTRY_CLASS) \ >+PR_EXTERN(const void *) \ >+ENTRY_CLASS##GetKey(PLDHashTable* table, PLDHashEntryHdr* entry); \ >+PR_EXTERN(PLDHashNumber) \ >+ENTRY_CLASS##HashKey(PLDHashTable* table, const void* key); \ >+PR_EXTERN(PRBool) \ >+ENTRY_CLASS##MatchEntry(PLDHashTable *table, const PLDHashEntryHdr *entry, \ >+ const void *key); \ >+PR_EXTERN(void) \ >+ENTRY_CLASS##ClearEntry(PLDHashTable *table, PLDHashEntryHdr *entry); \ >+PR_EXTERN(void) \ >+ENTRY_CLASS##InitEntry(PLDHashTable *table, PLDHashEntryHdr *entry, \ >+ const void *key); Indentation off for by two for the continuation of InitEntry's parameter list. >+#define DHASH_CALLBACKS(ENTRY_CLASS) \ >+PR_CALLBACK const void * \ >+ENTRY_CLASS##GetKey(PLDHashTable* table, PLDHashEntryHdr* entry) \ Shouldn't these be PR_STATIC_CALLBACKs? >+#define DHASH_INIT(HASHTABLE,ENTRY_CLASS,NUM_INITIAL_ENTRIES,RV) \ >+{ \ >+ static PLDHashTableOps hash_table_ops = \ >+ { \ >+ PL_DHashAllocTable, \ >+ PL_DHashFreeTable, \ >+ ENTRY_CLASS##GetKey, \ >+ ENTRY_CLASS##HashKey, \ >+ ENTRY_CLASS##MatchEntry, \ >+ PL_DHashMoveEntryStub, \ >+ ENTRY_CLASS##ClearEntry, \ >+ PL_DHashFinalizeStub, \ >+ ENTRY_CLASS##InitEntry \ >+ }; \ >+ PRBool isLive = PL_DHashTableInit(&(HASHTABLE), \ >+ &hash_table_ops, nsnull, \ >+ sizeof(ENTRY_CLASS), \ >+ sizeof(ENTRY_CLASS) * \ >+ (NUM_INITIAL_ENTRIES)); \ The last argument is wrong, you want just NUM_INITIAL_ENTRIES. PL_DHashTableInit will scale by the next-to-last argument for you. >+ * DECL_DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE) >+ * >+ * Declare the hash class but do not define the functions. >+ * >+ * CLASSNAME: the name of the class to declare. >+ * ENTRY_CLASS: the class of the entry struct. >+ * KEY_TYPE: the name of the key type for GetEntry and AddEntry. >+ * >+ * >+ * DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE) No DEFINE_ prefix here -- ok by me, maybe you should be consistent earlier with DECL_ vs. no prefix? Else DECLARE_ and DEFINE_ to make everything crystal-clear. >+ * >+ * Define the functions for the hash class. >+ * >+ * CLASSNAME: the name of the class to declare. >+ * ENTRY_CLASS: the class of the entry struct. >+ * KEY_TYPE: the name of the key type for GetEntry and AddEntry. >+ * >+ * >+ * CAVEATS: >+ * - You may only have *one* wrapper class per entry class. English nit: "have only *one*", not "only have *one*". >+nsresult CLASSNAME::Init(PRUint32 aNumInitialEntries) { \ >+ if (!mHashTable.ops) { \ >+ nsresult rv; \ >+ DHASH_INIT(mHashTable,ENTRY_CLASS,aNumInitialEntries,rv) \ >+ return rv; \ >+ } else { \ else after return non-sequitur alert. >+#define DECL_HASH_SET(CLASSNAME,ENTRY_CLASS,KEY_TYPE) \ HASH_ vs DHASH_ -- is the double-hashing an uninteresting implementation detail (yes, but so is hashing, by the same argument taken further)? Is it better to be consistent and avoid a HASH_* name collision down the road? Food for thought, up to you to do something here, or nothing :-). >@@ -387,7 +403,7 @@ > } > NS_ADDREF(mControls); > >- rv = mSelectedRadioButtons.Init(); >+ rv = mSelectedRadioButtons.Init(1); Another "just a thought": default PL_DHASH_MIN_SIZE or 1 parameter for Init, so you don't need to pass 1 in lieu of something better? Fix the nits you agree are worth fixing, and r=brendan@mozilla.org -- thanks again for doing this. /be
Attachment #92468 - Flags: review+
> Should this be a struct, not a class? Just wondering what the default access > is without a public: label. Could safely be a struct, but given that we're trying to convey the OOP-ness of this, class with public label is better. Good catch. > Uber-nit: DECL clashes with the spelled-out DEFINE -- why not DECLARE? Turns out there is no DEFINE_ macro--it's omitted entirely. Doc error :) > Shouldn't these be PR_STATIC_CALLBACKs? If it's static, it's only usable from within one library / object file. These need to be usable from other places. > Another "just a thought": default PL_DHASH_MIN_SIZE or 1 parameter for Init, so you don't need to pass 1 in lieu of something better? Hmm, I think it's best to make them think about it. Even though the minimum size is 16 entries (!) it could (and hopefully will) change to be lower.
Attached patch Macro-based hashtable v1.0.4 (obsolete) — — Splinter Review
Address brendan's issues
Attachment #92468 - Attachment is obsolete: true
Comment on attachment 92514 [details] [diff] [review] Macro-based hashtable v1.0.4 Carrying r=brendan, sr=alecf, thank God!
Attachment #92514 - Flags: superreview+
Attachment #92514 - Flags: review+
Attached patch Macro-based hashtable v1.0.4 (obsolete) — — Splinter Review
Urk, uploaded patch for another bug. This is the right patch.
Attachment #92514 - Attachment is obsolete: true
> > Shouldn't these be PR_STATIC_CALLBACKs? > > If it's static, it's only usable from within one library / object file. > These need to be usable from other places. PR_STATIC_CALLBACK does the right thing -- on systems such as Windows where the function can't be static, the macro will not include the static keyword. But on systems where static is fine, using PR_STATIC_CALLBACK helps reduce the global linker namespace, which is a good thing. > > Another "just a thought": default PL_DHASH_MIN_SIZE or 1 parameter for > > Init, so you don't need to pass 1 in lieu of something better? > > Hmm, I think it's best to make them think about it. Even though the minimum > size is 16 entries (!) it could (and hopefully will) change to be lower. The build system can override PL_DHASH_MIN_SIZE, but why do you think 16 is too large? Both plhash.c and pldhash.c (aka js/src/jsdhash.c) use 16. Given the default maximum load factor, 4 or 8 seem too small (3 and 6 maximum population before growth, respectively). It seems best to avoid hashing and use linear search if you know the population will always or usually be that small. /be
> PR_STATIC_CALLBACK does the right thing -- on systems such as Windows where the > function can't be static, the macro will not include the static keyword. But on > systems where static is fine, using PR_STATIC_CALLBACK helps reduce the global > linker namespace, which is a good thing. Strangely, though, on Windows it can't be used in another lib. Changing it to PR_CALLBACK makes it work. It appears to be because of the static keyword. I think this is the line I'm after: http://lxr.mozilla.org/seamonkey/source/nsprpub/pr/include/prtypes.h#133 ... and it has static. But that's only if WINDLL is on. Perhaps it's not? > The build system can override PL_DHASH_MIN_SIZE, but why do you think 16 is too > large? Both plhash.c and pldhash.c (aka js/src/jsdhash.c) use 16. Given the > default maximum load factor, 4 or 8 seem too small (3 and 6 maximum population > before growth, respectively). It seems best to avoid hashing and use linear > search if you know the population will always or usually be that small. Point taken. I think I can see 8 being acceptable, but 4 would in fact be too small. Especially if this is arbitrary, why limit it?
Er ... http://lxr.mozilla.org/seamonkey/source/nsprpub/pr/include/prtypes.h#99 is the one That's WIN32, and it has static. And it doesn't work AFAICT.
I don't know why PR_STATIC_CALLBACK works differently from how I remember it from days of old. Cc'ing wtc. If it's busted, we should have an NSPR bug on file about that. We have to place a lower bound on table capacity, in order to keep one entry free (to terminate double-hashing, see the comment about relative primality around line 258 in xpcom/ds/pldhash.c). Given the default max-alpha, that means 4 is the smallest lower bound. When I wrote plhash.c (prhash.c in NSPR1, actually) and then jsdhash.c (the original file), it seemed to me that shrinking too often to a size so small that linear search would be better was not a good idea. But I could have been wrong. There is plenty of instrumentation in pldhash.c. If you turn it on (see the DEBUG_brendan stuff, try it if you like) and find too many underutilized small tables, please file a bug asking for the default JS/PL_DHASH_MIN_SIZE to be reduced. Thanks, /be
Brendan, I didn't know how PR_STATIC_CALLBACK should work until I read your comments in this bug. In mozilla/nsprpub/lib/ds/plhash.c, there are callbacks declared with static. For example, static void * PR_CALLBACK DefaultAllocTable(void *pool, PRSize size) { #if defined(XP_MAC) #pragma unused (pool) #endif return PR_MALLOC(size); } PR_STATIC_CALLBACK would also work there. So I don't know why PR_STATIC_CALLBACK doesn't work for you.
If you'll note, DefaultAllocTable in plhash.c is not exported or directly referred to in other dlls. That is why it works as static and the key functions of which I speak do not. However, I've figured out that we don't really need to export these callbacks in any case. Patch upcoming.
Attached patch Macro-based hashtable v1.0.5 (obsolete) — — Splinter Review
This patch addresses Brendan's static concerns and clears up the class namespace as well by not exporting classes unless they are defined in nsDoubleHashtable.h.
Attachment #92517 - Attachment is obsolete: true
Comment on attachment 93114 [details] [diff] [review] Macro-based hashtable v1.0.5 Since we don't have to declare those functions, I got rid of DECL_DHASH_CALLBACKS altogether, hallelujah! Bringing over r=brendan/sr=alecf, this patch just addresses their concerns.
Attachment #93114 - Flags: superreview+
Attachment #93114 - Flags: review+
Comment on attachment 93114 [details] [diff] [review] Macro-based hashtable v1.0.5 One more thing: DHASH_INIT should use PR_BEGIN_MACRO and PR_END_MACRO, I think. /be
Attached patch Macro-based hashtable v1.0.6 (obsolete) — — Splinter Review
Your wish is my command :) I'm pretty puzzled about that macro though. Why doesn't it just do #define PR_BEGIN_MACRO { #define PR_END_MACRO } The do { ... } while(0); thing seems silly to me.
Attachment #93114 - Attachment is obsolete: true
BTW, there will be a followon patch *in a different bug* where we add some of Tim's cool ideas (enumerations and the like) and make it trivial to do X -> Y mappings (perhaps he will do this himself :)
jkeiser: consider what would happen if PR_BEGIN_MACRO wer { and PR_END_MACRO were } in this case, for a macro named BIG_MAC(): if (fries) BIG_MAC(); else dessert(); /be
Comment on attachment 93174 [details] [diff] [review] Macro-based hashtable v1.0.6 So remove that trailing semicolon after the PR_END_MACRO, eh? /be
It seems like your example would work just fine. It would come out to: if (fries) { bigmac() } else dessert() It doesn't compile in Windows without the trailing semicolon. while requires a semicolon I suppose.
jkeiser: read my example again -- note the usual terminating semicolon in the "then" statement: BIG_MAC(); (verbatim). Note that {...}; in the expansion makes two statements, which makes a syntax error. You need to put the semicolon after each macro *call*, not in the *definition*, or you are perpetrating a non-syntactic macro. /be
Posting the semicolon change because I'm anal that way. I should have a Mac build by morning; I will then compile this patch in and make sure it works. brendan, I am still puzzled by why PR_BEGIN_MACRO / PR_END_MACRO do "do { ... } while(0)" instead of "{ ... }" ... if that is what you were responding to, I still haven't seen the logic. I can't think of a situation where it wouldn't work and be syntactic.
Attachment #93174 - Attachment is obsolete: true
the do/while allows a semicolon at the end... consider #define MY_MACRO(_foo) { baz = _foo; _foo = bar; } now if (test) MY_MACRO(foo); else do_something_else(); compiles to: if (test) { baz = foo; foo = bar; }; else do_something_else(); in this case you'll get a syntax error (else without if) In another case: if (test1) if (test2) MY_MACRO(foo); else do_something_else(); the "else" will get tacked onto test1, rather than test2, because the semicolon will end the whole statement - clearly not the author's intent. At least I think I've got that right :) I think there are other odd examples like this.
doh! Got it, it allows the semicolon to be added in the first place. Thanks.
Blocks: 161220
Fix checked in, my God, fix checked IN.
Status: ASSIGNED → RESOLVED
Closed: 23 years ago → 23 years ago
Resolution: --- → FIXED
Oh, I filed bug 161220 to handle a few improvements to the hashtable wrapper. Enumeration in particular is going to be a necessity.
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: