@Test public void testPutRemoveOnSamePlaces() throws Exception { withMap(map -> { doAddRemove(map); for (int i = 0; i < 99; i++) { int grpId = i + 1; int val = grpId * grpId; assertSizeChanged("Unique put should be successful " + grpId, map, () -> map.put(grpId, 1, val, 1)); } doAddRemove(map); }, 100); }
@Override public void put(int grpId, long pageId, long val, int ver) { assert grpId != 0; int idxInit = U.safeAbs(FullPageId.hashCode(grpId, pageId)) % numBuckets; int swapCnt = 0; int grpIdToInsert = grpId; long pageIdToInsert = pageId; long valToInsert = val; int verToInsert = ver; int idxIdealToInsert = idxInit; for (int i = 0; i < numBuckets; i++) { int idxCurr = (idxInit + i) % numBuckets; final long base = entryBase(idxCurr); final int dibEntryToInsert = distance(idxCurr, idxInit); final int curGrpId = getGrpId(base); final long curPageId = getPageId(base); final int curIdealBucket = getIdealBucket(base); final long curVal = getValue(base); final int curVer = getVersion(base); final int dibCurEntry = distance(idxCurr, curIdealBucket); if (isEmpty(curGrpId, curPageId)) { setCellValue(base, idxIdealToInsert, grpIdToInsert, pageIdToInsert, valToInsert, verToInsert); setSize(size() + 1); return; } else if (curGrpId == grpIdToInsert && curPageId == pageIdToInsert) { if (swapCnt != 0) throw new IllegalStateException("Swapped " + swapCnt + " times. Entry: " + dumpEntry(idxCurr)); setValue(base, valToInsert); return; } else if (dibCurEntry < dibEntryToInsert) { setCellValue(base, idxIdealToInsert, grpIdToInsert, pageIdToInsert, valToInsert, verToInsert); idxIdealToInsert = curIdealBucket; pageIdToInsert = curPageId; grpIdToInsert = curGrpId; valToInsert = curVal; verToInsert = curVer; swapCnt++; } } throw new IgniteOutOfMemoryException("No room for a new key"); }
RobinHoodBackwardShiftHashMap implements LoadedPagesMap { @Override public void put(int grpId, long pageId, long val, int ver) { assert grpId != 0; int idxInit = U.safeAbs(FullPageId.hashCode(grpId, pageId)) % numBuckets; int swapCnt = 0; int grpIdToInsert = grpId; long pageIdToInsert = pageId; long valToInsert = val; int verToInsert = ver; int idxIdealToInsert = idxInit; for (int i = 0; i < numBuckets; i++) { int idxCurr = (idxInit + i) % numBuckets; final long base = entryBase(idxCurr); final int dibEntryToInsert = distance(idxCurr, idxInit); final int curGrpId = getGrpId(base); final long curPageId = getPageId(base); final int curIdealBucket = getIdealBucket(base); final long curVal = getValue(base); final int curVer = getVersion(base); final int dibCurEntry = distance(idxCurr, curIdealBucket); if (isEmpty(curGrpId, curPageId)) { setCellValue(base, idxIdealToInsert, grpIdToInsert, pageIdToInsert, valToInsert, verToInsert); setSize(size() + 1); return; } else if (curGrpId == grpIdToInsert && curPageId == pageIdToInsert) { if (swapCnt != 0) throw new IllegalStateException("Swapped " + swapCnt + " times. Entry: " + dumpEntry(idxCurr)); setValue(base, valToInsert); return; } else if (dibCurEntry < dibEntryToInsert) { setCellValue(base, idxIdealToInsert, grpIdToInsert, pageIdToInsert, valToInsert, verToInsert); idxIdealToInsert = curIdealBucket; pageIdToInsert = curPageId; grpIdToInsert = curGrpId; valToInsert = curVal; verToInsert = curVer; swapCnt++; } } throw new IgniteOutOfMemoryException("No room for a new key"); } }
RobinHoodBackwardShiftHashMap implements LoadedPagesMap { @Override public void put(int grpId, long pageId, long val, int ver) { assert grpId != 0; int idxInit = U.safeAbs(FullPageId.hashCode(grpId, pageId)) % numBuckets; int swapCnt = 0; int grpIdToInsert = grpId; long pageIdToInsert = pageId; long valToInsert = val; int verToInsert = ver; int idxIdealToInsert = idxInit; for (int i = 0; i < numBuckets; i++) { int idxCurr = (idxInit + i) % numBuckets; final long base = entryBase(idxCurr); final int dibEntryToInsert = distance(idxCurr, idxInit); final int curGrpId = getGrpId(base); final long curPageId = getPageId(base); final int curIdealBucket = getIdealBucket(base); final long curVal = getValue(base); final int curVer = getVersion(base); final int dibCurEntry = distance(idxCurr, curIdealBucket); if (isEmpty(curGrpId, curPageId)) { setCellValue(base, idxIdealToInsert, grpIdToInsert, pageIdToInsert, valToInsert, verToInsert); setSize(size() + 1); return; } else if (curGrpId == grpIdToInsert && curPageId == pageIdToInsert) { if (swapCnt != 0) throw new IllegalStateException("Swapped " + swapCnt + " times. Entry: " + dumpEntry(idxCurr)); setValue(base, valToInsert); return; } else if (dibCurEntry < dibEntryToInsert) { setCellValue(base, idxIdealToInsert, grpIdToInsert, pageIdToInsert, valToInsert, verToInsert); idxIdealToInsert = curIdealBucket; pageIdToInsert = curPageId; grpIdToInsert = curGrpId; valToInsert = curVal; verToInsert = curVer; swapCnt++; } } throw new IgniteOutOfMemoryException("No room for a new key"); } RobinHoodBackwardShiftHashMap(long baseAddr, long size); }
RobinHoodBackwardShiftHashMap implements LoadedPagesMap { @Override public void put(int grpId, long pageId, long val, int ver) { assert grpId != 0; int idxInit = U.safeAbs(FullPageId.hashCode(grpId, pageId)) % numBuckets; int swapCnt = 0; int grpIdToInsert = grpId; long pageIdToInsert = pageId; long valToInsert = val; int verToInsert = ver; int idxIdealToInsert = idxInit; for (int i = 0; i < numBuckets; i++) { int idxCurr = (idxInit + i) % numBuckets; final long base = entryBase(idxCurr); final int dibEntryToInsert = distance(idxCurr, idxInit); final int curGrpId = getGrpId(base); final long curPageId = getPageId(base); final int curIdealBucket = getIdealBucket(base); final long curVal = getValue(base); final int curVer = getVersion(base); final int dibCurEntry = distance(idxCurr, curIdealBucket); if (isEmpty(curGrpId, curPageId)) { setCellValue(base, idxIdealToInsert, grpIdToInsert, pageIdToInsert, valToInsert, verToInsert); setSize(size() + 1); return; } else if (curGrpId == grpIdToInsert && curPageId == pageIdToInsert) { if (swapCnt != 0) throw new IllegalStateException("Swapped " + swapCnt + " times. Entry: " + dumpEntry(idxCurr)); setValue(base, valToInsert); return; } else if (dibCurEntry < dibEntryToInsert) { setCellValue(base, idxIdealToInsert, grpIdToInsert, pageIdToInsert, valToInsert, verToInsert); idxIdealToInsert = curIdealBucket; pageIdToInsert = curPageId; grpIdToInsert = curGrpId; valToInsert = curVal; verToInsert = curVer; swapCnt++; } } throw new IgniteOutOfMemoryException("No room for a new key"); } RobinHoodBackwardShiftHashMap(long baseAddr, long size); static long requiredMemory(long elementsCnt); @Override long get(int grpId, long pageId, int reqVer, long absent, long outdated); @Override void put(int grpId, long pageId, long val, int ver); @Override boolean remove(int grpId, long pageId); @Override ReplaceCandidate getNearestAt(final int idxStart); @Override long refresh(int grpId, long pageId, int ver); @Override GridLongList removeIf(int startIdxToClear, int endIdxToClear, KeyPredicate keyPred); @Override int capacity(); String dump(); @Override final int size(); @Override void forEach(BiConsumer<FullPageId, Long> act); }
RobinHoodBackwardShiftHashMap implements LoadedPagesMap { @Override public void put(int grpId, long pageId, long val, int ver) { assert grpId != 0; int idxInit = U.safeAbs(FullPageId.hashCode(grpId, pageId)) % numBuckets; int swapCnt = 0; int grpIdToInsert = grpId; long pageIdToInsert = pageId; long valToInsert = val; int verToInsert = ver; int idxIdealToInsert = idxInit; for (int i = 0; i < numBuckets; i++) { int idxCurr = (idxInit + i) % numBuckets; final long base = entryBase(idxCurr); final int dibEntryToInsert = distance(idxCurr, idxInit); final int curGrpId = getGrpId(base); final long curPageId = getPageId(base); final int curIdealBucket = getIdealBucket(base); final long curVal = getValue(base); final int curVer = getVersion(base); final int dibCurEntry = distance(idxCurr, curIdealBucket); if (isEmpty(curGrpId, curPageId)) { setCellValue(base, idxIdealToInsert, grpIdToInsert, pageIdToInsert, valToInsert, verToInsert); setSize(size() + 1); return; } else if (curGrpId == grpIdToInsert && curPageId == pageIdToInsert) { if (swapCnt != 0) throw new IllegalStateException("Swapped " + swapCnt + " times. Entry: " + dumpEntry(idxCurr)); setValue(base, valToInsert); return; } else if (dibCurEntry < dibEntryToInsert) { setCellValue(base, idxIdealToInsert, grpIdToInsert, pageIdToInsert, valToInsert, verToInsert); idxIdealToInsert = curIdealBucket; pageIdToInsert = curPageId; grpIdToInsert = curGrpId; valToInsert = curVal; verToInsert = curVer; swapCnt++; } } throw new IgniteOutOfMemoryException("No room for a new key"); } RobinHoodBackwardShiftHashMap(long baseAddr, long size); static long requiredMemory(long elementsCnt); @Override long get(int grpId, long pageId, int reqVer, long absent, long outdated); @Override void put(int grpId, long pageId, long val, int ver); @Override boolean remove(int grpId, long pageId); @Override ReplaceCandidate getNearestAt(final int idxStart); @Override long refresh(int grpId, long pageId, int ver); @Override GridLongList removeIf(int startIdxToClear, int endIdxToClear, KeyPredicate keyPred); @Override int capacity(); String dump(); @Override final int size(); @Override void forEach(BiConsumer<FullPageId, Long> act);  }