Issue #1258 - Part 1: Import mailnews, ldap, and mork from comm-esr52.9.1

1 files changed, 953 insertions, 0 deletions

diff --git a/db/mork/src/morkMap.cpp b/db/mork/src/morkMap.cpp
new file mode 100644
index 000000000..ca6b27827
--- /dev/null
+++ b/db/mork/src/morkMap.cpp
@@ -0,0 +1,953 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-  */
+/* ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is mozilla.org code.
+ *
+ * The Initial Developer of the Original Code is
+ * Netscape Communications Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 1999
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either of the GNU General Public License Version 2 or later (the "GPL"),
+ * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+// This code is mostly a port to C++ from public domain IronDoc C sources.
+// Note many code comments here come verbatim from cut-and-pasted IronDoc.
+
+#ifndef _MDB_
+#include "mdb.h"
+#endif
+
+#ifndef _MORK_
+#include "mork.h"
+#endif
+
+#ifndef _MORKNODE_
+#include "morkNode.h"
+#endif
+
+#ifndef _MORKMAP_
+#include "morkMap.h"
+#endif
+
+#ifndef _MORKENV_
+#include "morkEnv.h"
+#endif
+
+
+class morkHashArrays {
+public:
+  nsIMdbHeap*   mHashArrays_Heap;     // copy of mMap_Heap
+  mork_count    mHashArrays_Slots;    // copy of mMap_Slots
+  
+  mork_u1*      mHashArrays_Keys;     // copy of mMap_Keys
+  mork_u1*      mHashArrays_Vals;     // copy of mMap_Vals
+  morkAssoc*    mHashArrays_Assocs;   // copy of mMap_Assocs
+  mork_change*  mHashArrays_Changes;  // copy of mMap_Changes
+  morkAssoc**   mHashArrays_Buckets;  // copy of mMap_Buckets
+  morkAssoc*    mHashArrays_FreeList; // copy of mMap_FreeList
+  
+public:
+  void finalize(morkEnv* ev);
+};
+
+void morkHashArrays::finalize(morkEnv* ev)
+{
+  nsIMdbEnv* menv = ev->AsMdbEnv();
+  nsIMdbHeap* heap = mHashArrays_Heap;
+  
+  if ( heap )
+  {
+    if ( mHashArrays_Keys )
+      heap->Free(menv, mHashArrays_Keys);
+    if ( mHashArrays_Vals )
+      heap->Free(menv, mHashArrays_Vals);
+    if ( mHashArrays_Assocs )
+      heap->Free(menv, mHashArrays_Assocs);
+    if ( mHashArrays_Changes )
+      heap->Free(menv, mHashArrays_Changes);
+    if ( mHashArrays_Buckets )
+      heap->Free(menv, mHashArrays_Buckets);
+  }
+}
+
+//3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789
+
+// ````` ````` ````` ````` ````` 
+// { ===== begin morkNode interface =====
+
+/*public virtual*/ void
+morkMap::CloseMorkNode(morkEnv* ev) // CloseMap() only if open
+{
+  if ( this->IsOpenNode() )
+  {
+    this->MarkClosing();
+    this->CloseMap(ev);
+    this->MarkShut();
+  }
+}
+
+/*public virtual*/
+morkMap::~morkMap() // assert CloseMap() executed earlier
+{
+  MORK_ASSERT(mMap_FreeList==0);
+  MORK_ASSERT(mMap_Buckets==0);
+  MORK_ASSERT(mMap_Keys==0);
+  MORK_ASSERT(mMap_Vals==0);
+  MORK_ASSERT(mMap_Changes==0);
+  MORK_ASSERT(mMap_Assocs==0);
+}
+
+/*public non-poly*/ void
+morkMap::CloseMap(morkEnv* ev) // called by CloseMorkNode();
+{
+    if ( this->IsNode() )
+    {
+      nsIMdbHeap* heap = mMap_Heap;
+      if ( heap ) /* need to free the arrays? */
+      {
+        nsIMdbEnv* menv = ev->AsMdbEnv();
+        
+        if ( mMap_Keys )
+          heap->Free(menv, mMap_Keys);
+          
+        if ( mMap_Vals )
+          heap->Free(menv, mMap_Vals);
+          
+        if ( mMap_Assocs )
+          heap->Free(menv, mMap_Assocs);
+          
+        if ( mMap_Buckets )
+          heap->Free(menv, mMap_Buckets);
+          
+        if ( mMap_Changes )
+          heap->Free(menv, mMap_Changes);
+      }
+      mMap_Keys = 0;
+      mMap_Vals = 0;
+      mMap_Buckets = 0;
+      mMap_Assocs = 0;
+      mMap_Changes = 0;
+      mMap_FreeList = 0;
+      MORK_MEMSET(&mMap_Form, 0, sizeof(morkMapForm));
+      this->MarkShut();
+    }
+    else
+      this->NonNodeError(ev);
+}
+
+// } ===== end morkNode methods =====
+// ````` ````` ````` ````` ````` 
+
+void
+morkMap::clear_map(morkEnv* ev, nsIMdbHeap* ioSlotHeap)
+{
+  mMap_Tag = 0;
+  mMap_Seed = 0;
+  mMap_Slots = 0;
+  mMap_Fill = 0;
+  mMap_Keys = 0;
+  mMap_Vals = 0;
+  mMap_Assocs = 0;
+  mMap_Changes = 0;
+  mMap_Buckets = 0;
+  mMap_FreeList = 0;
+  MORK_MEMSET(&mMap_Form, 0, sizeof(morkMapForm));
+  
+  mMap_Heap = 0;
+  if ( ioSlotHeap )
+  {
+    nsIMdbHeap_SlotStrongHeap(ioSlotHeap, ev, &mMap_Heap);
+  }
+  else
+    ev->NilPointerError();
+}
+
+morkMap::morkMap(morkEnv* ev, const morkUsage& inUsage, nsIMdbHeap* ioHeap, 
+  mork_size inKeySize, mork_size inValSize,
+  mork_size inSlots, nsIMdbHeap* ioSlotHeap, mork_bool inHoldChanges)
+: morkNode(ev, inUsage, ioHeap)
+, mMap_Heap( 0 )
+{
+  if ( ev->Good() )
+  {
+    this->clear_map(ev, ioSlotHeap);
+    if ( ev->Good() )
+    {
+      mMap_Form.mMapForm_HoldChanges = inHoldChanges;
+      
+      mMap_Form.mMapForm_KeySize = inKeySize;
+      mMap_Form.mMapForm_ValSize = inValSize;
+      mMap_Form.mMapForm_KeyIsIP = ( inKeySize == sizeof(mork_ip) );
+      mMap_Form.mMapForm_ValIsIP = ( inValSize == sizeof(mork_ip) );
+      
+      this->InitMap(ev, inSlots);
+      if ( ev->Good() )
+        mNode_Derived = morkDerived_kMap;
+    }
+  }
+}
+
+void
+morkMap::NewIterOutOfSyncError(morkEnv* ev)
+{
+  ev->NewError("map iter out of sync");
+}
+
+void morkMap::NewBadMapError(morkEnv* ev)
+{
+  ev->NewError("bad morkMap tag");
+}
+
+void morkMap::NewSlotsUnderflowWarning(morkEnv* ev)
+{
+  ev->NewWarning("member count underflow");
+}
+
+void morkMap::InitMap(morkEnv* ev, mork_size inSlots)
+{
+  if ( ev->Good() )
+  {
+    morkHashArrays old;
+    // MORK_MEMCPY(&mMap_Form, &inForm, sizeof(morkMapForm));
+    if ( inSlots < 3 ) /* requested capacity absurdly small? */
+      inSlots = 3; /* bump it up to a minimum practical level */
+    else if ( inSlots > (128 * 1024) ) /* requested slots absurdly big? */
+      inSlots = (128 * 1024); /* decrease it to a maximum practical level */
+      
+    if ( this->new_arrays(ev, &old, inSlots) )
+      mMap_Tag = morkMap_kTag;
+
+    MORK_MEMSET(&old, 0, sizeof(morkHashArrays)); // do NOT finalize
+  }
+}
+
+morkAssoc**
+morkMap::find(morkEnv* ev, const void* inKey, mork_u4 inHash) const
+{
+  mork_u1* keys = mMap_Keys;
+  mork_num keySize = this->FormKeySize();
+  // morkMap_mEqual equal = this->FormEqual();
+  
+  morkAssoc** ref = mMap_Buckets + (inHash % mMap_Slots);
+  morkAssoc* assoc = *ref;
+  while ( assoc ) /* look at another assoc in the bucket? */
+  {
+    mork_pos i = assoc - mMap_Assocs; /* index of this assoc */
+    if ( this->Equal(ev, keys + (i * keySize), inKey) ) /* found? */
+      return ref;
+      
+    ref = &assoc->mAssoc_Next; /* consider next assoc slot in bucket */
+    assoc = *ref; /* if this is null, then we are done */
+  }
+  return 0;
+}
+
+/*| get_assoc: read the key and/or value at index inPos
+|*/
+void
+morkMap::get_assoc(void* outKey, void* outVal, mork_pos inPos) const
+{
+  mork_num valSize = this->FormValSize();
+  if ( valSize && outVal ) /* map holds values? caller wants the value? */
+  {
+    const mork_u1* value = mMap_Vals + (valSize * inPos);
+    if ( valSize == sizeof(mork_ip) && this->FormValIsIP() ) /* ip case? */
+      *((mork_ip*) outVal) = *((const mork_ip*) value);
+    else
+      MORK_MEMCPY(outVal, value, valSize);
+  }
+  if ( outKey ) /* caller wants the key? */
+  {
+    mork_num keySize = this->FormKeySize();
+    const mork_u1* key = mMap_Keys + (keySize * inPos);
+    if ( keySize == sizeof(mork_ip) && this->FormKeyIsIP() ) /* ip case? */
+      *((mork_ip*) outKey) = *((const mork_ip*) key);
+    else
+      MORK_MEMCPY(outKey, key, keySize);
+  }
+}
+
+/*| put_assoc: write the key and/or value at index inPos
+|*/
+void
+morkMap::put_assoc(const void* inKey, const void* inVal, mork_pos inPos) const
+{
+  mork_num valSize = this->FormValSize();
+  if ( valSize && inVal ) /* map holds values? caller sends a value? */
+  {
+    mork_u1* value = mMap_Vals + (valSize * inPos);
+    if ( valSize == sizeof(mork_ip) && this->FormValIsIP() ) /* ip case? */
+      *((mork_ip*) value) = *((const mork_ip*) inVal);
+    else
+      MORK_MEMCPY(value, inVal, valSize);
+  }
+  if ( inKey ) /* caller sends a key? */
+  {
+    mork_num keySize = this->FormKeySize();
+    mork_u1* key = mMap_Keys + (keySize * inPos);
+    if ( keySize == sizeof(mork_ip) && this->FormKeyIsIP() ) /* ip case? */
+      *((mork_ip*) key) = *((const mork_ip*) inKey);
+    else
+      MORK_MEMCPY(key, inKey, keySize);
+  }
+}
+
+void*
+morkMap::clear_alloc(morkEnv* ev, mork_size inSize)
+{
+  void* p = 0;
+  nsIMdbHeap* heap = mMap_Heap;
+  if ( heap )
+  {
+    if (NS_SUCCEEDED(heap->Alloc(ev->AsMdbEnv(), inSize, (void**) &p)) && p )
+    {
+      MORK_MEMSET(p, 0, inSize);
+      return p;
+    }
+  }
+  else
+    ev->NilPointerError();
+    
+  return (void*) 0;
+}
+
+void*
+morkMap::alloc(morkEnv* ev, mork_size inSize)
+{
+  void* p = 0;
+  nsIMdbHeap* heap = mMap_Heap;
+  if ( heap )
+  {
+    if (NS_SUCCEEDED(heap->Alloc(ev->AsMdbEnv(), inSize, (void**) &p)) && p )
+      return p;
+  }
+  else
+    ev->NilPointerError();
+
+  return (void*) 0;
+}
+
+/*| new_keys: allocate an array of inSlots new keys filled with zero.
+|*/
+mork_u1*
+morkMap::new_keys(morkEnv* ev, mork_num inSlots)
+{
+  mork_num size = inSlots * this->FormKeySize();
+  return (mork_u1*) this->clear_alloc(ev, size);
+}
+
+/*| new_values: allocate an array of inSlots new values filled with zero.
+**| When values are zero sized, we just return a null pointer.
+|*/
+mork_u1*
+morkMap::new_values(morkEnv* ev, mork_num inSlots)
+{
+  mork_u1* values = 0;
+  mork_num size = inSlots * this->FormValSize();
+  if ( size )
+    values = (mork_u1*) this->clear_alloc(ev, size);
+  return values;
+}
+
+mork_change*
+morkMap::new_changes(morkEnv* ev, mork_num inSlots)
+{
+  mork_change* changes = 0;
+  mork_num size = inSlots * sizeof(mork_change);
+  if ( size && mMap_Form.mMapForm_HoldChanges )
+    changes = (mork_change*) this->clear_alloc(ev, size);
+  return changes;
+}
+
+/*| new_buckets: allocate an array of inSlots new buckets filled with zero.
+|*/
+morkAssoc**
+morkMap::new_buckets(morkEnv* ev, mork_num inSlots)
+{
+  mork_num size = inSlots * sizeof(morkAssoc*);
+  return (morkAssoc**) this->clear_alloc(ev, size);
+}
+
+/*| new_assocs: allocate an array of inSlots new assocs, with each assoc
+**| linked together in a list with the first array element at the list head
+**| and the last element at the list tail. (morkMap::grow() needs this.)
+|*/
+morkAssoc*
+morkMap::new_assocs(morkEnv* ev, mork_num inSlots)
+{
+  mork_num size = inSlots * sizeof(morkAssoc);
+  morkAssoc* assocs = (morkAssoc*) this->alloc(ev, size);
+  if ( assocs ) /* able to allocate the array? */
+  {
+    morkAssoc* a = assocs + (inSlots - 1); /* the last array element */
+    a->mAssoc_Next = 0; /* terminate tail element of the list with null */
+    while ( --a >= assocs ) /* another assoc to link into the list? */
+      a->mAssoc_Next = a + 1; /* each points to the following assoc */
+  }
+  return assocs;
+}
+
+mork_bool
+morkMap::new_arrays(morkEnv* ev, morkHashArrays* old, mork_num inSlots)
+{
+  mork_bool outNew = morkBool_kFalse;
+    
+  /* see if we can allocate all the new arrays before we go any further: */
+  morkAssoc** newBuckets = this->new_buckets(ev, inSlots);
+  morkAssoc* newAssocs = this->new_assocs(ev, inSlots);
+  mork_u1* newKeys = this->new_keys(ev, inSlots);
+  mork_u1* newValues = this->new_values(ev, inSlots);
+  mork_change* newChanges = this->new_changes(ev, inSlots);
+  
+  /* it is okay for newChanges to be null when changes are not held: */
+  mork_bool okayChanges = ( newChanges || !this->FormHoldChanges() );
+  
+  /* it is okay for newValues to be null when values are zero sized: */
+  mork_bool okayValues = ( newValues || !this->FormValSize() );
+  
+  if ( newBuckets && newAssocs && newKeys && okayChanges && okayValues )
+  {
+    outNew = morkBool_kTrue; /* yes, we created all the arrays we need */
+
+    /* init the old hashArrays with slots from this hash table: */
+    old->mHashArrays_Heap = mMap_Heap;
+    
+    old->mHashArrays_Slots = mMap_Slots;
+    old->mHashArrays_Keys = mMap_Keys;
+    old->mHashArrays_Vals = mMap_Vals;
+    old->mHashArrays_Assocs = mMap_Assocs;
+    old->mHashArrays_Buckets = mMap_Buckets;
+    old->mHashArrays_Changes = mMap_Changes;
+    
+    /* now replace all our array slots with the new structures: */
+    ++mMap_Seed; /* note the map is now changed */
+    mMap_Keys = newKeys;
+    mMap_Vals = newValues;
+    mMap_Buckets = newBuckets;
+    mMap_Assocs = newAssocs;
+    mMap_FreeList = newAssocs; /* all are free to start with */
+    mMap_Changes = newChanges;
+    mMap_Slots = inSlots;
+  }
+  else /* free the partial set of arrays that were actually allocated */
+  {
+    nsIMdbEnv* menv = ev->AsMdbEnv();
+    nsIMdbHeap* heap = mMap_Heap;
+    if ( newBuckets )
+      heap->Free(menv, newBuckets);
+    if ( newAssocs )
+      heap->Free(menv, newAssocs);
+    if ( newKeys )
+      heap->Free(menv, newKeys);
+    if ( newValues )
+      heap->Free(menv, newValues);
+    if ( newChanges )
+      heap->Free(menv, newChanges);
+    
+    MORK_MEMSET(old, 0, sizeof(morkHashArrays));
+  }
+  
+  return outNew;
+}
+
+/*| grow: make the map arrays bigger by 33%.  The old map is completely
+**| full, or else we would not have called grow() to get more space.  This
+**| means the free list is empty, and also means every old key and value is in
+**| use in the old arrays.  So every key and value must be copied to the new
+**| arrays, and since they are contiguous in the old arrays, we can efficiently
+**| bitwise copy them in bulk from the old arrays to the new arrays, without
+**| paying any attention to the structure of the old arrays.
+**|
+**|| The content of the old bucket and assoc arrays need not be copied because
+**| this information is going to be completely rebuilt by rehashing all the
+**| keys into their new buckets, given the new larger map capacity.  The new
+**| bucket array from new_arrays() is assumed to contain all zeroes, which is
+**| necessary to ensure the lists in each bucket stay null terminated as we
+**| build the new linked lists.  (Note no old bucket ordering is preserved.)
+**|
+**|| If the old capacity is N, then in the new arrays the assocs with indexes
+**| from zero to N-1 are still allocated and must be rehashed into the map.
+**| The new free list contains all the following assocs, starting with the new
+**| assoc link at index N.  (We call the links in the link array "assocs"
+**| because allocating a link is the same as allocating the key/value pair
+**| with the same index as the link.)
+**|
+**|| The new free list is initialized simply by pointing at the first new link
+**| in the assoc array after the size of the old assoc array.  This assumes
+**| that FeHashTable_new_arrays() has already linked all the new assocs into a
+**| list with the first at the head of the list and the last at the tail of the
+**| list.  So by making the free list point to the first of the new uncopied
+**| assocs, the list is already well-formed.
+|*/
+mork_bool morkMap::grow(morkEnv* ev)
+{
+  if ( mMap_Heap ) /* can we grow the map? */
+  {
+    mork_num newSlots = (mMap_Slots * 2); /* +100% */
+    morkHashArrays old; /* a place to temporarily hold all the old arrays */
+    if ( this->new_arrays(ev, &old, newSlots) ) /* have more? */
+    {
+      // morkMap_mHash hash = this->FormHash(); /* for terse loop use */
+      
+      /* figure out the bulk volume sizes of old keys and values to move: */
+      mork_num oldSlots = old.mHashArrays_Slots; /* number of old assocs */
+      mork_num keyBulk = oldSlots * this->FormKeySize(); /* key volume */
+      mork_num valBulk = oldSlots * this->FormValSize(); /* values */
+      
+      /* convenient variables for new arrays that need to be rehashed: */
+      morkAssoc** newBuckets = mMap_Buckets; /* new all zeroes */
+      morkAssoc* newAssocs = mMap_Assocs; /* hash into buckets */
+      morkAssoc* newFreeList = newAssocs + oldSlots; /* new room is free */
+      mork_u1* key = mMap_Keys; /* the first key to rehash */
+      --newAssocs; /* back up one before preincrement used in while loop */
+      
+      /* move all old keys and values to the new arrays: */
+      MORK_MEMCPY(mMap_Keys, old.mHashArrays_Keys, keyBulk);
+      if ( valBulk ) /* are values nonzero sized? */
+        MORK_MEMCPY(mMap_Vals, old.mHashArrays_Vals, valBulk);
+        
+      mMap_FreeList = newFreeList; /* remaining assocs are free */
+      
+      while ( ++newAssocs < newFreeList ) /* rehash another old assoc? */
+      {
+        morkAssoc** top = newBuckets + (this->Hash(ev, key) % newSlots);
+        key += this->FormKeySize(); /* the next key to rehash */
+        newAssocs->mAssoc_Next = *top; /* link to prev bucket top */
+        *top = newAssocs; /* push assoc on top of bucket */
+      }
+      ++mMap_Seed; /* note the map has changed */
+      old.finalize(ev); /* remember to free the old arrays */
+    }
+  }
+  else ev->OutOfMemoryError();
+  
+  return ev->Good();
+}
+
+
+mork_bool
+morkMap::Put(morkEnv* ev, const void* inKey, const void* inVal,
+  void* outKey, void* outVal, mork_change** outChange)
+{
+  mork_bool outPut = morkBool_kFalse;
+  
+  if ( this->GoodMap() ) /* looks good? */
+  {
+    mork_u4 hash = this->Hash(ev, inKey);
+    morkAssoc** ref = this->find(ev, inKey, hash);
+    if ( ref ) /* assoc was found? reuse an existing assoc slot? */
+    {
+      outPut = morkBool_kTrue; /* inKey was indeed already inside the map */
+    }
+    else /* assoc not found -- need to allocate a new assoc slot */
+    {
+      morkAssoc* assoc = this->pop_free_assoc();
+      if ( !assoc ) /* no slots remaining in free list? must grow map? */
+      {
+        if ( this->grow(ev) ) /* successfully made map larger? */
+          assoc = this->pop_free_assoc();
+      }
+      if ( assoc ) /* allocated new assoc without error? */
+      {
+        ref = mMap_Buckets + (hash % mMap_Slots);
+        assoc->mAssoc_Next = *ref; /* link to prev bucket top */
+        *ref = assoc; /* push assoc on top of bucket */
+          
+        ++mMap_Fill; /* one more member in the collection */
+        ++mMap_Seed; /* note the map has changed */
+      }
+    }
+    if ( ref ) /* did not have an error during possible growth? */
+    {
+      mork_pos i = (*ref) - mMap_Assocs; /* index of assoc */
+      if ( outPut && (outKey || outVal) ) /* copy old before cobbering? */
+        this->get_assoc(outKey, outVal, i);
+
+      this->put_assoc(inKey, inVal, i);
+      ++mMap_Seed; /* note the map has changed */
+      
+      if ( outChange )
+      {
+        if ( mMap_Changes )
+          *outChange = mMap_Changes + i;
+        else
+          *outChange = this->FormDummyChange();
+      }
+    }
+  }
+  else this->NewBadMapError(ev);
+  
+  return outPut;
+}
+
+mork_num
+morkMap::CutAll(morkEnv* ev)
+{
+  mork_num outCutAll = 0;
+  
+  if ( this->GoodMap() ) /* map looks good? */
+  {
+    mork_num slots = mMap_Slots;
+    morkAssoc* before = mMap_Assocs - 1; /* before first member */
+    morkAssoc* assoc = before + slots; /* the very last member */
+
+    ++mMap_Seed; /* note the map is changed */
+
+    /* make the assoc array a linked list headed by first & tailed by last: */
+    assoc->mAssoc_Next = 0; /* null terminate the new free list */
+    while ( --assoc > before ) /* another assoc to link into the list? */
+      assoc->mAssoc_Next = assoc + 1;
+    mMap_FreeList = mMap_Assocs; /* all are free */
+
+    outCutAll = mMap_Fill; /* we'll cut all of them of course */
+
+    mMap_Fill = 0; /* the map is completely empty */
+  }
+  else this->NewBadMapError(ev);
+  
+  return outCutAll;
+}
+
+mork_bool
+morkMap::Cut(morkEnv* ev, const void* inKey,
+  void* outKey, void* outVal, mork_change** outChange)
+{
+  mork_bool outCut = morkBool_kFalse;
+  
+  if ( this->GoodMap() ) /* looks good? */
+  {
+    mork_u4 hash = this->Hash(ev, inKey);
+    morkAssoc** ref = this->find(ev, inKey, hash);
+    if ( ref ) /* found an assoc for key? */
+    {
+      outCut = morkBool_kTrue;
+      morkAssoc* assoc = *ref;
+      mork_pos i = assoc - mMap_Assocs; /* index of assoc */
+      if ( outKey || outVal )
+        this->get_assoc(outKey, outVal, i);
+
+      *ref = assoc->mAssoc_Next; /* unlink the found assoc */
+      this->push_free_assoc(assoc); /* and put it in free list */
+
+      if ( outChange )
+      {
+        if ( mMap_Changes )
+          *outChange = mMap_Changes + i;
+        else
+          *outChange = this->FormDummyChange();
+      }
+      
+      ++mMap_Seed; /* note the map has changed */
+      if ( mMap_Fill ) /* the count shows nonzero members? */
+        --mMap_Fill; /* one less member in the collection */
+      else
+        this->NewSlotsUnderflowWarning(ev);
+    }
+  }
+  else this->NewBadMapError(ev);
+  
+  return outCut;
+}
+
+mork_bool
+morkMap::Get(morkEnv* ev, const void* inKey,
+  void* outKey, void* outVal, mork_change** outChange)
+{
+  mork_bool outGet = morkBool_kFalse;
+  
+  if ( this->GoodMap() ) /* looks good? */
+  {
+    mork_u4 hash = this->Hash(ev, inKey);
+    morkAssoc** ref = this->find(ev, inKey, hash);
+    if ( ref ) /* found an assoc for inKey? */
+    {
+      mork_pos i = (*ref) - mMap_Assocs; /* index of assoc */
+      outGet = morkBool_kTrue;
+      this->get_assoc(outKey, outVal, i);
+      if ( outChange )
+      {
+        if ( mMap_Changes )
+          *outChange = mMap_Changes + i;
+        else
+          *outChange = this->FormDummyChange();
+      }
+    }
+  }
+  else this->NewBadMapError(ev);
+  
+  return outGet;
+}
+
+
+morkMapIter::morkMapIter( )
+: mMapIter_Map( 0 )
+, mMapIter_Seed( 0 )
+  
+, mMapIter_Bucket( 0 )
+, mMapIter_AssocRef( 0 )
+, mMapIter_Assoc( 0 )
+, mMapIter_Next( 0 )
+{
+}
+
+void
+morkMapIter::InitMapIter(morkEnv* ev, morkMap* ioMap)
+{
+  mMapIter_Map = 0;
+  mMapIter_Seed = 0;
+
+  mMapIter_Bucket = 0;
+  mMapIter_AssocRef = 0;
+  mMapIter_Assoc = 0;
+  mMapIter_Next = 0;
+
+  if ( ioMap )
+  {
+    if ( ioMap->GoodMap() )
+    {
+      mMapIter_Map = ioMap;
+      mMapIter_Seed = ioMap->mMap_Seed;
+    }
+    else ioMap->NewBadMapError(ev);
+  }
+  else ev->NilPointerError();
+}
+
+morkMapIter::morkMapIter(morkEnv* ev, morkMap* ioMap)
+: mMapIter_Map( 0 )
+, mMapIter_Seed( 0 )
+  
+, mMapIter_Bucket( 0 )
+, mMapIter_AssocRef( 0 )
+, mMapIter_Assoc( 0 )
+, mMapIter_Next( 0 )
+{
+  if ( ioMap )
+  {
+    if ( ioMap->GoodMap() )
+    {
+      mMapIter_Map = ioMap;
+      mMapIter_Seed = ioMap->mMap_Seed;
+    }
+    else ioMap->NewBadMapError(ev);
+  }
+  else ev->NilPointerError();
+}
+
+void
+morkMapIter::CloseMapIter(morkEnv* ev)
+{
+  MORK_USED_1(ev);
+  mMapIter_Map = 0;
+  mMapIter_Seed = 0;
+  
+  mMapIter_Bucket = 0;
+  mMapIter_AssocRef = 0;
+  mMapIter_Assoc = 0;
+  mMapIter_Next = 0;
+}
+
+mork_change*
+morkMapIter::First(morkEnv* ev, void* outKey, void* outVal)
+{
+  mork_change* outFirst = 0;
+  
+  morkMap* map = mMapIter_Map;
+  
+  if ( map && map->GoodMap() ) /* map looks good? */
+  {
+    morkAssoc** bucket = map->mMap_Buckets;
+    morkAssoc** end = bucket + map->mMap_Slots; /* one past last */
+ 
+    mMapIter_Seed = map->mMap_Seed; /* sync the seeds */
+   
+    while ( bucket < end ) /* another bucket in which to look for assocs? */
+    {
+      morkAssoc* assoc = *bucket++;
+      if ( assoc ) /* found the first map assoc in use? */
+      {
+        mork_pos i = assoc - map->mMap_Assocs;
+        mork_change* c = map->mMap_Changes;
+        outFirst = ( c )? (c + i) : map->FormDummyChange();
+        
+        mMapIter_Assoc = assoc; /* current assoc in iteration */
+        mMapIter_Next = assoc->mAssoc_Next; /* more in bucket */
+        mMapIter_Bucket = --bucket; /* bucket for this assoc */
+        mMapIter_AssocRef = bucket; /* slot referencing assoc */
+        
+        map->get_assoc(outKey, outVal, i);
+          
+        break; /* end while loop */
+      }
+    }
+  }
+  else map->NewBadMapError(ev);
+
+  return outFirst;
+}
+
+mork_change*
+morkMapIter::Next(morkEnv* ev, void* outKey, void* outVal)
+{
+  mork_change* outNext = 0;
+  
+  morkMap* map = mMapIter_Map;
+  
+  if ( map && map->GoodMap() ) /* map looks good? */
+  {
+    if ( mMapIter_Seed == map->mMap_Seed ) /* in sync? */
+    {
+      morkAssoc* here = mMapIter_Assoc; /* current assoc */
+      if ( here ) /* iteration is not yet concluded? */
+      {
+        morkAssoc* next = mMapIter_Next;
+        morkAssoc* assoc = next; /* default new mMapIter_Assoc */  
+        if ( next ) /* there are more assocs in the same bucket after Here? */
+        {
+          morkAssoc** ref = mMapIter_AssocRef;
+          
+          /* (*HereRef) equals Here, except when Here has been cut, after
+          ** which (*HereRef) always equals Next.  So if (*HereRef) is not
+          ** equal to Next, then HereRef still needs to be updated to point
+          ** somewhere else other than Here.  Otherwise it is fine.
+          */
+          if ( *ref != next ) /* Here was not cut? must update HereRef? */
+            mMapIter_AssocRef = &here->mAssoc_Next;
+            
+          mMapIter_Next = next->mAssoc_Next;
+        }
+        else /* look for the next assoc in the next nonempty bucket */
+        {
+          morkAssoc** bucket = map->mMap_Buckets;
+          morkAssoc** end = bucket + map->mMap_Slots; /* beyond */
+          mMapIter_Assoc = 0; /* default to no more assocs */
+          bucket = mMapIter_Bucket; /* last exhausted bucket */
+          mMapIter_Assoc = 0; /* default to iteration ended */
+          
+          while ( ++bucket < end ) /* another bucket to search for assocs? */
+          {
+            assoc = *bucket;
+            if ( assoc ) /* found another map assoc in use? */
+            {
+              mMapIter_Bucket = bucket;
+              mMapIter_AssocRef = bucket; /* ref to assoc */
+              mMapIter_Next = assoc->mAssoc_Next; /* more */
+              
+              break; /* end while loop */
+            }
+          }
+        }
+        if ( assoc ) /* did we find another assoc in the iteration? */
+        {
+          mMapIter_Assoc = assoc; /* current assoc */
+          mork_pos i = assoc - map->mMap_Assocs;
+          mork_change* c = map->mMap_Changes;
+          outNext = ( c )? (c + i) : map->FormDummyChange();
+        
+          map->get_assoc( outKey, outVal, i);
+        }
+      }
+    }
+    else map->NewIterOutOfSyncError(ev);
+  }
+  else map->NewBadMapError(ev);
+  
+  return outNext;
+}
+
+mork_change*
+morkMapIter::Here(morkEnv* ev, void* outKey, void* outVal)
+{
+  mork_change* outHere = 0;
+  
+  morkMap* map = mMapIter_Map;
+  
+  if ( map && map->GoodMap() ) /* map looks good? */
+  {
+    if ( mMapIter_Seed == map->mMap_Seed ) /* in sync? */
+    {
+      morkAssoc* here = mMapIter_Assoc; /* current assoc */
+      if ( here ) /* iteration is not yet concluded? */
+      {
+        mork_pos i = here - map->mMap_Assocs;
+        mork_change* c = map->mMap_Changes;
+        outHere = ( c )? (c + i) : map->FormDummyChange();
+          
+        map->get_assoc(outKey, outVal, i);
+      }
+    }
+    else map->NewIterOutOfSyncError(ev);
+  }
+  else map->NewBadMapError(ev);
+  
+  return outHere;
+}
+
+mork_change*
+morkMapIter::CutHere(morkEnv* ev, void* outKey, void* outVal)
+{
+  mork_change* outCutHere = 0;
+  morkMap* map = mMapIter_Map;
+  
+  if ( map && map->GoodMap() ) /* map looks good? */
+  {
+    if ( mMapIter_Seed == map->mMap_Seed ) /* in sync? */
+    {
+      morkAssoc* here = mMapIter_Assoc; /* current assoc */
+      if ( here ) /* iteration is not yet concluded? */
+      {
+        morkAssoc** ref = mMapIter_AssocRef;
+        if ( *ref != mMapIter_Next ) /* not already cut? */
+        {
+          mork_pos i = here - map->mMap_Assocs;
+          mork_change* c = map->mMap_Changes;
+          outCutHere = ( c )? (c + i) : map->FormDummyChange();
+          if ( outKey || outVal )
+            map->get_assoc(outKey, outVal, i);
+            
+          map->push_free_assoc(here); /* add to free list */
+          *ref = mMapIter_Next; /* unlink here from bucket list */
+          
+          /* note the map has changed, but we are still in sync: */
+          mMapIter_Seed = ++map->mMap_Seed; /* sync */
+          
+          if ( map->mMap_Fill ) /* still has nonzero value? */
+            --map->mMap_Fill; /* one less member in the collection */
+          else
+            map->NewSlotsUnderflowWarning(ev);
+        }
+      }
+    }
+    else map->NewIterOutOfSyncError(ev);
+  }
+  else map->NewBadMapError(ev);
+  
+  return outCutHere;
+}
+
+//3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789