Back to index

lightning-sunbird  0.9+nobinonly
morkMap.cpp
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 // This code is mostly a port to C++ from public domain IronDoc C sources.
00039 // Note many code comments here come verbatim from cut-and-pasted IronDoc.
00040 
00041 #ifndef _MDB_
00042 #include "mdb.h"
00043 #endif
00044 
00045 #ifndef _MORK_
00046 #include "mork.h"
00047 #endif
00048 
00049 #ifndef _MORKNODE_
00050 #include "morkNode.h"
00051 #endif
00052 
00053 #ifndef _MORKMAP_
00054 #include "morkMap.h"
00055 #endif
00056 
00057 #ifndef _MORKENV_
00058 #include "morkEnv.h"
00059 #endif
00060 
00061 
00062 class morkHashArrays {
00063 public:
00064   nsIMdbHeap*   mHashArrays_Heap;     // copy of mMap_Heap
00065   mork_count    mHashArrays_Slots;    // copy of mMap_Slots
00066   
00067   mork_u1*      mHashArrays_Keys;     // copy of mMap_Keys
00068   mork_u1*      mHashArrays_Vals;     // copy of mMap_Vals
00069   morkAssoc*    mHashArrays_Assocs;   // copy of mMap_Assocs
00070   mork_change*  mHashArrays_Changes;  // copy of mMap_Changes
00071   morkAssoc**   mHashArrays_Buckets;  // copy of mMap_Buckets
00072   morkAssoc*    mHashArrays_FreeList; // copy of mMap_FreeList
00073   
00074 public:
00075   void finalize(morkEnv* ev);
00076 };
00077 
00078 void morkHashArrays::finalize(morkEnv* ev)
00079 {
00080   nsIMdbEnv* menv = ev->AsMdbEnv();
00081   nsIMdbHeap* heap = mHashArrays_Heap;
00082   
00083   if ( heap )
00084   {
00085     if ( mHashArrays_Keys )
00086       heap->Free(menv, mHashArrays_Keys);
00087     if ( mHashArrays_Vals )
00088       heap->Free(menv, mHashArrays_Vals);
00089     if ( mHashArrays_Assocs )
00090       heap->Free(menv, mHashArrays_Assocs);
00091     if ( mHashArrays_Changes )
00092       heap->Free(menv, mHashArrays_Changes);
00093     if ( mHashArrays_Buckets )
00094       heap->Free(menv, mHashArrays_Buckets);
00095   }
00096 }
00097 
00098 //3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789
00099 
00100 // ````` ````` ````` ````` ````` 
00101 // { ===== begin morkNode interface =====
00102 
00103 /*public virtual*/ void
00104 morkMap::CloseMorkNode(morkEnv* ev) // CloseMap() only if open
00105 {
00106   if ( this->IsOpenNode() )
00107   {
00108     this->MarkClosing();
00109     this->CloseMap(ev);
00110     this->MarkShut();
00111   }
00112 }
00113 
00114 /*public virtual*/
00115 morkMap::~morkMap() // assert CloseMap() executed earlier
00116 {
00117   MORK_ASSERT(mMap_FreeList==0);
00118   MORK_ASSERT(mMap_Buckets==0);
00119   MORK_ASSERT(mMap_Keys==0);
00120   MORK_ASSERT(mMap_Vals==0);
00121   MORK_ASSERT(mMap_Changes==0);
00122   MORK_ASSERT(mMap_Assocs==0);
00123 }
00124 
00125 /*public non-poly*/ void
00126 morkMap::CloseMap(morkEnv* ev) // called by CloseMorkNode();
00127 {
00128   if ( this )
00129   {
00130     if ( this->IsNode() )
00131     {
00132       nsIMdbHeap* heap = mMap_Heap;
00133       if ( heap ) /* need to free the arrays? */
00134       {
00135         nsIMdbEnv* menv = ev->AsMdbEnv();
00136         
00137         if ( mMap_Keys )
00138           heap->Free(menv, mMap_Keys);
00139           
00140         if ( mMap_Vals )
00141           heap->Free(menv, mMap_Vals);
00142           
00143         if ( mMap_Assocs )
00144           heap->Free(menv, mMap_Assocs);
00145           
00146         if ( mMap_Buckets )
00147           heap->Free(menv, mMap_Buckets);
00148           
00149         if ( mMap_Changes )
00150           heap->Free(menv, mMap_Changes);
00151       }
00152       mMap_Keys = 0;
00153       mMap_Vals = 0;
00154       mMap_Buckets = 0;
00155       mMap_Assocs = 0;
00156       mMap_Changes = 0;
00157       mMap_FreeList = 0;
00158       MORK_MEMSET(&mMap_Form, 0, sizeof(morkMapForm));
00159       this->MarkShut();
00160     }
00161     else
00162       this->NonNodeError(ev);
00163   }
00164   else
00165     ev->NilPointerError();
00166 }
00167 
00168 // } ===== end morkNode methods =====
00169 // ````` ````` ````` ````` ````` 
00170 
00171 void
00172 morkMap::clear_map(morkEnv* ev, nsIMdbHeap* ioSlotHeap)
00173 {
00174   mMap_Tag = 0;
00175   mMap_Seed = 0;
00176   mMap_Slots = 0;
00177   mMap_Fill = 0;
00178   mMap_Keys = 0;
00179   mMap_Vals = 0;
00180   mMap_Assocs = 0;
00181   mMap_Changes = 0;
00182   mMap_Buckets = 0;
00183   mMap_FreeList = 0;
00184   MORK_MEMSET(&mMap_Form, 0, sizeof(morkMapForm));
00185   
00186   mMap_Heap = 0;
00187   if ( ioSlotHeap )
00188   {
00189     nsIMdbHeap_SlotStrongHeap(ioSlotHeap, ev, &mMap_Heap);
00190   }
00191   else
00192     ev->NilPointerError();
00193 }
00194 
00195 morkMap::morkMap(morkEnv* ev, const morkUsage& inUsage, nsIMdbHeap* ioHeap, 
00196   mork_size inKeySize, mork_size inValSize,
00197   mork_size inSlots, nsIMdbHeap* ioSlotHeap, mork_bool inHoldChanges)
00198 : morkNode(ev, inUsage, ioHeap)
00199 , mMap_Heap( 0 )
00200 {
00201   if ( ev->Good() )
00202   {
00203     this->clear_map(ev, ioSlotHeap);
00204     if ( ev->Good() )
00205     {
00206       mMap_Form.mMapForm_HoldChanges = inHoldChanges;
00207       
00208       mMap_Form.mMapForm_KeySize = inKeySize;
00209       mMap_Form.mMapForm_ValSize = inValSize;
00210       mMap_Form.mMapForm_KeyIsIP = ( inKeySize == sizeof(mork_ip) );
00211       mMap_Form.mMapForm_ValIsIP = ( inValSize == sizeof(mork_ip) );
00212       
00213       this->InitMap(ev, inSlots);
00214       if ( ev->Good() )
00215         mNode_Derived = morkDerived_kMap;
00216     }
00217   }
00218 }
00219 
00220 void
00221 morkMap::NewIterOutOfSyncError(morkEnv* ev)
00222 {
00223   ev->NewError("map iter out of sync");
00224 }
00225 
00226 void morkMap::NewBadMapError(morkEnv* ev)
00227 {
00228   ev->NewError("bad morkMap tag");
00229   if ( !this )
00230     ev->NewError("nil morkMap instance");
00231 }
00232 
00233 void morkMap::NewSlotsUnderflowWarning(morkEnv* ev)
00234 {
00235   ev->NewWarning("member count underflow");
00236 }
00237 
00238 void morkMap::InitMap(morkEnv* ev, mork_size inSlots)
00239 {
00240   if ( ev->Good() )
00241   {
00242     morkHashArrays old;
00243     // MORK_MEMCPY(&mMap_Form, &inForm, sizeof(morkMapForm));
00244     if ( inSlots < 3 ) /* requested capacity absurdly small? */
00245       inSlots = 3; /* bump it up to a minimum practical level */
00246     else if ( inSlots > (128 * 1024) ) /* requested slots absurdly big? */
00247       inSlots = (128 * 1024); /* decrease it to a maximum practical level */
00248       
00249     if ( this->new_arrays(ev, &old, inSlots) )
00250       mMap_Tag = morkMap_kTag;
00251 
00252     MORK_MEMSET(&old, 0, sizeof(morkHashArrays)); // do NOT finalize
00253   }
00254 }
00255 
00256 morkAssoc**
00257 morkMap::find(morkEnv* ev, const void* inKey, mork_u4 inHash) const
00258 {
00259   mork_u1* keys = mMap_Keys;
00260   mork_num keySize = this->FormKeySize();
00261   // morkMap_mEqual equal = this->FormEqual();
00262   
00263   morkAssoc** ref = mMap_Buckets + (inHash % mMap_Slots);
00264   morkAssoc* assoc = *ref;
00265   while ( assoc ) /* look at another assoc in the bucket? */
00266   {
00267     mork_pos i = assoc - mMap_Assocs; /* index of this assoc */
00268     if ( this->Equal(ev, keys + (i * keySize), inKey) ) /* found? */
00269       return ref;
00270       
00271     ref = &assoc->mAssoc_Next; /* consider next assoc slot in bucket */
00272     assoc = *ref; /* if this is null, then we are done */
00273   }
00274   return 0;
00275 }
00276 
00277 /*| get_assoc: read the key and/or value at index inPos
00278 |*/
00279 void
00280 morkMap::get_assoc(void* outKey, void* outVal, mork_pos inPos) const
00281 {
00282   mork_num valSize = this->FormValSize();
00283   if ( valSize && outVal ) /* map holds values? caller wants the value? */
00284   {
00285     const mork_u1* value = mMap_Vals + (valSize * inPos);
00286     if ( valSize == sizeof(mork_ip) && this->FormValIsIP() ) /* ip case? */
00287       *((mork_ip*) outVal) = *((const mork_ip*) value);
00288     else
00289       MORK_MEMCPY(outVal, value, valSize);
00290   }
00291   if ( outKey ) /* caller wants the key? */
00292   {
00293     mork_num keySize = this->FormKeySize();
00294     const mork_u1* key = mMap_Keys + (keySize * inPos);
00295     if ( keySize == sizeof(mork_ip) && this->FormKeyIsIP() ) /* ip case? */
00296       *((mork_ip*) outKey) = *((const mork_ip*) key);
00297     else
00298       MORK_MEMCPY(outKey, key, keySize);
00299   }
00300 }
00301 
00302 /*| put_assoc: write the key and/or value at index inPos
00303 |*/
00304 void
00305 morkMap::put_assoc(const void* inKey, const void* inVal, mork_pos inPos) const
00306 {
00307   mork_num valSize = this->FormValSize();
00308   if ( valSize && inVal ) /* map holds values? caller sends a value? */
00309   {
00310     mork_u1* value = mMap_Vals + (valSize * inPos);
00311     if ( valSize == sizeof(mork_ip) && this->FormValIsIP() ) /* ip case? */
00312       *((mork_ip*) value) = *((const mork_ip*) inVal);
00313     else
00314       MORK_MEMCPY(value, inVal, valSize);
00315   }
00316   if ( inKey ) /* caller sends a key? */
00317   {
00318     mork_num keySize = this->FormKeySize();
00319     mork_u1* key = mMap_Keys + (keySize * inPos);
00320     if ( keySize == sizeof(mork_ip) && this->FormKeyIsIP() ) /* ip case? */
00321       *((mork_ip*) key) = *((const mork_ip*) inKey);
00322     else
00323       MORK_MEMCPY(key, inKey, keySize);
00324   }
00325 }
00326 
00327 void*
00328 morkMap::clear_alloc(morkEnv* ev, mork_size inSize)
00329 {
00330   void* p = 0;
00331   nsIMdbHeap* heap = mMap_Heap;
00332   if ( heap )
00333   {
00334     if ( heap->Alloc(ev->AsMdbEnv(), inSize, (void**) &p) == 0 && p )
00335     {
00336       MORK_MEMSET(p, 0, inSize);
00337       return p;
00338     }
00339   }
00340   else
00341     ev->NilPointerError();
00342     
00343   return (void*) 0;
00344 }
00345 
00346 void*
00347 morkMap::alloc(morkEnv* ev, mork_size inSize)
00348 {
00349   void* p = 0;
00350   nsIMdbHeap* heap = mMap_Heap;
00351   if ( heap )
00352   {
00353     if ( heap->Alloc(ev->AsMdbEnv(), inSize, (void**) &p) == 0 && p )
00354       return p;
00355   }
00356   else
00357     ev->NilPointerError();
00358 
00359   return (void*) 0;
00360 }
00361 
00362 /*| new_keys: allocate an array of inSlots new keys filled with zero.
00363 |*/
00364 mork_u1*
00365 morkMap::new_keys(morkEnv* ev, mork_num inSlots)
00366 {
00367   mork_num size = inSlots * this->FormKeySize();
00368   return (mork_u1*) this->clear_alloc(ev, size);
00369 }
00370 
00371 /*| new_values: allocate an array of inSlots new values filled with zero.
00372 **| When values are zero sized, we just return a null pointer.
00373 |*/
00374 mork_u1*
00375 morkMap::new_values(morkEnv* ev, mork_num inSlots)
00376 {
00377   mork_u1* values = 0;
00378   mork_num size = inSlots * this->FormValSize();
00379   if ( size )
00380     values = (mork_u1*) this->clear_alloc(ev, size);
00381   return values;
00382 }
00383 
00384 mork_change*
00385 morkMap::new_changes(morkEnv* ev, mork_num inSlots)
00386 {
00387   mork_change* changes = 0;
00388   mork_num size = inSlots * sizeof(mork_change);
00389   if ( size && mMap_Form.mMapForm_HoldChanges )
00390     changes = (mork_change*) this->clear_alloc(ev, size);
00391   return changes;
00392 }
00393 
00394 /*| new_buckets: allocate an array of inSlots new buckets filled with zero.
00395 |*/
00396 morkAssoc**
00397 morkMap::new_buckets(morkEnv* ev, mork_num inSlots)
00398 {
00399   mork_num size = inSlots * sizeof(morkAssoc*);
00400   return (morkAssoc**) this->clear_alloc(ev, size);
00401 }
00402 
00403 /*| new_assocs: allocate an array of inSlots new assocs, with each assoc
00404 **| linked together in a list with the first array element at the list head
00405 **| and the last element at the list tail. (morkMap::grow() needs this.)
00406 |*/
00407 morkAssoc*
00408 morkMap::new_assocs(morkEnv* ev, mork_num inSlots)
00409 {
00410   mork_num size = inSlots * sizeof(morkAssoc);
00411   morkAssoc* assocs = (morkAssoc*) this->alloc(ev, size);
00412   if ( assocs ) /* able to allocate the array? */
00413   {
00414     morkAssoc* a = assocs + (inSlots - 1); /* the last array element */
00415     a->mAssoc_Next = 0; /* terminate tail element of the list with null */
00416     while ( --a >= assocs ) /* another assoc to link into the list? */
00417       a->mAssoc_Next = a + 1; /* each points to the following assoc */
00418   }
00419   return assocs;
00420 }
00421 
00422 mork_bool
00423 morkMap::new_arrays(morkEnv* ev, morkHashArrays* old, mork_num inSlots)
00424 {
00425   mork_bool outNew = morkBool_kFalse;
00426     
00427   /* see if we can allocate all the new arrays before we go any further: */
00428   morkAssoc** newBuckets = this->new_buckets(ev, inSlots);
00429   morkAssoc* newAssocs = this->new_assocs(ev, inSlots);
00430   mork_u1* newKeys = this->new_keys(ev, inSlots);
00431   mork_u1* newValues = this->new_values(ev, inSlots);
00432   mork_change* newChanges = this->new_changes(ev, inSlots);
00433   
00434   /* it is okay for newChanges to be null when changes are not held: */
00435   mork_bool okayChanges = ( newChanges || !this->FormHoldChanges() );
00436   
00437   /* it is okay for newValues to be null when values are zero sized: */
00438   mork_bool okayValues = ( newValues || !this->FormValSize() );
00439   
00440   if ( newBuckets && newAssocs && newKeys && okayChanges && okayValues )
00441   {
00442     outNew = morkBool_kTrue; /* yes, we created all the arrays we need */
00443 
00444     /* init the old hashArrays with slots from this hash table: */
00445     old->mHashArrays_Heap = mMap_Heap;
00446     
00447     old->mHashArrays_Slots = mMap_Slots;
00448     old->mHashArrays_Keys = mMap_Keys;
00449     old->mHashArrays_Vals = mMap_Vals;
00450     old->mHashArrays_Assocs = mMap_Assocs;
00451     old->mHashArrays_Buckets = mMap_Buckets;
00452     old->mHashArrays_Changes = mMap_Changes;
00453     
00454     /* now replace all our array slots with the new structures: */
00455     ++mMap_Seed; /* note the map is now changed */
00456     mMap_Keys = newKeys;
00457     mMap_Vals = newValues;
00458     mMap_Buckets = newBuckets;
00459     mMap_Assocs = newAssocs;
00460     mMap_FreeList = newAssocs; /* all are free to start with */
00461     mMap_Changes = newChanges;
00462     mMap_Slots = inSlots;
00463   }
00464   else /* free the partial set of arrays that were actually allocated */
00465   {
00466     nsIMdbEnv* menv = ev->AsMdbEnv();
00467     nsIMdbHeap* heap = mMap_Heap;
00468     if ( newBuckets )
00469       heap->Free(menv, newBuckets);
00470     if ( newAssocs )
00471       heap->Free(menv, newAssocs);
00472     if ( newKeys )
00473       heap->Free(menv, newKeys);
00474     if ( newValues )
00475       heap->Free(menv, newValues);
00476     if ( newChanges )
00477       heap->Free(menv, newChanges);
00478     
00479     MORK_MEMSET(old, 0, sizeof(morkHashArrays));
00480   }
00481   
00482   return outNew;
00483 }
00484 
00485 /*| grow: make the map arrays bigger by 33%.  The old map is completely
00486 **| full, or else we would not have called grow() to get more space.  This
00487 **| means the free list is empty, and also means every old key and value is in
00488 **| use in the old arrays.  So every key and value must be copied to the new
00489 **| arrays, and since they are contiguous in the old arrays, we can efficiently
00490 **| bitwise copy them in bulk from the old arrays to the new arrays, without
00491 **| paying any attention to the structure of the old arrays.
00492 **|
00493 **|| The content of the old bucket and assoc arrays need not be copied because
00494 **| this information is going to be completely rebuilt by rehashing all the
00495 **| keys into their new buckets, given the new larger map capacity.  The new
00496 **| bucket array from new_arrays() is assumed to contain all zeroes, which is
00497 **| necessary to ensure the lists in each bucket stay null terminated as we
00498 **| build the new linked lists.  (Note no old bucket ordering is preserved.)
00499 **|
00500 **|| If the old capacity is N, then in the new arrays the assocs with indexes
00501 **| from zero to N-1 are still allocated and must be rehashed into the map.
00502 **| The new free list contains all the following assocs, starting with the new
00503 **| assoc link at index N.  (We call the links in the link array "assocs"
00504 **| because allocating a link is the same as allocating the key/value pair
00505 **| with the same index as the link.)
00506 **|
00507 **|| The new free list is initialized simply by pointing at the first new link
00508 **| in the assoc array after the size of the old assoc array.  This assumes
00509 **| that FeHashTable_new_arrays() has already linked all the new assocs into a
00510 **| list with the first at the head of the list and the last at the tail of the
00511 **| list.  So by making the free list point to the first of the new uncopied
00512 **| assocs, the list is already well-formed.
00513 |*/
00514 mork_bool morkMap::grow(morkEnv* ev)
00515 {
00516   if ( mMap_Heap ) /* can we grow the map? */
00517   {
00518     mork_num newSlots = (mMap_Slots * 2); /* +100% */
00519     morkHashArrays old; /* a place to temporarily hold all the old arrays */
00520     if ( this->new_arrays(ev, &old, newSlots) ) /* have more? */
00521     {
00522       // morkMap_mHash hash = this->FormHash(); /* for terse loop use */
00523       
00524       /* figure out the bulk volume sizes of old keys and values to move: */
00525       mork_num oldSlots = old.mHashArrays_Slots; /* number of old assocs */
00526       mork_num keyBulk = oldSlots * this->FormKeySize(); /* key volume */
00527       mork_num valBulk = oldSlots * this->FormValSize(); /* values */
00528       
00529       /* convenient variables for new arrays that need to be rehashed: */
00530       morkAssoc** newBuckets = mMap_Buckets; /* new all zeroes */
00531       morkAssoc* newAssocs = mMap_Assocs; /* hash into buckets */
00532       morkAssoc* newFreeList = newAssocs + oldSlots; /* new room is free */
00533       mork_u1* key = mMap_Keys; /* the first key to rehash */
00534       --newAssocs; /* back up one before preincrement used in while loop */
00535       
00536       /* move all old keys and values to the new arrays: */
00537       MORK_MEMCPY(mMap_Keys, old.mHashArrays_Keys, keyBulk);
00538       if ( valBulk ) /* are values nonzero sized? */
00539         MORK_MEMCPY(mMap_Vals, old.mHashArrays_Vals, valBulk);
00540         
00541       mMap_FreeList = newFreeList; /* remaining assocs are free */
00542       
00543       while ( ++newAssocs < newFreeList ) /* rehash another old assoc? */
00544       {
00545         morkAssoc** top = newBuckets + (this->Hash(ev, key) % newSlots);
00546         key += this->FormKeySize(); /* the next key to rehash */
00547         newAssocs->mAssoc_Next = *top; /* link to prev bucket top */
00548         *top = newAssocs; /* push assoc on top of bucket */
00549       }
00550       ++mMap_Seed; /* note the map has changed */
00551       old.finalize(ev); /* remember to free the old arrays */
00552     }
00553   }
00554   else ev->OutOfMemoryError();
00555   
00556   return ev->Good();
00557 }
00558 
00559 
00560 mork_bool
00561 morkMap::Put(morkEnv* ev, const void* inKey, const void* inVal,
00562   void* outKey, void* outVal, mork_change** outChange)
00563 {
00564   mork_bool outPut = morkBool_kFalse;
00565   
00566   if ( this->GoodMap() ) /* looks good? */
00567   {
00568     mork_u4 hash = this->Hash(ev, inKey);
00569     morkAssoc** ref = this->find(ev, inKey, hash);
00570     if ( ref ) /* assoc was found? reuse an existing assoc slot? */
00571     {
00572       outPut = morkBool_kTrue; /* inKey was indeed already inside the map */
00573     }
00574     else /* assoc not found -- need to allocate a new assoc slot */
00575     {
00576       morkAssoc* assoc = this->pop_free_assoc();
00577       if ( !assoc ) /* no slots remaining in free list? must grow map? */
00578       {
00579         if ( this->grow(ev) ) /* successfully made map larger? */
00580           assoc = this->pop_free_assoc();
00581       }
00582       if ( assoc ) /* allocated new assoc without error? */
00583       {
00584         ref = mMap_Buckets + (hash % mMap_Slots);
00585         assoc->mAssoc_Next = *ref; /* link to prev bucket top */
00586         *ref = assoc; /* push assoc on top of bucket */
00587           
00588         ++mMap_Fill; /* one more member in the collection */
00589         ++mMap_Seed; /* note the map has changed */
00590       }
00591     }
00592     if ( ref ) /* did not have an error during possible growth? */
00593     {
00594       mork_pos i = (*ref) - mMap_Assocs; /* index of assoc */
00595       if ( outPut && (outKey || outVal) ) /* copy old before cobbering? */
00596         this->get_assoc(outKey, outVal, i);
00597 
00598       this->put_assoc(inKey, inVal, i);
00599       ++mMap_Seed; /* note the map has changed */
00600       
00601       if ( outChange )
00602       {
00603         if ( mMap_Changes )
00604           *outChange = mMap_Changes + i;
00605         else
00606           *outChange = this->FormDummyChange();
00607       }
00608     }
00609   }
00610   else this->NewBadMapError(ev);
00611   
00612   return outPut;
00613 }
00614 
00615 mork_num
00616 morkMap::CutAll(morkEnv* ev)
00617 {
00618   mork_num outCutAll = 0;
00619   
00620   if ( this->GoodMap() ) /* map looks good? */
00621   {
00622     mork_num slots = mMap_Slots;
00623     morkAssoc* before = mMap_Assocs - 1; /* before first member */
00624     morkAssoc* assoc = before + slots; /* the very last member */
00625 
00626     ++mMap_Seed; /* note the map is changed */
00627 
00628     /* make the assoc array a linked list headed by first & tailed by last: */
00629     assoc->mAssoc_Next = 0; /* null terminate the new free list */
00630     while ( --assoc > before ) /* another assoc to link into the list? */
00631       assoc->mAssoc_Next = assoc + 1;
00632     mMap_FreeList = mMap_Assocs; /* all are free */
00633 
00634     outCutAll = mMap_Fill; /* we'll cut all of them of course */
00635 
00636     mMap_Fill = 0; /* the map is completely empty */
00637   }
00638   else this->NewBadMapError(ev);
00639   
00640   return outCutAll;
00641 }
00642 
00643 mork_bool
00644 morkMap::Cut(morkEnv* ev, const void* inKey,
00645   void* outKey, void* outVal, mork_change** outChange)
00646 {
00647   mork_bool outCut = morkBool_kFalse;
00648   
00649   if ( this->GoodMap() ) /* looks good? */
00650   {
00651     mork_u4 hash = this->Hash(ev, inKey);
00652     morkAssoc** ref = this->find(ev, inKey, hash);
00653     if ( ref ) /* found an assoc for key? */
00654     {
00655       outCut = morkBool_kTrue;
00656       morkAssoc* assoc = *ref;
00657       mork_pos i = assoc - mMap_Assocs; /* index of assoc */
00658       if ( outKey || outVal )
00659         this->get_assoc(outKey, outVal, i);
00660 
00661       *ref = assoc->mAssoc_Next; /* unlink the found assoc */
00662       this->push_free_assoc(assoc); /* and put it in free list */
00663 
00664       if ( outChange )
00665       {
00666         if ( mMap_Changes )
00667           *outChange = mMap_Changes + i;
00668         else
00669           *outChange = this->FormDummyChange();
00670       }
00671       
00672       ++mMap_Seed; /* note the map has changed */
00673       if ( mMap_Fill ) /* the count shows nonzero members? */
00674         --mMap_Fill; /* one less member in the collection */
00675       else
00676         this->NewSlotsUnderflowWarning(ev);
00677     }
00678   }
00679   else this->NewBadMapError(ev);
00680   
00681   return outCut;
00682 }
00683 
00684 mork_bool
00685 morkMap::Get(morkEnv* ev, const void* inKey,
00686   void* outKey, void* outVal, mork_change** outChange)
00687 {
00688   mork_bool outGet = morkBool_kFalse;
00689   
00690   if ( this->GoodMap() ) /* looks good? */
00691   {
00692     mork_u4 hash = this->Hash(ev, inKey);
00693     morkAssoc** ref = this->find(ev, inKey, hash);
00694     if ( ref ) /* found an assoc for inKey? */
00695     {
00696       mork_pos i = (*ref) - mMap_Assocs; /* index of assoc */
00697       outGet = morkBool_kTrue;
00698       this->get_assoc(outKey, outVal, i);
00699       if ( outChange )
00700       {
00701         if ( mMap_Changes )
00702           *outChange = mMap_Changes + i;
00703         else
00704           *outChange = this->FormDummyChange();
00705       }
00706     }
00707   }
00708   else this->NewBadMapError(ev);
00709   
00710   return outGet;
00711 }
00712 
00713 
00714 morkMapIter::morkMapIter( )
00715 : mMapIter_Map( 0 )
00716 , mMapIter_Seed( 0 )
00717   
00718 , mMapIter_Bucket( 0 )
00719 , mMapIter_AssocRef( 0 )
00720 , mMapIter_Assoc( 0 )
00721 , mMapIter_Next( 0 )
00722 {
00723 }
00724 
00725 void
00726 morkMapIter::InitMapIter(morkEnv* ev, morkMap* ioMap)
00727 {
00728   mMapIter_Map = 0;
00729   mMapIter_Seed = 0;
00730 
00731   mMapIter_Bucket = 0;
00732   mMapIter_AssocRef = 0;
00733   mMapIter_Assoc = 0;
00734   mMapIter_Next = 0;
00735 
00736   if ( ioMap )
00737   {
00738     if ( ioMap->GoodMap() )
00739     {
00740       mMapIter_Map = ioMap;
00741       mMapIter_Seed = ioMap->mMap_Seed;
00742     }
00743     else ioMap->NewBadMapError(ev);
00744   }
00745   else ev->NilPointerError();
00746 }
00747 
00748 morkMapIter::morkMapIter(morkEnv* ev, morkMap* ioMap)
00749 : mMapIter_Map( 0 )
00750 , mMapIter_Seed( 0 )
00751   
00752 , mMapIter_Bucket( 0 )
00753 , mMapIter_AssocRef( 0 )
00754 , mMapIter_Assoc( 0 )
00755 , mMapIter_Next( 0 )
00756 {
00757   if ( ioMap )
00758   {
00759     if ( ioMap->GoodMap() )
00760     {
00761       mMapIter_Map = ioMap;
00762       mMapIter_Seed = ioMap->mMap_Seed;
00763     }
00764     else ioMap->NewBadMapError(ev);
00765   }
00766   else ev->NilPointerError();
00767 }
00768 
00769 void
00770 morkMapIter::CloseMapIter(morkEnv* ev)
00771 {
00772   MORK_USED_1(ev);
00773   mMapIter_Map = 0;
00774   mMapIter_Seed = 0;
00775   
00776   mMapIter_Bucket = 0;
00777   mMapIter_AssocRef = 0;
00778   mMapIter_Assoc = 0;
00779   mMapIter_Next = 0;
00780 }
00781 
00782 mork_change*
00783 morkMapIter::First(morkEnv* ev, void* outKey, void* outVal)
00784 {
00785   mork_change* outFirst = 0;
00786   
00787   morkMap* map = mMapIter_Map;
00788   
00789   if ( map && map->GoodMap() ) /* map looks good? */
00790   {
00791     morkAssoc** bucket = map->mMap_Buckets;
00792     morkAssoc** end = bucket + map->mMap_Slots; /* one past last */
00793  
00794     mMapIter_Seed = map->mMap_Seed; /* sync the seeds */
00795    
00796     while ( bucket < end ) /* another bucket in which to look for assocs? */
00797     {
00798       morkAssoc* assoc = *bucket++;
00799       if ( assoc ) /* found the first map assoc in use? */
00800       {
00801         mork_pos i = assoc - map->mMap_Assocs;
00802         mork_change* c = map->mMap_Changes;
00803         outFirst = ( c )? (c + i) : map->FormDummyChange();
00804         
00805         mMapIter_Assoc = assoc; /* current assoc in iteration */
00806         mMapIter_Next = assoc->mAssoc_Next; /* more in bucket */
00807         mMapIter_Bucket = --bucket; /* bucket for this assoc */
00808         mMapIter_AssocRef = bucket; /* slot referencing assoc */
00809         
00810         map->get_assoc(outKey, outVal, i);
00811           
00812         break; /* end while loop */
00813       }
00814     }
00815   }
00816   else map->NewBadMapError(ev);
00817 
00818   return outFirst;
00819 }
00820 
00821 mork_change*
00822 morkMapIter::Next(morkEnv* ev, void* outKey, void* outVal)
00823 {
00824   mork_change* outNext = 0;
00825   
00826   morkMap* map = mMapIter_Map;
00827   
00828   if ( map && map->GoodMap() ) /* map looks good? */
00829   {
00830     if ( mMapIter_Seed == map->mMap_Seed ) /* in sync? */
00831     {
00832       morkAssoc* here = mMapIter_Assoc; /* current assoc */
00833       if ( here ) /* iteration is not yet concluded? */
00834       {
00835         morkAssoc* next = mMapIter_Next;
00836         morkAssoc* assoc = next; /* default new mMapIter_Assoc */  
00837         if ( next ) /* there are more assocs in the same bucket after Here? */
00838         {
00839           morkAssoc** ref = mMapIter_AssocRef;
00840           
00841           /* (*HereRef) equals Here, except when Here has been cut, after
00842           ** which (*HereRef) always equals Next.  So if (*HereRef) is not
00843           ** equal to Next, then HereRef still needs to be updated to point
00844           ** somewhere else other than Here.  Otherwise it is fine.
00845           */
00846           if ( *ref != next ) /* Here was not cut? must update HereRef? */
00847             mMapIter_AssocRef = &here->mAssoc_Next;
00848             
00849           mMapIter_Next = next->mAssoc_Next;
00850         }
00851         else /* look for the next assoc in the next nonempty bucket */
00852         {
00853           morkAssoc** bucket = map->mMap_Buckets;
00854           morkAssoc** end = bucket + map->mMap_Slots; /* beyond */
00855           mMapIter_Assoc = 0; /* default to no more assocs */
00856           bucket = mMapIter_Bucket; /* last exhausted bucket */
00857           mMapIter_Assoc = 0; /* default to iteration ended */
00858           
00859           while ( ++bucket < end ) /* another bucket to search for assocs? */
00860           {
00861             assoc = *bucket;
00862             if ( assoc ) /* found another map assoc in use? */
00863             {
00864               mMapIter_Bucket = bucket;
00865               mMapIter_AssocRef = bucket; /* ref to assoc */
00866               mMapIter_Next = assoc->mAssoc_Next; /* more */
00867               
00868               break; /* end while loop */
00869             }
00870           }
00871         }
00872         if ( assoc ) /* did we find another assoc in the iteration? */
00873         {
00874           mMapIter_Assoc = assoc; /* current assoc */
00875           mork_pos i = assoc - map->mMap_Assocs;
00876           mork_change* c = map->mMap_Changes;
00877           outNext = ( c )? (c + i) : map->FormDummyChange();
00878         
00879           map->get_assoc( outKey, outVal, i);
00880         }
00881       }
00882     }
00883     else map->NewIterOutOfSyncError(ev);
00884   }
00885   else map->NewBadMapError(ev);
00886   
00887   return outNext;
00888 }
00889 
00890 mork_change*
00891 morkMapIter::Here(morkEnv* ev, void* outKey, void* outVal)
00892 {
00893   mork_change* outHere = 0;
00894   
00895   morkMap* map = mMapIter_Map;
00896   
00897   if ( map && map->GoodMap() ) /* map looks good? */
00898   {
00899     if ( mMapIter_Seed == map->mMap_Seed ) /* in sync? */
00900     {
00901       morkAssoc* here = mMapIter_Assoc; /* current assoc */
00902       if ( here ) /* iteration is not yet concluded? */
00903       {
00904         mork_pos i = here - map->mMap_Assocs;
00905         mork_change* c = map->mMap_Changes;
00906         outHere = ( c )? (c + i) : map->FormDummyChange();
00907           
00908         map->get_assoc(outKey, outVal, i);
00909       }
00910     }
00911     else map->NewIterOutOfSyncError(ev);
00912   }
00913   else map->NewBadMapError(ev);
00914   
00915   return outHere;
00916 }
00917 
00918 mork_change*
00919 morkMapIter::CutHere(morkEnv* ev, void* outKey, void* outVal)
00920 {
00921   mork_change* outCutHere = 0;
00922   morkMap* map = mMapIter_Map;
00923   
00924   if ( map && map->GoodMap() ) /* map looks good? */
00925   {
00926     if ( mMapIter_Seed == map->mMap_Seed ) /* in sync? */
00927     {
00928       morkAssoc* here = mMapIter_Assoc; /* current assoc */
00929       if ( here ) /* iteration is not yet concluded? */
00930       {
00931         morkAssoc** ref = mMapIter_AssocRef;
00932         if ( *ref != mMapIter_Next ) /* not already cut? */
00933         {
00934           mork_pos i = here - map->mMap_Assocs;
00935           mork_change* c = map->mMap_Changes;
00936           outCutHere = ( c )? (c + i) : map->FormDummyChange();
00937           if ( outKey || outVal )
00938             map->get_assoc(outKey, outVal, i);
00939             
00940           map->push_free_assoc(here); /* add to free list */
00941           *ref = mMapIter_Next; /* unlink here from bucket list */
00942           
00943           /* note the map has changed, but we are still in sync: */
00944           mMapIter_Seed = ++map->mMap_Seed; /* sync */
00945           
00946           if ( map->mMap_Fill ) /* still has nonzero value? */
00947             --map->mMap_Fill; /* one less member in the collection */
00948           else
00949             map->NewSlotsUnderflowWarning(ev);
00950         }
00951       }
00952     }
00953     else map->NewIterOutOfSyncError(ev);
00954   }
00955   else map->NewBadMapError(ev);
00956   
00957   return outCutHere;
00958 }
00959 
00960 //3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789