Return-Path: X-Original-To: apmail-hbase-commits-archive@www.apache.org Delivered-To: apmail-hbase-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 67F76185F8 for ; Wed, 16 Dec 2015 16:50:50 +0000 (UTC) Received: (qmail 35688 invoked by uid 500); 16 Dec 2015 16:50:47 -0000 Delivered-To: apmail-hbase-commits-archive@hbase.apache.org Received: (qmail 35304 invoked by uid 500); 16 Dec 2015 16:50:47 -0000 Mailing-List: contact commits-help@hbase.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@hbase.apache.org Delivered-To: mailing list commits@hbase.apache.org Received: (qmail 34509 invoked by uid 99); 16 Dec 2015 16:50:47 -0000 Received: from git1-us-west.apache.org (HELO git1-us-west.apache.org) (140.211.11.23) by apache.org (qpsmtpd/0.29) with ESMTP; Wed, 16 Dec 2015 16:50:46 +0000 Received: by git1-us-west.apache.org (ASF Mail Server at git1-us-west.apache.org, from userid 33) id D855FE0A96; Wed, 16 Dec 2015 16:50:46 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: misty@apache.org To: commits@hbase.apache.org Date: Wed, 16 Dec 2015 16:51:08 -0000 Message-Id: In-Reply-To: <80cf44be04ef48d5b3105b20c6230b5c@git.apache.org> References: <80cf44be04ef48d5b3105b20c6230b5c@git.apache.org> X-Mailer: ASF-Git Admin Mailer Subject: [23/51] [partial] hbase-site git commit: Published site at 60d33ce34191533bb858852584bd9bddfeb16a23. http://git-wip-us.apache.org/repos/asf/hbase-site/blob/539ad177/devapidocs/src-html/org/apache/hadoop/hbase/procedure2/store/ProcedureStoreTracker.BitSetNode.html ---------------------------------------------------------------------- diff --git a/devapidocs/src-html/org/apache/hadoop/hbase/procedure2/store/ProcedureStoreTracker.BitSetNode.html b/devapidocs/src-html/org/apache/hadoop/hbase/procedure2/store/ProcedureStoreTracker.BitSetNode.html index 9a2a5bc..f6c7b80 100644 --- a/devapidocs/src-html/org/apache/hadoop/hbase/procedure2/store/ProcedureStoreTracker.BitSetNode.html +++ b/devapidocs/src-html/org/apache/hadoop/hbase/procedure2/store/ProcedureStoreTracker.BitSetNode.html @@ -35,574 +35,567 @@ 027 028import org.apache.hadoop.hbase.classification.InterfaceAudience; 029import org.apache.hadoop.hbase.classification.InterfaceStability; -030import org.apache.hadoop.hbase.procedure2.Procedure; -031import org.apache.hadoop.hbase.protobuf.generated.ProcedureProtos; -032 -033/** -034 * Keeps track of live procedures. -035 * -036 * It can be used by the ProcedureStore to identify which procedures are already -037 * deleted/completed to avoid the deserialization step on restart. -038 */ -039@InterfaceAudience.Private -040@InterfaceStability.Evolving -041public class ProcedureStoreTracker { -042 private final TreeMap<Long, BitSetNode> map = new TreeMap<Long, BitSetNode>(); -043 -044 private boolean keepDeletes = false; -045 private boolean partial = false; -046 -047 private long minUpdatedProcId = Long.MAX_VALUE; -048 private long maxUpdatedProcId = Long.MIN_VALUE; -049 -050 public enum DeleteState { YES, NO, MAYBE } -051 -052 public static class BitSetNode { -053 private final static long WORD_MASK = 0xffffffffffffffffL; -054 private final static int ADDRESS_BITS_PER_WORD = 6; -055 private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD; -056 private final static int MAX_NODE_SIZE = 1 << ADDRESS_BITS_PER_WORD; -057 -058 private final boolean partial; -059 private long[] updated; -060 private long[] deleted; -061 private long start; -062 -063 public void dump() { -064 System.out.printf("%06d:%06d min=%d max=%d%n", getStart(), getEnd(), -065 getMinProcId(), getMaxProcId()); -066 System.out.println("Update:"); -067 for (int i = 0; i < updated.length; ++i) { -068 for (int j = 0; j < BITS_PER_WORD; ++j) { -069 System.out.print((updated[i] & (1L << j)) != 0 ? "1" : "0"); -070 } -071 System.out.println(" " + i); -072 } -073 System.out.println(); -074 System.out.println("Delete:"); -075 for (int i = 0; i < deleted.length; ++i) { -076 for (int j = 0; j < BITS_PER_WORD; ++j) { -077 System.out.print((deleted[i] & (1L << j)) != 0 ? "1" : "0"); -078 } -079 System.out.println(" " + i); -080 } -081 System.out.println(); -082 } -083 -084 public BitSetNode(final long procId, final boolean partial) { -085 start = alignDown(procId); -086 -087 int count = 1; -088 updated = new long[count]; -089 deleted = new long[count]; -090 for (int i = 0; i < count; ++i) { -091 updated[i] = 0; -092 deleted[i] = partial ? 0 : WORD_MASK; -093 } -094 -095 this.partial = partial; -096 updateState(procId, false); -097 } -098 -099 protected BitSetNode(final long start, final long[] updated, final long[] deleted) { -100 this.start = start; -101 this.updated = updated; -102 this.deleted = deleted; -103 this.partial = false; -104 } -105 -106 public void update(final long procId) { -107 updateState(procId, false); -108 } -109 -110 public void delete(final long procId) { -111 updateState(procId, true); -112 } -113 -114 public Long getStart() { -115 return start; -116 } -117 -118 public Long getEnd() { -119 return start + (updated.length << ADDRESS_BITS_PER_WORD) - 1; -120 } -121 -122 public boolean contains(final long procId) { -123 return start <= procId && procId <= getEnd(); -124 } -125 -126 public DeleteState isDeleted(final long procId) { -127 int bitmapIndex = getBitmapIndex(procId); -128 int wordIndex = bitmapIndex >> ADDRESS_BITS_PER_WORD; -129 if (wordIndex >= deleted.length) { -130 return DeleteState.MAYBE; -131 } -132 return (deleted[wordIndex] & (1L << bitmapIndex)) != 0 ? DeleteState.YES : DeleteState.NO; -133 } -134 -135 private boolean isUpdated(final long procId) { -136 int bitmapIndex = getBitmapIndex(procId); -137 int wordIndex = bitmapIndex >> ADDRESS_BITS_PER_WORD; -138 if (wordIndex >= updated.length) { -139 return false; -140 } -141 return (updated[wordIndex] & (1L << bitmapIndex)) != 0; -142 } -143 -144 public boolean isUpdated() { -145 // TODO: cache the value -146 for (int i = 0; i < updated.length; ++i) { -147 if ((updated[i] | deleted[i]) != WORD_MASK) { -148 return false; -149 } -150 } -151 return true; -152 } -153 -154 public boolean isEmpty() { -155 // TODO: cache the value -156 for (int i = 0; i < deleted.length; ++i) { -157 if (deleted[i] != WORD_MASK) { -158 return false; -159 } -160 } -161 return true; -162 } -163 -164 public void resetUpdates() { -165 for (int i = 0; i < updated.length; ++i) { -166 updated[i] = 0; -167 } -168 } -169 -170 public void undeleteAll() { -171 for (int i = 0; i < updated.length; ++i) { -172 deleted[i] = 0; -173 } -174 } -175 -176 public void unsetPartialFlag() { -177 for (int i = 0; i < updated.length; ++i) { -178 for (int j = 0; j < BITS_PER_WORD; ++j) { -179 if ((updated[i] & (1L << j)) == 0) { -180 deleted[i] |= (1L << j); -181 } -182 } -183 } -184 } -185 -186 public ProcedureProtos.ProcedureStoreTracker.TrackerNode convert() { -187 ProcedureProtos.ProcedureStoreTracker.TrackerNode.Builder builder = -188 ProcedureProtos.ProcedureStoreTracker.TrackerNode.newBuilder(); -189 builder.setStartId(start); -190 for (int i = 0; i < updated.length; ++i) { -191 builder.addUpdated(updated[i]); -192 builder.addDeleted(deleted[i]); -193 } -194 return builder.build(); -195 } -196 -197 public static BitSetNode convert(ProcedureProtos.ProcedureStoreTracker.TrackerNode data) { -198 long start = data.getStartId(); -199 int size = data.getUpdatedCount(); -200 long[] updated = new long[size]; -201 long[] deleted = new long[size]; -202 for (int i = 0; i < size; ++i) { -203 updated[i] = data.getUpdated(i); -204 deleted[i] = data.getDeleted(i); -205 } -206 return new BitSetNode(start, updated, deleted); -207 } -208 -209 // ======================================================================== -210 // Grow/Merge Helpers -211 // ======================================================================== -212 public boolean canGrow(final long procId) { -213 return Math.abs(procId - start) < MAX_NODE_SIZE; -214 } -215 -216 public boolean canMerge(final BitSetNode rightNode) { -217 assert start < rightNode.getEnd(); -218 return (rightNode.getEnd() - start) < MAX_NODE_SIZE; -219 } -220 -221 public void grow(final long procId) { -222 int delta, offset; -223 -224 if (procId < start) { -225 // add to head -226 long newStart = alignDown(procId); -227 delta = (int)(start - newStart) >> ADDRESS_BITS_PER_WORD; -228 offset = delta; -229 start = newStart; -230 } else { -231 // Add to tail -232 long newEnd = alignUp(procId + 1); -233 delta = (int)(newEnd - getEnd()) >> ADDRESS_BITS_PER_WORD; -234 offset = 0; -235 } -236 -237 long[] newBitmap; -238 int oldSize = updated.length; -239 -240 newBitmap = new long[oldSize + delta]; -241 for (int i = 0; i < newBitmap.length; ++i) { -242 newBitmap[i] = 0; -243 } -244 System.arraycopy(updated, 0, newBitmap, offset, oldSize); -245 updated = newBitmap; -246 -247 newBitmap = new long[deleted.length + delta]; -248 for (int i = 0; i < newBitmap.length; ++i) { -249 newBitmap[i] = partial ? 0 : WORD_MASK; -250 } -251 System.arraycopy(deleted, 0, newBitmap, offset, oldSize); -252 deleted = newBitmap; -253 } -254 -255 public void merge(final BitSetNode rightNode) { -256 int delta = (int)(rightNode.getEnd() - getEnd()) >> ADDRESS_BITS_PER_WORD; -257 -258 long[] newBitmap; -259 int oldSize = updated.length; -260 int newSize = (delta - rightNode.updated.length); -261 int offset = oldSize + newSize; -262 -263 newBitmap = new long[oldSize + delta]; -264 System.arraycopy(updated, 0, newBitmap, 0, oldSize); -265 System.arraycopy(rightNode.updated, 0, newBitmap, offset, rightNode.updated.length); -266 updated = newBitmap; -267 -268 newBitmap = new long[oldSize + delta]; -269 System.arraycopy(deleted, 0, newBitmap, 0, oldSize); -270 System.arraycopy(rightNode.deleted, 0, newBitmap, offset, rightNode.deleted.length); -271 deleted = newBitmap; -272 -273 for (int i = 0; i < newSize; ++i) { -274 updated[offset + i] = 0; -275 deleted[offset + i] = partial ? 0 : WORD_MASK; -276 } -277 } -278 -279 @Override -280 public String toString() { -281 return "BitSetNode(" + getStart() + "-" + getEnd() + ")"; -282 } -283 -284 // ======================================================================== -285 // Min/Max Helpers -286 // ======================================================================== -287 public long getMinProcId() { -288 long minProcId = start; -289 for (int i = 0; i < deleted.length; ++i) { -290 if (deleted[i] == 0) { -291 return(minProcId); -292 } -293 -294 if (deleted[i] != WORD_MASK) { -295 for (int j = 0; j < BITS_PER_WORD; ++j) { -296 if ((deleted[i] & (1L << j)) != 0) { -297 return minProcId + j; -298 } -299 } -300 } -301 -302 minProcId += BITS_PER_WORD; -303 } -304 return minProcId; -305 } -306 -307 public long getMaxProcId() { -308 long maxProcId = getEnd(); -309 for (int i = deleted.length - 1; i >= 0; --i) { -310 if (deleted[i] == 0) { -311 return maxProcId; -312 } -313 -314 if (deleted[i] != WORD_MASK) { -315 for (int j = BITS_PER_WORD - 1; j >= 0; --j) { -316 if ((deleted[i] & (1L << j)) == 0) { -317 return maxProcId - (BITS_PER_WORD - 1 - j); -318 } -319 } -320 } -321 maxProcId -= BITS_PER_WORD; -322 } -323 return maxProcId; -324 } -325 -326 // ======================================================================== -327 // Bitmap Helpers -328 // ======================================================================== -329 private int getBitmapIndex(final long procId) { -330 return (int)(procId - start); -331 } -332 -333 private void updateState(final long procId, final boolean isDeleted) { -334 int bitmapIndex = getBitmapIndex(procId); -335 int wordIndex = bitmapIndex >> ADDRESS_BITS_PER_WORD; -336 long value = (1L << bitmapIndex); -337 -338 if (isDeleted) { -339 updated[wordIndex] |= value; -340 deleted[wordIndex] |= value; -341 } else { -342 updated[wordIndex] |= value; -343 deleted[wordIndex] &= ~value; -344 } -345 } -346 -347 // ======================================================================== -348 // Helpers -349 // ======================================================================== -350 private static long alignUp(final long x) { -351 return (x + (BITS_PER_WORD - 1)) & -BITS_PER_WORD; -352 } -353 -354 private static long alignDown(final long x) { -355 return x & -BITS_PER_WORD; -356 } -357 } -358 -359 public void insert(final Procedure proc, final Procedure[] subprocs) { -360 insert(proc.getProcId()); -361 if (subprocs != null) { -362 for (int i = 0; i < subprocs.length; ++i) { -363 insert(subprocs[i].getProcId()); -364 } -365 } -366 } -367 -368 public void update(final Procedure proc) { -369 update(proc.getProcId()); -370 } -371 -372 public void insert(long procId) { -373 BitSetNode node = getOrCreateNode(procId); -374 node.update(procId); -375 trackProcIds(procId); -376 } -377 -378 public void update(long procId) { -379 Map.Entry<Long, BitSetNode> entry = map.floorEntry(procId); -380 assert entry != null : "expected node to update procId=" + procId; -381 -382 BitSetNode node = entry.getValue(); -383 assert node.contains(procId); -384 node.update(procId); -385 trackProcIds(procId); -386 } -387 -388 public void delete(long procId) { -389 Map.Entry<Long, BitSetNode> entry = map.floorEntry(procId); -390 assert entry != null : "expected node to delete procId=" + procId; -391 -392 BitSetNode node = entry.getValue(); -393 assert node.contains(procId) : "expected procId in the node"; -394 node.delete(procId); -395 -396 if (!keepDeletes && node.isEmpty()) { -397 // TODO: RESET if (map.size() == 1) -398 map.remove(entry.getKey()); -399 } -400 -401 trackProcIds(procId); -402 } -403 -404 private void trackProcIds(long procId) { -405 minUpdatedProcId = Math.min(minUpdatedProcId, procId); -406 maxUpdatedProcId = Math.max(maxUpdatedProcId, procId); -407 } -408 -409 public long getUpdatedMinProcId() { -410 return minUpdatedProcId; -411 } -412 -413 public long getUpdatedMaxProcId() { -414 return maxUpdatedProcId; +030import org.apache.hadoop.hbase.protobuf.generated.ProcedureProtos; +031 +032/** +033 * Keeps track of live procedures. +034 * +035 * It can be used by the ProcedureStore to identify which procedures are already +036 * deleted/completed to avoid the deserialization step on restart. +037 */ +038@InterfaceAudience.Private +039@InterfaceStability.Evolving +040public class ProcedureStoreTracker { +041 private final TreeMap<Long, BitSetNode> map = new TreeMap<Long, BitSetNode>(); +042 +043 private boolean keepDeletes = false; +044 private boolean partial = false; +045 +046 private long minUpdatedProcId = Long.MAX_VALUE; +047 private long maxUpdatedProcId = Long.MIN_VALUE; +048 +049 public enum DeleteState { YES, NO, MAYBE } +050 +051 public static class BitSetNode { +052 private final static long WORD_MASK = 0xffffffffffffffffL; +053 private final static int ADDRESS_BITS_PER_WORD = 6; +054 private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD; +055 private final static int MAX_NODE_SIZE = 1 << ADDRESS_BITS_PER_WORD; +056 +057 private final boolean partial; +058 private long[] updated; +059 private long[] deleted; +060 private long start; +061 +062 public void dump() { +063 System.out.printf("%06d:%06d min=%d max=%d%n", getStart(), getEnd(), +064 getMinProcId(), getMaxProcId()); +065 System.out.println("Update:"); +066 for (int i = 0; i < updated.length; ++i) { +067 for (int j = 0; j < BITS_PER_WORD; ++j) { +068 System.out.print((updated[i] & (1L << j)) != 0 ? "1" : "0"); +069 } +070 System.out.println(" " + i); +071 } +072 System.out.println(); +073 System.out.println("Delete:"); +074 for (int i = 0; i < deleted.length; ++i) { +075 for (int j = 0; j < BITS_PER_WORD; ++j) { +076 System.out.print((deleted[i] & (1L << j)) != 0 ? "1" : "0"); +077 } +078 System.out.println(" " + i); +079 } +080 System.out.println(); +081 } +082 +083 public BitSetNode(final long procId, final boolean partial) { +084 start = alignDown(procId); +085 +086 int count = 1; +087 updated = new long[count]; +088 deleted = new long[count]; +089 for (int i = 0; i < count; ++i) { +090 updated[i] = 0; +091 deleted[i] = partial ? 0 : WORD_MASK; +092 } +093 +094 this.partial = partial; +095 updateState(procId, false); +096 } +097 +098 protected BitSetNode(final long start, final long[] updated, final long[] deleted) { +099 this.start = start; +100 this.updated = updated; +101 this.deleted = deleted; +102 this.partial = false; +103 } +104 +105 public void update(final long procId) { +106 updateState(procId, false); +107 } +108 +109 public void delete(final long procId) { +110 updateState(procId, true); +111 } +112 +113 public Long getStart() { +114 return start; +115 } +116 +117 public Long getEnd() { +118 return start + (updated.length << ADDRESS_BITS_PER_WORD) - 1; +119 } +120 +121 public boolean contains(final long procId) { +122 return start <= procId && procId <= getEnd(); +123 } +124 +125 public DeleteState isDeleted(final long procId) { +126 int bitmapIndex = getBitmapIndex(procId); +127 int wordIndex = bitmapIndex >> ADDRESS_BITS_PER_WORD; +128 if (wordIndex >= deleted.length) { +129 return DeleteState.MAYBE; +130 } +131 return (deleted[wordIndex] & (1L << bitmapIndex)) != 0 ? DeleteState.YES : DeleteState.NO; +132 } +133 +134 private boolean isUpdated(final long procId) { +135 int bitmapIndex = getBitmapIndex(procId); +136 int wordIndex = bitmapIndex >> ADDRESS_BITS_PER_WORD; +137 if (wordIndex >= updated.length) { +138 return false; +139 } +140 return (updated[wordIndex] & (1L << bitmapIndex)) != 0; +141 } +142 +143 public boolean isUpdated() { +144 // TODO: cache the value +145 for (int i = 0; i < updated.length; ++i) { +146 if ((updated[i] | deleted[i]) != WORD_MASK) { +147 return false; +148 } +149 } +150 return true; +151 } +152 +153 public boolean isEmpty() { +154 // TODO: cache the value +155 for (int i = 0; i < deleted.length; ++i) { +156 if (deleted[i] != WORD_MASK) { +157 return false; +158 } +159 } +160 return true; +161 } +162 +163 public void resetUpdates() { +164 for (int i = 0; i < updated.length; ++i) { +165 updated[i] = 0; +166 } +167 } +168 +169 public void undeleteAll() { +170 for (int i = 0; i < updated.length; ++i) { +171 deleted[i] = 0; +172 } +173 } +174 +175 public void unsetPartialFlag() { +176 for (int i = 0; i < updated.length; ++i) { +177 for (int j = 0; j < BITS_PER_WORD; ++j) { +178 if ((updated[i] & (1L << j)) == 0) { +179 deleted[i] |= (1L << j); +180 } +181 } +182 } +183 } +184 +185 public ProcedureProtos.ProcedureStoreTracker.TrackerNode convert() { +186 ProcedureProtos.ProcedureStoreTracker.TrackerNode.Builder builder = +187 ProcedureProtos.ProcedureStoreTracker.TrackerNode.newBuilder(); +188 builder.setStartId(start); +189 for (int i = 0; i < updated.length; ++i) { +190 builder.addUpdated(updated[i]); +191 builder.addDeleted(deleted[i]); +192 } +193 return builder.build(); +194 } +195 +196 public static BitSetNode convert(ProcedureProtos.ProcedureStoreTracker.TrackerNode data) { +197 long start = data.getStartId(); +198 int size = data.getUpdatedCount(); +199 long[] updated = new long[size]; +200 long[] deleted = new long[size]; +201 for (int i = 0; i < size; ++i) { +202 updated[i] = data.getUpdated(i); +203 deleted[i] = data.getDeleted(i); +204 } +205 return new BitSetNode(start, updated, deleted); +206 } +207 +208 // ======================================================================== +209 // Grow/Merge Helpers +210 // ======================================================================== +211 public boolean canGrow(final long procId) { +212 return Math.abs(procId - start) < MAX_NODE_SIZE; +213 } +214 +215 public boolean canMerge(final BitSetNode rightNode) { +216 assert start < rightNode.getEnd(); +217 return (rightNode.getEnd() - start) < MAX_NODE_SIZE; +218 } +219 +220 public void grow(final long procId) { +221 int delta, offset; +222 +223 if (procId < start) { +224 // add to head +225 long newStart = alignDown(procId); +226 delta = (int)(start - newStart) >> ADDRESS_BITS_PER_WORD; +227 offset = delta; +228 start = newStart; +229 } else { +230 // Add to tail +231 long newEnd = alignUp(procId + 1); +232 delta = (int)(newEnd - getEnd()) >> ADDRESS_BITS_PER_WORD; +233 offset = 0; +234 } +235 +236 long[] newBitmap; +237 int oldSize = updated.length; +238 +239 newBitmap = new long[oldSize + delta]; +240 for (int i = 0; i < newBitmap.length; ++i) { +241 newBitmap[i] = 0; +242 } +243 System.arraycopy(updated, 0, newBitmap, offset, oldSize); +244 updated = newBitmap; +245 +246 newBitmap = new long[deleted.length + delta]; +247 for (int i = 0; i < newBitmap.length; ++i) { +248 newBitmap[i] = partial ? 0 : WORD_MASK; +249 } +250 System.arraycopy(deleted, 0, newBitmap, offset, oldSize); +251 deleted = newBitmap; +252 } +253 +254 public void merge(final BitSetNode rightNode) { +255 int delta = (int)(rightNode.getEnd() - getEnd()) >> ADDRESS_BITS_PER_WORD; +256 +257 long[] newBitmap; +258 int oldSize = updated.length; +259 int newSize = (delta - rightNode.updated.length); +260 int offset = oldSize + newSize; +261 +262 newBitmap = new long[oldSize + delta]; +263 System.arraycopy(updated, 0, newBitmap, 0, oldSize); +264 System.arraycopy(rightNode.updated, 0, newBitmap, offset, rightNode.updated.length); +265 updated = newBitmap; +266 +267 newBitmap = new long[oldSize + delta]; +268 System.arraycopy(deleted, 0, newBitmap, 0, oldSize); +269 System.arraycopy(rightNode.deleted, 0, newBitmap, offset, rightNode.deleted.length); +270 deleted = newBitmap; +271 +272 for (int i = 0; i < newSize; ++i) { +273 updated[offset + i] = 0; +274 deleted[offset + i] = partial ? 0 : WORD_MASK; +275 } +276 } +277 +278 @Override +279 public String toString() { +280 return "BitSetNode(" + getStart() + "-" + getEnd() + ")"; +281 } +282 +283 // ======================================================================== +284 // Min/Max Helpers +285 // ======================================================================== +286 public long getMinProcId() { +287 long minProcId = start; +288 for (int i = 0; i < deleted.length; ++i) { +289 if (deleted[i] == 0) { +290 return(minProcId); +291 } +292 +293 if (deleted[i] != WORD_MASK) { +294 for (int j = 0; j < BITS_PER_WORD; ++j) { +295 if ((deleted[i] & (1L << j)) != 0) { +296 return minProcId + j; +297 } +298 } +299 } +300 +301 minProcId += BITS_PER_WORD; +302 } +303 return minProcId; +304 } +305 +306 public long getMaxProcId() { +307 long maxProcId = getEnd(); +308 for (int i = deleted.length - 1; i >= 0; --i) { +309 if (deleted[i] == 0) { +310 return maxProcId; +311 } +312 +313 if (deleted[i] != WORD_MASK) { +314 for (int j = BITS_PER_WORD - 1; j >= 0; --j) { +315 if ((deleted[i] & (1L << j)) == 0) { +316 return maxProcId - (BITS_PER_WORD - 1 - j); +317 } +318 } +319 } +320 maxProcId -= BITS_PER_WORD; +321 } +322 return maxProcId; +323 } +324 +325 // ======================================================================== +326 // Bitmap Helpers +327 // ======================================================================== +328 private int getBitmapIndex(final long procId) { +329 return (int)(procId - start); +330 } +331 +332 private void updateState(final long procId, final boolean isDeleted) { +333 int bitmapIndex = getBitmapIndex(procId); +334 int wordIndex = bitmapIndex >> ADDRESS_BITS_PER_WORD; +335 long value = (1L << bitmapIndex); +336 +337 if (isDeleted) { +338 updated[wordIndex] |= value; +339 deleted[wordIndex] |= value; +340 } else { +341 updated[wordIndex] |= value; +342 deleted[wordIndex] &= ~value; +343 } +344 } +345 +346 // ======================================================================== +347 // Helpers +348 // ======================================================================== +349 private static long alignUp(final long x) { +350 return (x + (BITS_PER_WORD - 1)) & -BITS_PER_WORD; +351 } +352 +353 private static long alignDown(final long x) { +354 return x & -BITS_PER_WORD; +355 } +356 } +357 +358 public void insert(long procId) { +359 BitSetNode node = getOrCreateNode(procId); +360 node.update(procId); +361 trackProcIds(procId); +362 } +363 +364 public void insert(final long procId, final long[] subProcIds) { +365 update(procId); +366 for (int i = 0; i < subProcIds.length; ++i) { +367 insert(subProcIds[i]); +368 } +369 } +370 +371 public void update(long procId) { +372 Map.Entry<Long, BitSetNode> entry = map.floorEntry(procId); +373 assert entry != null : "expected node to update procId=" + procId; +374 +375 BitSetNode node = entry.getValue(); +376 assert node.contains(procId); +377 node.update(procId); +378 trackProcIds(procId); +379 } +380 +381 public void delete(long procId) { +382 Map.Entry<Long, BitSetNode> entry = map.floorEntry(procId); +383 assert entry != null : "expected node to delete procId=" + procId; +384 +385 BitSetNode node = entry.getValue(); +386 assert node.contains(procId) : "expected procId in the node"; +387 node.delete(procId); +388 +389 if (!keepDeletes && node.isEmpty()) { +390 // TODO: RESET if (map.size() == 1) +391 map.remove(entry.getKey()); +392 } +393 +394 trackProcIds(procId); +395 } +396 +397 private void trackProcIds(long procId) { +398 minUpdatedProcId = Math.min(minUpdatedProcId, procId); +399 maxUpdatedProcId = Math.max(maxUpdatedProcId, procId); +400 } +401 +402 public long getUpdatedMinProcId() { +403 return minUpdatedProcId; +404 } +405 +406 public long getUpdatedMaxProcId() { +407 return maxUpdatedProcId; +408 } +409 +410 @InterfaceAudience.Private +411 public void setDeleted(final long procId, final boolean isDeleted) { +412 BitSetNode node = getOrCreateNode(procId); +413 assert node.contains(procId) : "expected procId=" + procId + " in the node=" + node; +414 node.updateState(procId, isDeleted); 415 } 416 -417 @InterfaceAudience.Private -418 public void setDeleted(final long procId, final boolean isDeleted) { -419 BitSetNode node = getOrCreateNode(procId); -420 assert node.contains(procId) : "expected procId=" + procId + " in the node=" + node; -421 node.updateState(procId, isDeleted); -422 } -423 -424 public void clear() { -425 this.map.clear(); -426 resetUpdates(); -427 } -428 -429 public DeleteState isDeleted(long procId) { -430 Map.Entry<Long, BitSetNode> entry = map.floorEntry(procId); -431 if (entry != null && entry.getValue().contains(procId)) { -432 BitSetNode node = entry.getValue(); -433 DeleteState state = node.isDeleted(procId); -434 return partial && !node.isUpdated(procId) ? DeleteState.MAYBE : state; -435 } -436 return partial ? DeleteState.MAYBE : DeleteState.YES; -437 } -438 -439 public long getMinProcId() { -440 // TODO: Cache? -441 Map.Entry<Long, BitSetNode> entry = map.firstEntry(); -442 return entry == null ? 0 : entry.getValue().getMinProcId(); -443 } -444 -445 public void setKeepDeletes(boolean keepDeletes) { -446 this.keepDeletes = keepDeletes; -447 if (!keepDeletes) { -448 Iterator<Map.Entry<Long, BitSetNode>> it = map.entrySet().iterator(); -449 while (it.hasNext()) { -450 Map.Entry<Long, BitSetNode> entry = it.next(); -451 if (entry.getValue().isEmpty()) { -452 it.remove(); -453 } -454 } -455 } -456 } -457 -458 public void setPartialFlag(boolean isPartial) { -459 if (this.partial && !isPartial) { -460 for (Map.Entry<Long, BitSetNode> entry : map.entrySet()) { -461 entry.getValue().unsetPartialFlag(); -462 } -463 } -464 this.partial = isPartial; -465 } -466 -467 public boolean isEmpty() { -468 for (Map.Entry<Long, BitSetNode> entry : map.entrySet()) { -469 if (entry.getValue().isEmpty() == false) { -470 return false; -471 } -472 } -473 return true; -474 } -475 -476 public boolean isUpdated() { -477 for (Map.Entry<Long, BitSetNode> entry : map.entrySet()) { -478 if (entry.getValue().isUpdated() == false) { -479 return false; -480 } -481 } -482 return true; -483 } -484 -485 public boolean isTracking(long minId, long maxId) { -486 // TODO: we can make it more precise, instead of looking just at the block -487 return map.floorEntry(minId) != null || map.floorEntry(maxId) != null; -488 } -489 -490 public void resetUpdates() { -491 for (Map.Entry<Long, BitSetNode> entry : map.entrySet()) { -492 entry.getValue().resetUpdates(); -493 } -494 minUpdatedProcId = Long.MAX_VALUE; -495 maxUpdatedProcId = Long.MIN_VALUE; -496 } -497 -498 public void undeleteAll() { -499 for (Map.Entry<Long, BitSetNode> entry : map.entrySet()) { -500 entry.getValue().undeleteAll(); -501 } -502 } -503 -504 private BitSetNode getOrCreateNode(final long procId) { -505 // can procId fit in the left node? -506 BitSetNode leftNode = null; -507 boolean leftCanGrow = false; -508 Map.Entry<Long, BitSetNode> leftEntry = map.floorEntry(procId); -509 if (leftEntry != null) { -510 leftNode = leftEntry.getValue(); -511 if (leftNode.contains(procId)) { -512 return leftNode; -513 } -514 leftCanGrow = leftNode.canGrow(procId); -515 } -516 -517 BitSetNode rightNode = null; -518 boolean rightCanGrow = false; -519 Map.Entry<Long, BitSetNode> rightEntry = map.ceilingEntry(procId); -520 if (rightEntry != null) { -521 rightNode = rightEntry.getValue(); -522 rightCanGrow = rightNode.canGrow(procId); -523 if (leftNode != null) { -524 if (leftNode.canMerge(rightNode)) { -525 // merge left and right node -526 return mergeNodes(leftNode, rightNode); -527 } -528 -529 if (leftCanGrow && rightCanGrow) { -530 if ((procId - leftNode.getEnd()) <= (rightNode.getStart() - procId)) { -531 // grow the left node -532 return growNode(leftNode, procId); -533 } -534 // grow the right node -535 return growNode(rightNode, procId); -536 } -537 } -538 } -539 -540 // grow the left node -541 if (leftCanGrow) { -542 return growNode(leftNode, procId); -543 } -544 -545 // grow the right node -546 if (rightCanGrow) { -547 return growNode(rightNode, procId); -548 } -549 -550 // add new node -551 BitSetNode node = new BitSetNode(procId, partial); +417 public void clear() { +418 this.map.clear(); +419 resetUpdates(); +420 } +421 +422 public DeleteState isDeleted(long procId) { +423 Map.Entry<Long, BitSetNode> entry = map.floorEntry(procId); +424 if (entry != null && entry.getValue().contains(procId)) { +425 BitSetNode node = entry.getValue(); +426 DeleteState state = node.isDeleted(procId); +427 return partial && !node.isUpdated(procId) ? DeleteState.MAYBE : state; +428 } +429 return partial ? DeleteState.MAYBE : DeleteState.YES; +430 } +431 +432 public long getMinProcId() { +433 // TODO: Cache? +434 Map.Entry<Long, BitSetNode> entry = map.firstEntry(); +435 return entry == null ? 0 : entry.getValue().getMinProcId(); +436 } +437 +438 public void setKeepDeletes(boolean keepDeletes) { +439 this.keepDeletes = keepDeletes; +440 if (!keepDeletes) { +441 Iterator<Map.Entry<Long, BitSetNode>> it = map.entrySet().iterator(); +442 while (it.hasNext()) { +443 Map.Entry<Long, BitSetNode> entry = it.next(); +444 if (entry.getValue().isEmpty()) { +445 it.remove(); +446 } +447 } +448 } +449 } +450 +451 public void setPartialFlag(boolean isPartial) { +452 if (this.partial && !isPartial) { +453 for (Map.Entry<Long, BitSetNode> entry : map.entrySet()) { +454 entry.getValue().unsetPartialFlag(); +455 } +456 } +457 this.partial = isPartial; +458 } +459 +460 public boolean isEmpty() { +461 for (Map.Entry<Long, BitSetNode> entry : map.entrySet()) { +462 if (entry.getValue().isEmpty() == false) { +463 return false; +464 } +465 } +466 return true; +467 } +468 +469 public boolean isUpdated() { +470 for (Map.Entry<Long, BitSetNode> entry : map.entrySet()) { +471 if (entry.getValue().isUpdated() == false) { +472 return false; +473 } +474 } +475 return true; +476 } +