Back to index

lightning-sunbird  0.9+nobinonly
morkMap.h
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-  */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is mozilla.org code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1999
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *
00024  * Alternatively, the contents of this file may be used under the terms of
00025  * either of the GNU General Public License Version 2 or later (the "GPL"),
00026  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00027  * in which case the provisions of the GPL or the LGPL are applicable instead
00028  * of those above. If you wish to allow use of your version of this file only
00029  * under the terms of either the GPL or the LGPL, and not to allow others to
00030  * use your version of this file under the terms of the MPL, indicate your
00031  * decision by deleting the provisions above and replace them with the notice
00032  * and other provisions required by the GPL or the LGPL. If you do not delete
00033  * the provisions above, a recipient may use your version of this file under
00034  * the terms of any one of the MPL, the GPL or the LGPL.
00035  *
00036  * ***** END LICENSE BLOCK ***** */
00037 
00038 #ifndef _MORKMAP_
00039 #define _MORKMAP_ 1
00040 
00041 #ifndef _MORK_
00042 #include "mork.h"
00043 #endif
00044 
00045 #ifndef _MORKNODE_
00046 #include "morkNode.h"
00047 #endif
00048 
00049 //3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789
00050 
00051 /* (These hash methods closely resemble those in public domain IronDoc.) */
00052 
00053 /*| Equal: equal for hash table. Note equal(a,b) implies hash(a)==hash(b).
00054 |*/
00055 typedef mork_bool (* morkMap_mEqual)
00056 (const morkMap* self, morkEnv* ev, const void* inKeyA, const void* inKeyB);
00057 
00058 /*| Hash: hash for hash table. Note equal(a,b) implies hash(a)==hash(b).
00059 |*/
00060 typedef mork_u4 (* morkMap_mHash)
00061 (const morkMap* self, morkEnv* ev, const void* inKey);
00062 
00063 /*| IsNil: whether a key slot contains a "null" value denoting "no such key".
00064 |*/
00065 typedef mork_bool (* morkMap_mIsNil)
00066 (const morkMap* self, morkEnv* ev, const void* inKey);
00067 
00068 /*| Note: notify regarding a refcounting change for a key or a value.
00069 |*/
00070 //typedef void (* morkMap_mNote)
00071 //(morkMap* self, morkEnv* ev, void* inKeyOrVal);
00072 
00073 /*| morkMapForm: slots need to initialize a new dict.  (This is very similar
00074 **| to the config object for public domain IronDoc hash tables.)
00075 |*/
00076 class morkMapForm { // a struct of callback method pointers for morkMap
00077 public:
00078   
00079   // const void*     mMapForm_NilKey;  // externally defined 'nil' bit pattern
00080 
00081   // void*           mMapForm_NilBuf[ 8 ]; // potential place to put NilKey
00082   // If keys are no larger than 8*sizeof(void*), NilKey can be put in NilBuf.
00083   // Note this should be true for all Mork subclasses, and we plan usage so.
00084   
00085   // These three methods must always be provided, so zero will cause errors:
00086   
00087   // morkMap_mEqual  mMapForm_Equal;   // for comparing two keys for identity
00088   // morkMap_mHash   mMapForm_Hash;    // deterministic key to hash method
00089   // morkMap_mIsNil  mMapForm_IsNil;   // to query whether a key equals 'nil'
00090   
00091   // If any of these method slots are nonzero, then morkMap will call the
00092   // appropriate one to notify dict users when a key or value is added or cut.
00093   // Presumably a caller wants to know this in order to perform refcounting or
00094   // some other kind of memory management.  These methods are definitely only
00095   // called when references to keys or values are inserted or removed, and are
00096   // never called when the actual number of references does not change (such
00097   // as when added keys are already present or cut keys are alreading missing).
00098   // 
00099   // morkMap_mNote   mMapForm_AddKey;  // if nonzero, notify about add key
00100   // morkMap_mNote   mMapForm_CutKey;  // if nonzero, notify about cut key
00101   // morkMap_mNote   mMapForm_AddVal;  // if nonzero, notify about add val
00102   // morkMap_mNote   mMapForm_CutVal;  // if nonzero, notify about cut val
00103   //
00104   // These note methods have been removed because it seems difficult to
00105   // guarantee suitable alignment of objects passed to notification methods.
00106   
00107   // Note dict clients should pick key and val sizes that provide whatever
00108   // alignment will be required for an array of such keys and values.
00109   mork_size       mMapForm_KeySize; // size of every key (cannot be zero)
00110   mork_size       mMapForm_ValSize; // size of every val (can indeed be zero)
00111   
00112   mork_bool       mMapForm_HoldChanges; // support changes array in the map
00113   mork_change     mMapForm_DummyChange; // change used for false HoldChanges
00114   mork_bool       mMapForm_KeyIsIP;     // key is mork_ip sized
00115   mork_bool       mMapForm_ValIsIP;     // key is mork_ip sized
00116 };
00117 
00118 /*| morkAssoc: a canonical association slot in a morkMap.  A single assoc
00119 **| instance does nothing except point to the next assoc in the same bucket
00120 **| of a hash table.  Each assoc has only two interesting attributes: 1) the
00121 **| address of the assoc, and 2) the next assoc in a bucket's list.  The assoc
00122 **| address is interesting because in the context of an array of such assocs,
00123 **| one can determine the index of a particular assoc in the array by address
00124 **| arithmetic, subtracting the array address from the assoc address.  And the
00125 **| index of each assoc is the same index as the associated key and val slots
00126 **| in the associated arrays
00127 **|
00128 **|| Think of an assoc instance as really also containing a key slot and a val
00129 **| slot, where each key is mMap_Form.mMapForm_KeySize bytes in size, and
00130 **| each val is mMap_Form.mMapForm_ValSize in size.  But the key and val
00131 **| slots are stored in separate arrays with indexes that are parallel to the
00132 **| indexes in the array of morkAssoc instances.  We have taken the variable
00133 **| sized slots out of the morkAssoc structure, and put them into parallel
00134 **| arrays associated with each morkAssoc by array index.  And this leaves us
00135 **| with only the link field to the next assoc in each assoc instance.
00136 |*/
00137 class morkAssoc {
00138 public:
00139   morkAssoc*   mAssoc_Next;
00140 };
00141 
00142 
00143 #define morkDerived_kMap     /*i*/ 0x4D70 /* ascii 'Mp' */
00144 
00145 #define morkMap_kTag     /*i*/ 0x6D4D6150 /* ascii 'mMaP' */
00146 
00147 /*| morkMap: a hash table based on the public domain IronDoc hash table
00148 **| (which is in turn rather like a similar OpenDoc hash table).
00149 |*/
00150 class morkMap : public morkNode {
00151 
00152 // public: // slots inherited from morkNode (meant to inform only)
00153   // nsIMdbHeap*       mNode_Heap;
00154 
00155   // mork_base      mNode_Base;     // must equal morkBase_kNode
00156   // mork_derived   mNode_Derived;  // depends on specific node subclass
00157   
00158   // mork_access    mNode_Access;   // kOpen, kClosing, kShut, or kDead
00159   // mork_usage     mNode_Usage;    // kHeap, kStack, kMember, kGlobal, kNone
00160   // mork_able      mNode_Mutable;  // can this node be modified?
00161   // mork_load      mNode_Load;     // is this node clean or dirty?
00162   
00163   // mork_uses      mNode_Uses;     // refcount for strong refs
00164   // mork_refs      mNode_Refs;     // refcount for strong refs + weak refs
00165 
00166 public: // state is public because the entire Mork system is private
00167 
00168   nsIMdbHeap*       mMap_Heap; // strong ref to heap allocating all space
00169   mork_u4           mMap_Tag; // must equal morkMap_kTag
00170 
00171   // When a morkMap instance is constructed, the dict form slots must be
00172   // provided in order to properly configure a dict with all runtime needs:
00173   
00174   morkMapForm       mMap_Form; // construction time parameterization
00175   
00176   // Whenever the dict changes structure in a way that would affect any
00177   // iteration of the dict associations, the seed increments to show this:
00178   
00179   mork_seed         mMap_Seed;   // counter for member and structural changes
00180   
00181   // The current total assoc capacity of the dict is mMap_Slots, where
00182   // mMap_Fill of these slots are actually holding content, so mMap_Fill
00183   // is the actual membership count, and mMap_Slots is how larger membership
00184   // can become before the hash table must grow the buffers being used. 
00185   
00186   mork_count        mMap_Slots;  // count of slots in the hash table
00187   mork_fill         mMap_Fill;   // number of used slots in the hash table
00188   
00189   // Key and value slots are bound to corresponding mMap_Assocs array slots.
00190   // Instead of having a single array like this: {key,val,next}[ mMap_Slots ]
00191   // we have instead three parallel arrays with essentially the same meaning:
00192   // {key}[ mMap_Slots ], {val}[ mMap_Slots ], {assocs}[ mMap_Slots ]
00193   
00194   mork_u1*          mMap_Keys;  // mMap_Slots * mMapForm_KeySize buffer
00195   mork_u1*          mMap_Vals;  // mMap_Slots * mMapForm_ValSize buffer
00196 
00197   // An assoc is "used" when it appears in a bucket's linked list of assocs.
00198   // Until an assoc is used, it appears in the FreeList linked list.  Every
00199   // assoc that becomes used goes into the bucket determined by hashing the
00200   // key associated with a new assoc.  The key associated with a new assoc
00201   // goes in to the slot in mMap_Keys which occupies exactly the same array
00202   // index as the array index of the used assoc in the mMap_Assocs array.
00203   
00204   morkAssoc*        mMap_Assocs;   // mMap_Slots * sizeof(morkAssoc) buffer
00205   
00206   // The changes array is only needed when the
00207 
00208   mork_change*      mMap_Changes;  // mMap_Slots * sizeof(mork_change) buffer
00209   
00210   // The Buckets array need not be the same length as the Assocs array, but we
00211   // usually do it that way so the average bucket depth is no more than one.
00212   // (We could pick a different policy, or make it parameterizable, but that's
00213   // tuning we can do some other time.)
00214   
00215   morkAssoc**       mMap_Buckets;  // mMap_Slots * sizeof(morkAssoc*) buffer
00216   
00217   // The length of the mMap_FreeList should equal (mMap_Slots - mMap_Fill).
00218   // We need a free list instead of a simpler representation because assocs
00219   // can be cut and returned to availability in any kind of unknown pattern.
00220   // (However, when assocs are first allocated, or when the dict is grown, we
00221   // know all new assocs are contiguous and can chain together adjacently.)
00222   
00223   morkAssoc*        mMap_FreeList; // list of unused mMap_Assocs array slots 
00224 
00225 public: // getters (morkProbeMap compatibility)
00226   mork_fill        MapFill() const { return mMap_Fill; }
00227   
00228 // { ===== begin morkNode interface =====
00229 public: // morkNode virtual methods
00230   virtual void CloseMorkNode(morkEnv* ev); // CloseMap() only if open
00231   virtual ~morkMap(); // assert that CloseMap() executed earlier
00232   
00233 public: // morkMap construction & destruction
00234   morkMap(morkEnv* ev, const morkUsage& inUsage, nsIMdbHeap* ioNodeHeap, 
00235     mork_size inKeySize, mork_size inValSize,
00236     mork_size inSlots, nsIMdbHeap* ioSlotHeap, mork_bool inHoldChanges);
00237   
00238   void CloseMap(morkEnv* ev); // called by 
00239   
00240 public: // dynamic type identification
00241   mork_bool IsMap() const
00242   { return IsNode() && mNode_Derived == morkDerived_kMap; }
00243 // } ===== end morkNode methods =====
00244 
00245 public: // poly map hash table methods
00246 
00247 // { ===== begin morkMap poly interface =====
00248   virtual mork_bool // note: equal(a,b) implies hash(a) == hash(b)
00249   Equal(morkEnv* ev, const void* inKeyA, const void* inKeyB) const = 0;
00250 
00251   virtual mork_u4 // note: equal(a,b) implies hash(a) == hash(b)
00252   Hash(morkEnv* ev, const void* inKey) const = 0;
00253 // } ===== end morkMap poly interface =====
00254 
00255 public: // open utitity methods
00256 
00257   mork_bool GoodMapTag() const { return mMap_Tag == morkMap_kTag; }
00258   mork_bool GoodMap() const
00259   { return ( IsNode() && GoodMapTag() ); }
00260   
00261   void NewIterOutOfSyncError(morkEnv* ev);
00262   void NewBadMapError(morkEnv* ev);
00263   void NewSlotsUnderflowWarning(morkEnv* ev);
00264   void InitMap(morkEnv* ev, mork_size inSlots);
00265 
00266 protected: // internal utitity methods
00267 
00268   friend class morkMapIter;
00269   void clear_map(morkEnv* ev, nsIMdbHeap* ioHeap);
00270 
00271   void* alloc(morkEnv* ev, mork_size inSize);
00272   void* clear_alloc(morkEnv* ev, mork_size inSize);
00273   
00274   void push_free_assoc(morkAssoc* ioAssoc)
00275   {
00276     ioAssoc->mAssoc_Next = mMap_FreeList;
00277     mMap_FreeList = ioAssoc;
00278   }
00279   
00280   morkAssoc* pop_free_assoc()
00281   {
00282     morkAssoc* assoc = mMap_FreeList;
00283     if ( assoc )
00284       mMap_FreeList = assoc->mAssoc_Next;
00285     return assoc;
00286   }
00287 
00288   morkAssoc** find(morkEnv* ev, const void* inKey, mork_u4 inHash) const;
00289   
00290   mork_u1* new_keys(morkEnv* ev, mork_num inSlots);
00291   mork_u1* new_values(morkEnv* ev, mork_num inSlots);
00292   mork_change* new_changes(morkEnv* ev, mork_num inSlots);
00293   morkAssoc** new_buckets(morkEnv* ev, mork_num inSlots);
00294   morkAssoc* new_assocs(morkEnv* ev, mork_num inSlots);
00295   mork_bool new_arrays(morkEnv* ev, morkHashArrays* old, mork_num inSlots);
00296   
00297   mork_bool grow(morkEnv* ev);
00298 
00299   void get_assoc(void* outKey, void* outVal, mork_pos inPos) const;
00300   void put_assoc(const void* inKey, const void* inVal, mork_pos inPos) const;
00301   
00302 public: // inlines to form slots
00303   // const void*     FormNilKey() const { return mMap_Form.mMapForm_NilKey; }
00304   
00305   // morkMap_mEqual  FormEqual() const { return mMap_Form.mMapForm_Equal; }
00306   // morkMap_mHash   FormHash() const { return mMap_Form.mMapForm_Hash; }
00307   // orkMap_mIsNil  FormIsNil() const { return mMap_Form.mMapForm_IsNil; } 
00308     
00309   // morkMap_mNote   FormAddKey() const { return mMap_Form.mMapForm_AddKey; }
00310   // morkMap_mNote   FormCutKey() const { return mMap_Form.mMapForm_CutKey; }
00311   // morkMap_mNote   FormAddVal() const { return mMap_Form.mMapForm_AddVal; }
00312   // morkMap_mNote   FormCutVal() const { return mMap_Form.mMapForm_CutVal; }
00313   
00314   mork_size       FormKeySize() const { return mMap_Form.mMapForm_KeySize; }
00315   mork_size       FormValSize() const { return mMap_Form.mMapForm_ValSize; }
00316 
00317   mork_bool       FormKeyIsIP() const { return mMap_Form.mMapForm_KeyIsIP; }
00318   mork_bool       FormValIsIP() const { return mMap_Form.mMapForm_ValIsIP; }
00319 
00320   mork_bool       FormHoldChanges() const
00321   { return mMap_Form.mMapForm_HoldChanges; }
00322   
00323   mork_change*    FormDummyChange()
00324   { return &mMap_Form.mMapForm_DummyChange; }
00325 
00326 public: // other map methods
00327  
00328   mork_bool Put(morkEnv* ev, const void* inKey, const void* inVal,
00329     void* outKey, void* outVal, mork_change** outChange);
00330     
00331   mork_bool Cut(morkEnv* ev, const void* inKey,
00332     void* outKey, void* outVal, mork_change** outChange);
00333     
00334   mork_bool Get(morkEnv* ev, const void* inKey, 
00335     void* outKey, void* outVal, mork_change** outChange);
00336     
00337   mork_num CutAll(morkEnv* ev);
00338 
00339 private: // copying is not allowed
00340   morkMap(const morkMap& other);
00341   morkMap& operator=(const morkMap& other);
00342 
00343 
00344 public: // typesafe refcounting inlines calling inherited morkNode methods
00345   static void SlotWeakMap(morkMap* me,
00346     morkEnv* ev, morkMap** ioSlot)
00347   { morkNode::SlotWeakNode((morkNode*) me, ev, (morkNode**) ioSlot); }
00348   
00349   static void SlotStrongMap(morkMap* me,
00350     morkEnv* ev, morkMap** ioSlot)
00351   { morkNode::SlotStrongNode((morkNode*) me, ev, (morkNode**) ioSlot); }
00352 };
00353 
00354 /*| morkMapIter: an iterator for morkMap and subclasses.  This is not a node,
00355 **| and expected usage is as a member of some other node subclass, such as in
00356 **| a cursor subclass or a thumb subclass.  Also, iters might be as temp stack
00357 **| objects when scanning the content of a map.
00358 |*/
00359 class morkMapIter{  // iterator for hash table map
00360 
00361 protected:
00362   morkMap*    mMapIter_Map;      // map to iterate, NOT refcounted
00363   mork_seed   mMapIter_Seed;     // cached copy of map's seed
00364   
00365   morkAssoc** mMapIter_Bucket;   // one bucket in mMap_Buckets array
00366   morkAssoc** mMapIter_AssocRef; // usually *AtRef equals Here
00367   morkAssoc*  mMapIter_Assoc;    // the current assoc in an iteration
00368   morkAssoc*  mMapIter_Next;     // mMapIter_Assoc->mAssoc_Next */
00369 
00370 public:
00371   morkMapIter(morkEnv* ev, morkMap* ioMap);
00372   void CloseMapIter(morkEnv* ev);
00373  
00374   morkMapIter( ); // everything set to zero -- need to call InitMapIter()
00375 
00376 protected: // we want all subclasses to provide typesafe wrappers:
00377 
00378   void InitMapIter(morkEnv* ev, morkMap* ioMap);
00379  
00380   // The morkAssoc returned below is always either mork_change* or
00381   // else nil (when there is no such assoc).  We return a pointer to
00382   // the change rather than a simple bool, because callers might
00383   // want to access change info associated with an assoc.
00384   
00385   mork_change* First(morkEnv* ev, void* outKey, void* outVal);
00386   mork_change* Next(morkEnv* ev, void* outKey, void* outVal);
00387   mork_change* Here(morkEnv* ev, void* outKey, void* outVal);
00388   
00389   mork_change* CutHere(morkEnv* ev, void* outKey, void* outVal);
00390 };
00391 
00392 //3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789
00393 
00394 #endif /* _MORKMAP_ */