- FoldingSetNodeID ID;
- TreeTy::Profile(ID,L,R,V);
- void* InsertPos;
-
- if (TreeTy* T = Cache.FindNodeOrInsertPos(ID,InsertPos))
+ // Search the FoldingSet bucket for a Tree with the same digest.
+ FoldingSetNodeID ID;
+ unsigned digest = TreeTy::ComputeDigest(L, R, V);
+ ID.AddInteger(digest);
+ unsigned hash = ID.ComputeHash();
+
+ typename CacheTy::bucket_iterator I = Cache.bucket_begin(hash);
+ typename CacheTy::bucket_iterator E = Cache.bucket_end(hash);
+
+ for (; I != E; ++I) {
+ TreeTy* T = &*I;
+
+ if (T->ComputeDigest() != digest)
+ continue;
+
+ // We found a collision. Perform a comparison of Contents('T')
+ // with Contents('L')+'V'+Contents('R').
+
+ typename TreeTy::iterator TI = T->begin(), TE = T->end();
+
+ // First compare Contents('L') with the (initial) contents of T.
+ if (!CompareTreeWithSection(L, TI, TE))
+ continue;
+
+ // Now compare the new data element.
+ if (TI == TE || !TI->ElementEqual(V))
+ continue;
+
+ ++TI;
+
+ // Now compare the remainder of 'T' with 'R'.
+ if (!CompareTreeWithSection(R, TI, TE))
+ continue;
+
+ if (TI != TE) // Contents('R') did not match suffix of 'T'.
+ continue;
+
+ // Trees did match! Return 'T'.