summaryrefslogtreecommitdiff
path: root/db/mork/src/morkMap.h
blob: 57104df0e3eab30b547bfa90a7486183b2e9c96b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
/* -*- 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 ***** */

#ifndef _MORKMAP_
#define _MORKMAP_ 1

#ifndef _MORK_
#include "mork.h"
#endif

#ifndef _MORKNODE_
#include "morkNode.h"
#endif

//3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789

/* (These hash methods closely resemble those in public domain IronDoc.) */

/*| Equal: equal for hash table. Note equal(a,b) implies hash(a)==hash(b).
|*/
typedef mork_bool (* morkMap_mEqual)
(const morkMap* self, morkEnv* ev, const void* inKeyA, const void* inKeyB);

/*| Hash: hash for hash table. Note equal(a,b) implies hash(a)==hash(b).
|*/
typedef mork_u4 (* morkMap_mHash)
(const morkMap* self, morkEnv* ev, const void* inKey);

/*| IsNil: whether a key slot contains a "null" value denoting "no such key".
|*/
typedef mork_bool (* morkMap_mIsNil)
(const morkMap* self, morkEnv* ev, const void* inKey);

/*| Note: notify regarding a refcounting change for a key or a value.
|*/
//typedef void (* morkMap_mNote)
//(morkMap* self, morkEnv* ev, void* inKeyOrVal);

/*| morkMapForm: slots need to initialize a new dict.  (This is very similar
**| to the config object for public domain IronDoc hash tables.)
|*/
class morkMapForm { // a struct of callback method pointers for morkMap
public:
  
  // const void*     mMapForm_NilKey;  // externally defined 'nil' bit pattern

  // void*           mMapForm_NilBuf[ 8 ]; // potential place to put NilKey
  // If keys are no larger than 8*sizeof(void*), NilKey can be put in NilBuf.
  // Note this should be true for all Mork subclasses, and we plan usage so.
  
  // These three methods must always be provided, so zero will cause errors:
  
  // morkMap_mEqual  mMapForm_Equal;   // for comparing two keys for identity
  // morkMap_mHash   mMapForm_Hash;    // deterministic key to hash method
  // morkMap_mIsNil  mMapForm_IsNil;   // to query whether a key equals 'nil'
  
  // If any of these method slots are nonzero, then morkMap will call the
  // appropriate one to notify dict users when a key or value is added or cut.
  // Presumably a caller wants to know this in order to perform refcounting or
  // some other kind of memory management.  These methods are definitely only
  // called when references to keys or values are inserted or removed, and are
  // never called when the actual number of references does not change (such
  // as when added keys are already present or cut keys are alreading missing).
  // 
  // morkMap_mNote   mMapForm_AddKey;  // if nonzero, notify about add key
  // morkMap_mNote   mMapForm_CutKey;  // if nonzero, notify about cut key
  // morkMap_mNote   mMapForm_AddVal;  // if nonzero, notify about add val
  // morkMap_mNote   mMapForm_CutVal;  // if nonzero, notify about cut val
  //
  // These note methods have been removed because it seems difficult to
  // guarantee suitable alignment of objects passed to notification methods.
  
  // Note dict clients should pick key and val sizes that provide whatever
  // alignment will be required for an array of such keys and values.
  mork_size       mMapForm_KeySize; // size of every key (cannot be zero)
  mork_size       mMapForm_ValSize; // size of every val (can indeed be zero)
  
  mork_bool       mMapForm_HoldChanges; // support changes array in the map
  mork_change     mMapForm_DummyChange; // change used for false HoldChanges
  mork_bool       mMapForm_KeyIsIP;     // key is mork_ip sized
  mork_bool       mMapForm_ValIsIP;     // key is mork_ip sized
};

/*| morkAssoc: a canonical association slot in a morkMap.  A single assoc
**| instance does nothing except point to the next assoc in the same bucket
**| of a hash table.  Each assoc has only two interesting attributes: 1) the
**| address of the assoc, and 2) the next assoc in a bucket's list.  The assoc
**| address is interesting because in the context of an array of such assocs,
**| one can determine the index of a particular assoc in the array by address
**| arithmetic, subtracting the array address from the assoc address.  And the
**| index of each assoc is the same index as the associated key and val slots
**| in the associated arrays
**|
**|| Think of an assoc instance as really also containing a key slot and a val
**| slot, where each key is mMap_Form.mMapForm_KeySize bytes in size, and
**| each val is mMap_Form.mMapForm_ValSize in size.  But the key and val
**| slots are stored in separate arrays with indexes that are parallel to the
**| indexes in the array of morkAssoc instances.  We have taken the variable
**| sized slots out of the morkAssoc structure, and put them into parallel
**| arrays associated with each morkAssoc by array index.  And this leaves us
**| with only the link field to the next assoc in each assoc instance.
|*/
class morkAssoc {
public:
  morkAssoc*   mAssoc_Next;
};


#define morkDerived_kMap     /*i*/ 0x4D70 /* ascii 'Mp' */

#define morkMap_kTag     /*i*/ 0x6D4D6150 /* ascii 'mMaP' */

/*| morkMap: a hash table based on the public domain IronDoc hash table
**| (which is in turn rather like a similar OpenDoc hash table).
|*/
class morkMap : public morkNode {

// public: // slots inherited from morkNode (meant to inform only)
  // nsIMdbHeap*       mNode_Heap;

  // mork_base      mNode_Base;     // must equal morkBase_kNode
  // mork_derived   mNode_Derived;  // depends on specific node subclass
  
  // mork_access    mNode_Access;   // kOpen, kClosing, kShut, or kDead
  // mork_usage     mNode_Usage;    // kHeap, kStack, kMember, kGlobal, kNone
  // mork_able      mNode_Mutable;  // can this node be modified?
  // mork_load      mNode_Load;     // is this node clean or dirty?
  
  // mork_uses      mNode_Uses;     // refcount for strong refs
  // mork_refs      mNode_Refs;     // refcount for strong refs + weak refs

public: // state is public because the entire Mork system is private

  nsIMdbHeap*       mMap_Heap; // strong ref to heap allocating all space
  mork_u4           mMap_Tag; // must equal morkMap_kTag

  // When a morkMap instance is constructed, the dict form slots must be
  // provided in order to properly configure a dict with all runtime needs:
  
  morkMapForm       mMap_Form; // construction time parameterization
  
  // Whenever the dict changes structure in a way that would affect any
  // iteration of the dict associations, the seed increments to show this:
  
  mork_seed         mMap_Seed;   // counter for member and structural changes
  
  // The current total assoc capacity of the dict is mMap_Slots, where
  // mMap_Fill of these slots are actually holding content, so mMap_Fill
  // is the actual membership count, and mMap_Slots is how larger membership
  // can become before the hash table must grow the buffers being used. 
  
  mork_count        mMap_Slots;  // count of slots in the hash table
  mork_fill         mMap_Fill;   // number of used slots in the hash table
  
  // Key and value slots are bound to corresponding mMap_Assocs array slots.
  // Instead of having a single array like this: {key,val,next}[ mMap_Slots ]
  // we have instead three parallel arrays with essentially the same meaning:
  // {key}[ mMap_Slots ], {val}[ mMap_Slots ], {assocs}[ mMap_Slots ]
  
  mork_u1*          mMap_Keys;  // mMap_Slots * mMapForm_KeySize buffer
  mork_u1*          mMap_Vals;  // mMap_Slots * mMapForm_ValSize buffer

  // An assoc is "used" when it appears in a bucket's linked list of assocs.
  // Until an assoc is used, it appears in the FreeList linked list.  Every
  // assoc that becomes used goes into the bucket determined by hashing the
  // key associated with a new assoc.  The key associated with a new assoc
  // goes in to the slot in mMap_Keys which occupies exactly the same array
  // index as the array index of the used assoc in the mMap_Assocs array.
  
  morkAssoc*        mMap_Assocs;   // mMap_Slots * sizeof(morkAssoc) buffer
  
  // The changes array is only needed when the

  mork_change*      mMap_Changes;  // mMap_Slots * sizeof(mork_change) buffer
  
  // The Buckets array need not be the same length as the Assocs array, but we
  // usually do it that way so the average bucket depth is no more than one.
  // (We could pick a different policy, or make it parameterizable, but that's
  // tuning we can do some other time.)
  
  morkAssoc**       mMap_Buckets;  // mMap_Slots * sizeof(morkAssoc*) buffer
  
  // The length of the mMap_FreeList should equal (mMap_Slots - mMap_Fill).
  // We need a free list instead of a simpler representation because assocs
  // can be cut and returned to availability in any kind of unknown pattern.
  // (However, when assocs are first allocated, or when the dict is grown, we
  // know all new assocs are contiguous and can chain together adjacently.)
  
  morkAssoc*        mMap_FreeList; // list of unused mMap_Assocs array slots 

public: // getters (morkProbeMap compatibility)
  mork_fill        MapFill() const { return mMap_Fill; }
  
// { ===== begin morkNode interface =====
public: // morkNode virtual methods
  virtual void CloseMorkNode(morkEnv* ev) override; // CloseMap() only if open
  virtual ~morkMap(); // assert that CloseMap() executed earlier
  
public: // morkMap construction & destruction
  morkMap(morkEnv* ev, const morkUsage& inUsage, nsIMdbHeap* ioNodeHeap, 
    mork_size inKeySize, mork_size inValSize,
    mork_size inSlots, nsIMdbHeap* ioSlotHeap, mork_bool inHoldChanges);
  
  void CloseMap(morkEnv* ev); // called by 
  
public: // dynamic type identification
  mork_bool IsMap() const
  { return IsNode() && mNode_Derived == morkDerived_kMap; }
// } ===== end morkNode methods =====

public: // poly map hash table methods

// { ===== begin morkMap poly interface =====
  virtual mork_bool // note: equal(a,b) implies hash(a) == hash(b)
  Equal(morkEnv* ev, const void* inKeyA, const void* inKeyB) const = 0;

  virtual mork_u4 // note: equal(a,b) implies hash(a) == hash(b)
  Hash(morkEnv* ev, const void* inKey) const = 0;
// } ===== end morkMap poly interface =====

public: // open utitity methods

  mork_bool GoodMapTag() const { return mMap_Tag == morkMap_kTag; }
  mork_bool GoodMap() const
  { return ( IsNode() && GoodMapTag() ); }
  
  void NewIterOutOfSyncError(morkEnv* ev);
  void NewBadMapError(morkEnv* ev);
  void NewSlotsUnderflowWarning(morkEnv* ev);
  void InitMap(morkEnv* ev, mork_size inSlots);

protected: // internal utitity methods

  friend class morkMapIter;
  void clear_map(morkEnv* ev, nsIMdbHeap* ioHeap);

  void* alloc(morkEnv* ev, mork_size inSize);
  void* clear_alloc(morkEnv* ev, mork_size inSize);
  
  void push_free_assoc(morkAssoc* ioAssoc)
  {
    ioAssoc->mAssoc_Next = mMap_FreeList;
    mMap_FreeList = ioAssoc;
  }
  
  morkAssoc* pop_free_assoc()
  {
    morkAssoc* assoc = mMap_FreeList;
    if ( assoc )
      mMap_FreeList = assoc->mAssoc_Next;
    return assoc;
  }

  morkAssoc** find(morkEnv* ev, const void* inKey, mork_u4 inHash) const;
  
  mork_u1* new_keys(morkEnv* ev, mork_num inSlots);
  mork_u1* new_values(morkEnv* ev, mork_num inSlots);
  mork_change* new_changes(morkEnv* ev, mork_num inSlots);
  morkAssoc** new_buckets(morkEnv* ev, mork_num inSlots);
  morkAssoc* new_assocs(morkEnv* ev, mork_num inSlots);
  mork_bool new_arrays(morkEnv* ev, morkHashArrays* old, mork_num inSlots);
  
  mork_bool grow(morkEnv* ev);

  void get_assoc(void* outKey, void* outVal, mork_pos inPos) const;
  void put_assoc(const void* inKey, const void* inVal, mork_pos inPos) const;
  
public: // inlines to form slots
  // const void*     FormNilKey() const { return mMap_Form.mMapForm_NilKey; }
  
  // morkMap_mEqual  FormEqual() const { return mMap_Form.mMapForm_Equal; }
  // morkMap_mHash   FormHash() const { return mMap_Form.mMapForm_Hash; }
  // orkMap_mIsNil  FormIsNil() const { return mMap_Form.mMapForm_IsNil; } 
    
  // morkMap_mNote   FormAddKey() const { return mMap_Form.mMapForm_AddKey; }
  // morkMap_mNote   FormCutKey() const { return mMap_Form.mMapForm_CutKey; }
  // morkMap_mNote   FormAddVal() const { return mMap_Form.mMapForm_AddVal; }
  // morkMap_mNote   FormCutVal() const { return mMap_Form.mMapForm_CutVal; }
  
  mork_size       FormKeySize() const { return mMap_Form.mMapForm_KeySize; }
  mork_size       FormValSize() const { return mMap_Form.mMapForm_ValSize; }

  mork_bool       FormKeyIsIP() const { return mMap_Form.mMapForm_KeyIsIP; }
  mork_bool       FormValIsIP() const { return mMap_Form.mMapForm_ValIsIP; }

  mork_bool       FormHoldChanges() const
  { return mMap_Form.mMapForm_HoldChanges; }
  
  mork_change*    FormDummyChange()
  { return &mMap_Form.mMapForm_DummyChange; }

public: // other map methods
 
  mork_bool Put(morkEnv* ev, const void* inKey, const void* inVal,
    void* outKey, void* outVal, mork_change** outChange);
    
  mork_bool Cut(morkEnv* ev, const void* inKey,
    void* outKey, void* outVal, mork_change** outChange);
    
  mork_bool Get(morkEnv* ev, const void* inKey, 
    void* outKey, void* outVal, mork_change** outChange);
    
  mork_num CutAll(morkEnv* ev);

private: // copying is not allowed
  morkMap(const morkMap& other);
  morkMap& operator=(const morkMap& other);


public: // typesafe refcounting inlines calling inherited morkNode methods
  static void SlotWeakMap(morkMap* me,
    morkEnv* ev, morkMap** ioSlot)
  { morkNode::SlotWeakNode((morkNode*) me, ev, (morkNode**) ioSlot); }
  
  static void SlotStrongMap(morkMap* me,
    morkEnv* ev, morkMap** ioSlot)
  { morkNode::SlotStrongNode((morkNode*) me, ev, (morkNode**) ioSlot); }
};

/*| morkMapIter: an iterator for morkMap and subclasses.  This is not a node,
**| and expected usage is as a member of some other node subclass, such as in
**| a cursor subclass or a thumb subclass.  Also, iters might be as temp stack
**| objects when scanning the content of a map.
|*/
class morkMapIter{  // iterator for hash table map

protected:
  morkMap*    mMapIter_Map;      // map to iterate, NOT refcounted
  mork_seed   mMapIter_Seed;     // cached copy of map's seed
  
  morkAssoc** mMapIter_Bucket;   // one bucket in mMap_Buckets array
  morkAssoc** mMapIter_AssocRef; // usually *AtRef equals Here
  morkAssoc*  mMapIter_Assoc;    // the current assoc in an iteration
  morkAssoc*  mMapIter_Next;     // mMapIter_Assoc->mAssoc_Next */

public:
  morkMapIter(morkEnv* ev, morkMap* ioMap);
  void CloseMapIter(morkEnv* ev);
 
  morkMapIter( ); // everything set to zero -- need to call InitMapIter()

protected: // we want all subclasses to provide typesafe wrappers:

  void InitMapIter(morkEnv* ev, morkMap* ioMap);
 
  // The morkAssoc returned below is always either mork_change* or
  // else nil (when there is no such assoc).  We return a pointer to
  // the change rather than a simple bool, because callers might
  // want to access change info associated with an assoc.
  
  mork_change* First(morkEnv* ev, void* outKey, void* outVal);
  mork_change* Next(morkEnv* ev, void* outKey, void* outVal);
  mork_change* Here(morkEnv* ev, void* outKey, void* outVal);
  
  mork_change* CutHere(morkEnv* ev, void* outKey, void* outVal);
};

//3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789

#endif /* _MORKMAP_ */