// @(#)root/cont:$Id$
// Author: Fons Rademakers   26/05/99

/*************************************************************************
 * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers.               *
 * All rights reserved.                                                  *
 *                                                                       *
 * For the licensing terms see $ROOTSYS/LICENSE.                         *
 * For the list of contributors see $ROOTSYS/README/CREDITS.             *
 *************************************************************************/

//////////////////////////////////////////////////////////////////////////
//                                                                      //
// TExMap                                                               //
//                                                                      //
// This class stores a (key,value) pair using an external hash.         //
// The (key,value) are Long64_t's and therefore can contain object      //
// pointers or any longs. The map uses an open addressing hashing       //
// method (linear probing).                                             //
//                                                                      //
//////////////////////////////////////////////////////////////////////////

#include "TExMap.h"
#include "TError.h"
#include "TMathBase.h"
#include <string.h>


ClassImp(TExMap)

//______________________________________________________________________________
TExMap::TExMap(Int_t mapSize)
{
   // Create a TExMap.

   // needed for automatic resizing to guarantee that one slot is always empty
   if (mapSize < 4) mapSize = 5;

   switch (mapSize) {
      // Avoid calling NextPrime for the common case:
      case   5: fSize = 5; break;
      case 503: fSize = 503; break;
      default:
         fSize  = (Int_t)TMath::NextPrime(mapSize);
   }
   fTable = new Assoc_t [fSize];

   memset(fTable,0,sizeof(Assoc_t)*fSize);
   fTally = 0;
}

//______________________________________________________________________________
TExMap::TExMap(const TExMap &map) : TObject(map)
{
   // Copy constructor.

   fSize  = map.fSize;
   fTally = map.fTally;
   fTable = new Assoc_t [fSize];
   memcpy(fTable, map.fTable, fSize*sizeof(Assoc_t));
}

//______________________________________________________________________________
TExMap& TExMap::operator=(const TExMap &map)
{
   // Assignement operator.

   if (this != &map) {
      TObject::operator=(map);
      fSize  = map.fSize;
      fTally = map.fTally;
      fTable = new Assoc_t [fSize];
      memcpy(fTable, map.fTable, fSize*sizeof(Assoc_t));
   }
   return *this;
}

//______________________________________________________________________________
TExMap::~TExMap()
{
   // Delete TExMap.

   delete [] fTable; fTable = 0;
}

//______________________________________________________________________________
void TExMap::Add(ULong64_t hash, Long64_t key, Long64_t value)
{
   // Add an (key,value) pair to the table. The key should be unique.

   if (!fTable) return;

   Int_t slot = FindElement(hash, key);
   if (!fTable[slot].InUse()) {
      fTable[slot].SetHash(hash);
      fTable[slot].fKey = key;
      fTable[slot].fValue = value;
      fTally++;
      if (HighWaterMark())
         Expand(2 * fSize);
   } else
      Error("Add", "key %lld is not unique", key);
}

//______________________________________________________________________________
void TExMap::AddAt(UInt_t slot, ULong64_t hash, Long64_t key, Long64_t value)
{
   // Add an (key,value) pair to the table. The key should be unique.
   // If the 'slot' is open, use it to store the value,
   // otherwise revert to Add(hash,key,value)
   // This is usually used in conjuction with GetValue wiht 3 parameters:
   // if ((idx = (ULong64_t)fMap->GetValue(hash, key, slot)) != 0) {
   //    ...
   // } else {
   //    fMap->AddAt(slot,hash,key,value);
   // }

   if (!fTable) return;

   if (!fTable[slot].InUse()) {
      fTable[slot].SetHash(hash);
      fTable[slot].fKey = key;
      fTable[slot].fValue = value;
      fTally++;
      if (HighWaterMark())
         Expand(2 * fSize);
   } else {
      Add(hash,key,value);
   }
}

//______________________________________________________________________________
Long64_t &TExMap::operator()(ULong64_t hash, Long64_t key)
{
   // Return a reference to the value belonging to the key with the
   // specified hash value. If the key does not exist it will be added.
   // NOTE: the reference will be invalidated an Expand() triggered by
   // an Add() or another operator() call.

   static Long64_t err;
   if (!fTable) {
      Error("operator()", "fTable==0, should never happen");
      return err;
   }

   Int_t slot = FindElement(hash, key);
   if (!fTable[slot].InUse()) {
      fTable[slot].SetHash(hash);
      fTable[slot].fKey = key;
      fTable[slot].fValue = 0;
      fTally++;
      if (HighWaterMark()) {
         Expand(2 * fSize);
         slot = FindElement(hash, key);
      }
   }
   return fTable[slot].fValue;
}

//______________________________________________________________________________
void TExMap::Delete(Option_t *)
{
   // Delete all entries stored in the TExMap.

   memset(fTable,0,sizeof(Assoc_t)*fSize);
   fTally = 0;
}

//______________________________________________________________________________
Long64_t TExMap::GetValue(ULong64_t hash, Long64_t key)
{
   // Return the value belonging to specified key and hash value. If key not
   // found return 0.

   if (!fTable) return 0;

   hash |= 0x1;
   Int_t slot = Int_t(hash % fSize);
   Int_t firstSlot = slot;
   do {
      if (!fTable[slot].InUse()) return 0;
      if (key == fTable[slot].fKey) return fTable[slot].fValue;
      if (++slot == fSize) slot = 0;
   } while (firstSlot != slot);

   Error("GetValue", "table full");
   return 0;
}

//______________________________________________________________________________
Long64_t TExMap::GetValue(ULong64_t hash, Long64_t key, UInt_t &slot)
{
   // Return the value belonging to specified key and hash value. If key not
   // found return 0.
   // In 'slot', return the index of the slot used or the first empty slot.
   // (to be used with AddAt).

   if (!fTable) { slot = 0; return 0; }

   hash |= 0x1;
   slot = Int_t(hash % fSize);
   UInt_t firstSlot = slot;
   do {
      if (!fTable[slot].InUse()) return 0;
      if (key == fTable[slot].fKey) return fTable[slot].fValue;
      if (++slot == (UInt_t)fSize) slot = 0;
   } while (firstSlot != slot);

   Error("GetValue", "table full");
   return 0;
}

//______________________________________________________________________________
void TExMap::Remove(ULong64_t hash, Long64_t key)
{
   // Remove entry with specified key from the TExMap.

   if (!fTable)
      return;

   Int_t i = FindElement(hash, key);
   if (!fTable[i].InUse()) {
      Error("Remove", "key %lld not found at %d", key, i);
      return;
   }

   fTable[i].Clear();
   FixCollisions(i);
   fTally--;
}

//______________________________________________________________________________
Int_t TExMap::FindElement(ULong64_t hash, Long64_t key)
{
   // Find an entry with specified hash and key in the TExMap.
   // Returns the slot of the key or the next empty slot.

   if (!fTable) return 0;

   hash |= 0x1;
   Int_t slot = Int_t(hash % fSize);
   Int_t firstSlot = slot;
   do {
      if (!fTable[slot].InUse()) return slot;
      if (key == fTable[slot].fKey) return slot;
      if (++slot == fSize) slot = 0;
   } while (firstSlot != slot);

   Error("FindElement", "table full");
   return 0;
}

//______________________________________________________________________________
void TExMap::FixCollisions(Int_t index)
{
   // Rehash the map in case an entry has been removed.

   Int_t oldIndex, nextIndex;
   Assoc_t nextObject;

   for (oldIndex = index+1; ;oldIndex++) {
      if (oldIndex >= fSize)
         oldIndex = 0;
      nextObject = fTable[oldIndex];
      if (!nextObject.InUse())
         break;
      nextIndex = FindElement(nextObject.GetHash(), nextObject.fKey);
      if (nextIndex != oldIndex) {
         fTable[nextIndex] = nextObject;
         fTable[oldIndex].Clear();
      }
   }
}

//______________________________________________________________________________
void TExMap::Expand(Int_t newSize)
{
   // Expand the TExMap.

   Int_t i;
   Assoc_t *oldTable = fTable;
   Int_t oldsize = fSize;
   newSize = (Int_t)TMath::NextPrime(newSize);
   fTable  = new Assoc_t [newSize];

   for (i = newSize; --i >= 0;) {
      fTable[i].Clear();
   }

   fSize = newSize;
   for (i = 0; i < oldsize; i++)
      if (oldTable[i].InUse()) {
         Int_t slot = FindElement(oldTable[i].GetHash(), oldTable[i].fKey);
         if (!fTable[slot].InUse())
            fTable[slot] = oldTable[i];
         else
            Error("Expand", "slot %d not empty (should never happen)", slot);
      }
   delete [] oldTable;
}

//_______________________________________________________________________
void TExMap::Streamer(TBuffer &b)
{
   // Stream all objects in the collection to or from the I/O buffer.

   Int_t i;
   UInt_t R__s, R__c;

   if (b.IsReading()) {
      Version_t R__v = b.ReadVersion(&R__s, &R__c);
      TObject::Streamer(b);

      if (R__v >= 3) {
         // new custom streamer with slots indices stored (Long64_t version).
         Int_t size, tally;
         b >> size;
         Expand(size);
         b >> tally;
         Int_t slot;
         ULong64_t hash;
         Long64_t key, value;
         for (i = 0; i < tally; ++i) {
            b >> slot;
            b >> hash;
            b >> key;
            b >> value;
            Assoc_t *assoc = fTable + slot;
            assoc->SetHash(hash);
            assoc->fKey = key;
            assoc->fValue = value;
         }
         fTally = tally;
      } else if (R__v >= 2) {
         // new custom streamer with slots indices stored.
         Int_t size, tally;
         b >> size;
         Expand(size);
         b >> tally;
         Int_t slot;
         ULong_t hash;
         Long_t key, value;
         for (i = 0; i < tally; ++i) {
            b >> slot;
            b >> hash;
            b >> key;
            b >> value;
            Assoc_t* assoc = fTable + slot;
            assoc->SetHash(hash);
            assoc->fKey = key;
            assoc->fValue = value;
         }
         fTally = tally;
      } else {
         // old custom streamer that only allows slow dynamic rebuild of TExMap:
         Int_t n;
         b >> n;
         ULong_t hash;
         Long_t key, value;
         for (i = 0; i < n; i++) {
            b >> hash;
            b >> key;
            b >> value;
            Add(hash, key, value);
         }
      }
      b.CheckByteCount(R__s, R__c, TExMap::IsA());
   } else {
      R__c = b.WriteVersion(TExMap::IsA(), kTRUE);
      // new custom streamer stores slots indices
      TObject::Streamer(b);
      b << fSize;
      b << fTally;

      for (i=0; i < fSize; i++) {
         if (!fTable[i].InUse()) continue;
         b << i;
         b << fTable[i].GetHash();
         b << fTable[i].fKey;
         b << fTable[i].fValue;
      }
      b.SetByteCount(R__c, kTRUE);
   }
}


ClassImp(TExMapIter)

//______________________________________________________________________________
TExMapIter::TExMapIter(const TExMap *map) : fMap(map), fCursor(0)
{
   // Create TExMap iterator.
}

//______________________________________________________________________________
TExMapIter &TExMapIter::operator=(const TExMapIter &rhs)
{
   // Overloaded assignment operator.

   if (this != &rhs) {
      fMap    = rhs.fMap;
      fCursor = rhs.fCursor;
   }
   return *this;
}

//______________________________________________________________________________
Bool_t TExMapIter::Next(ULong64_t &hash, Long64_t &key, Long64_t &value)
{
   // Get next entry from TExMap. Returns kFALSE at end of map.

   while (fCursor < fMap->fSize && !fMap->fTable[fCursor].InUse())
      fCursor++;

   if (fCursor == fMap->fSize)
      return kFALSE;

   hash  = fMap->fTable[fCursor].GetHash();
   key   = fMap->fTable[fCursor].fKey;
   value = fMap->fTable[fCursor].fValue;
   fCursor++;

   return kTRUE;
}

//______________________________________________________________________________
Bool_t TExMapIter::Next(Long64_t &key, Long64_t &value)
{
   // Get next entry from TExMap. Returns kFALSE at end of map.

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