Return-Path: X-Original-To: archive-asf-public-internal@cust-asf2.ponee.io Delivered-To: archive-asf-public-internal@cust-asf2.ponee.io Received: from cust-asf.ponee.io (cust-asf.ponee.io [163.172.22.183]) by cust-asf2.ponee.io (Postfix) with ESMTP id 9839B200CB7 for ; Fri, 30 Jun 2017 17:01:01 +0200 (CEST) Received: by cust-asf.ponee.io (Postfix) id 9624A160BEB; Fri, 30 Jun 2017 15:01:01 +0000 (UTC) Delivered-To: archive-asf-public@cust-asf.ponee.io Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by cust-asf.ponee.io (Postfix) with SMTP id 9D796160BF6 for ; Fri, 30 Jun 2017 17:00:59 +0200 (CEST) Received: (qmail 27448 invoked by uid 500); 30 Jun 2017 15:00:54 -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 26108 invoked by uid 99); 30 Jun 2017 15:00:53 -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; Fri, 30 Jun 2017 15:00:53 +0000 Received: by git1-us-west.apache.org (ASF Mail Server at git1-us-west.apache.org, from userid 33) id 82CD8E965C; Fri, 30 Jun 2017 15:00:52 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: git-site-role@apache.org To: commits@hbase.apache.org Date: Fri, 30 Jun 2017 15:01:03 -0000 Message-Id: In-Reply-To: <6802f6ed0a334890adcc73f75ef88cd2@git.apache.org> References: <6802f6ed0a334890adcc73f75ef88cd2@git.apache.org> X-Mailer: ASF-Git Admin Mailer Subject: [13/32] hbase-site git commit: Published site at 82d554e3783372cc6b05489452c815b57c06f6cd. archived-at: Fri, 30 Jun 2017 15:01:01 -0000 http://git-wip-us.apache.org/repos/asf/hbase-site/blob/1b5f3a4b/devapidocs/src-html/org/apache/hadoop/hbase/procedure2/store/wal/ProcedureWALFormatReader.EntryIterator.html ---------------------------------------------------------------------- diff --git a/devapidocs/src-html/org/apache/hadoop/hbase/procedure2/store/wal/ProcedureWALFormatReader.EntryIterator.html b/devapidocs/src-html/org/apache/hadoop/hbase/procedure2/store/wal/ProcedureWALFormatReader.EntryIterator.html index b1f9eeb..0b1b520 100644 --- a/devapidocs/src-html/org/apache/hadoop/hbase/procedure2/store/wal/ProcedureWALFormatReader.EntryIterator.html +++ b/devapidocs/src-html/org/apache/hadoop/hbase/procedure2/store/wal/ProcedureWALFormatReader.EntryIterator.html @@ -491,392 +491,396 @@ 483 */ 484 private static boolean isIncreasing(ProcedureProtos.Procedure current, 485 ProcedureProtos.Procedure candidate) { -486 boolean increasing = current.getStackIdCount() <= candidate.getStackIdCount() && -487 current.getLastUpdate() <= candidate.getLastUpdate(); -488 if (!increasing) { -489 LOG.warn("NOT INCREASING! current=" + current + ", candidate=" + candidate); -490 } -491 return increasing; -492 } -493 -494 public boolean remove(long procId) { -495 trackProcIds(procId); -496 Entry entry = removeFromMap(procId); -497 if (entry != null) { -498 unlinkFromReplayList(entry); -499 unlinkFromLinkList(entry); -500 return true; -501 } -502 return false; -503 } -504 -505 private void trackProcIds(long procId) { -506 minProcId = Math.min(minProcId, procId); -507 maxProcId = Math.max(maxProcId, procId); -508 } -509 -510 public long getMinProcId() { -511 return minProcId; +486 // Check that the procedures we see are 'increasing'. We used to compare +487 // procedure id first and then update time but it can legitimately go backwards if the +488 // procedure is failed or rolled back so that was unreliable. Was going to compare +489 // state but lets see if comparing update time enough (unfortunately this issue only +490 // seen under load...) +491 boolean increasing = current.getLastUpdate() <= candidate.getLastUpdate(); +492 if (!increasing) { +493 LOG.warn("NOT INCREASING! current=" + current + ", candidate=" + candidate); +494 } +495 return increasing; +496 } +497 +498 public boolean remove(long procId) { +499 trackProcIds(procId); +500 Entry entry = removeFromMap(procId); +501 if (entry != null) { +502 unlinkFromReplayList(entry); +503 unlinkFromLinkList(entry); +504 return true; +505 } +506 return false; +507 } +508 +509 private void trackProcIds(long procId) { +510 minProcId = Math.min(minProcId, procId); +511 maxProcId = Math.max(maxProcId, procId); 512 } 513 -514 public long getMaxProcId() { -515 return maxProcId; +514 public long getMinProcId() { +515 return minProcId; 516 } 517 -518 public boolean contains(long procId) { -519 return getProcedure(procId) != null; +518 public long getMaxProcId() { +519 return maxProcId; 520 } 521 -522 public boolean isEmpty() { -523 return replayOrderHead == null; +522 public boolean contains(long procId) { +523 return getProcedure(procId) != null; 524 } 525 -526 public void clear() { -527 for (int i = 0; i < procedureMap.length; ++i) { -528 procedureMap[i] = null; -529 } -530 replayOrderHead = null; -531 replayOrderTail = null; -532 rootHead = null; -533 childUnlinkedHead = null; -534 minProcId = Long.MAX_VALUE; -535 maxProcId = Long.MIN_VALUE; -536 } -537 -538 /* -539 * Merges two WalProcedureMap, -540 * the target is the "global" map, the source is the "local" map. -541 * - The entries in the hashtables are guaranteed to be unique. -542 * On replay we don't load procedures that already exist in the "global" -543 * map (the one we are merging the "local" in to). -544 * - The replayOrderList of the "local" nao will be appended to the "global" -545 * map replay list. -546 * - The "local" map will be cleared at the end of the operation. -547 */ -548 public void mergeTail(WalProcedureMap other) { -549 for (Entry p = other.replayOrderHead; p != null; p = p.replayNext) { -550 int slotIndex = getMapSlot(p.getProcId()); -551 p.hashNext = procedureMap[slotIndex]; -552 procedureMap[slotIndex] = p; -553 } -554 -555 if (replayOrderHead == null) { -556 replayOrderHead = other.replayOrderHead; -557 replayOrderTail = other.replayOrderTail; -558 rootHead = other.rootHead; -559 childUnlinkedHead = other.childUnlinkedHead; -560 } else { -561 // append replay list -562 assert replayOrderTail.replayNext == null; -563 assert other.replayOrderHead.replayPrev == null; -564 replayOrderTail.replayNext = other.replayOrderHead; -565 other.replayOrderHead.replayPrev = replayOrderTail; -566 replayOrderTail = other.replayOrderTail; -567 -568 // merge rootHead -569 if (rootHead == null) { -570 rootHead = other.rootHead; -571 } else if (other.rootHead != null) { -572 Entry otherTail = findLinkListTail(other.rootHead); -573 otherTail.linkNext = rootHead; -574 rootHead.linkPrev = otherTail; -575 rootHead = other.rootHead; -576 } -577 -578 // merge childUnlinkedHead -579 if (childUnlinkedHead == null) { -580 childUnlinkedHead = other.childUnlinkedHead; -581 } else if (other.childUnlinkedHead != null) { -582 Entry otherTail = findLinkListTail(other.childUnlinkedHead); -583 otherTail.linkNext = childUnlinkedHead; -584 childUnlinkedHead.linkPrev = otherTail; -585 childUnlinkedHead = other.childUnlinkedHead; -586 } -587 } -588 maxProcId = Math.max(maxProcId, other.maxProcId); -589 minProcId = Math.max(minProcId, other.minProcId); -590 -591 other.clear(); -592 } -593 -594 /* -595 * Returns an EntryIterator with the list of procedures ready -596 * to be added to the executor. -597 * A Procedure is ready if its children and parent are ready. -598 */ -599 public EntryIterator fetchReady() { -600 buildGraph(); -601 -602 Entry readyHead = null; -603 Entry readyTail = null; -604 Entry p = replayOrderHead; -605 while (p != null) { -606 Entry next = p.replayNext; -607 if (p.isReady()) { -608 unlinkFromReplayList(p); -609 if (readyTail != null) { -610 readyTail.replayNext = p; -611 p.replayPrev = readyTail; -612 } else { -613 p.replayPrev = null; -614 readyHead = p; -615 } -616 readyTail = p; -617 p.replayNext = null; -618 } -619 p = next; -620 } -621 // we need the hash-table lookups for parents, so this must be done -622 // out of the loop where we check isReadyToRun() -623 for (p = readyHead; p != null; p = p.replayNext) { -624 removeFromMap(p.getProcId()); -625 unlinkFromLinkList(p); -626 } -627 return readyHead != null ? new EntryIterator(readyHead) : null; -628 } -629 -630 /* -631 * Drain this map and return all procedures in it. -632 */ -633 public EntryIterator fetchAll() { -634 Entry head = replayOrderHead; -635 for (Entry p = head; p != null; p = p.replayNext) { -636 removeFromMap(p.getProcId()); -637 } -638 for (int i = 0; i < procedureMap.length; ++i) { -639 assert procedureMap[i] == null : "map not empty i=" + i; -640 } -641 replayOrderHead = null; -642 replayOrderTail = null; -643 childUnlinkedHead = null; -644 rootHead = null; -645 return head != null ? new EntryIterator(head) : null; -646 } -647 -648 private void buildGraph() { -649 Entry p = childUnlinkedHead; -650 while (p != null) { -651 Entry next = p.linkNext; -652 Entry rootProc = getRootProcedure(p); -653 if (rootProc != null) { -654 rootProc.childHead = addToLinkList(p, rootProc.childHead); -655 } -656 p = next; -657 } -658 -659 for (p = rootHead; p != null; p = p.linkNext) { -660 checkReadyToRun(p); +526 public boolean isEmpty() { +527 return replayOrderHead == null; +528 } +529 +530 public void clear() { +531 for (int i = 0; i < procedureMap.length; ++i) { +532 procedureMap[i] = null; +533 } +534 replayOrderHead = null; +535 replayOrderTail = null; +536 rootHead = null; +537 childUnlinkedHead = null; +538 minProcId = Long.MAX_VALUE; +539 maxProcId = Long.MIN_VALUE; +540 } +541 +542 /* +543 * Merges two WalProcedureMap, +544 * the target is the "global" map, the source is the "local" map. +545 * - The entries in the hashtables are guaranteed to be unique. +546 * On replay we don't load procedures that already exist in the "global" +547 * map (the one we are merging the "local" in to). +548 * - The replayOrderList of the "local" nao will be appended to the "global" +549 * map replay list. +550 * - The "local" map will be cleared at the end of the operation. +551 */ +552 public void mergeTail(WalProcedureMap other) { +553 for (Entry p = other.replayOrderHead; p != null; p = p.replayNext) { +554 int slotIndex = getMapSlot(p.getProcId()); +555 p.hashNext = procedureMap[slotIndex]; +556 procedureMap[slotIndex] = p; +557 } +558 +559 if (replayOrderHead == null) { +560 replayOrderHead = other.replayOrderHead; +561 replayOrderTail = other.replayOrderTail; +562 rootHead = other.rootHead; +563 childUnlinkedHead = other.childUnlinkedHead; +564 } else { +565 // append replay list +566 assert replayOrderTail.replayNext == null; +567 assert other.replayOrderHead.replayPrev == null; +568 replayOrderTail.replayNext = other.replayOrderHead; +569 other.replayOrderHead.replayPrev = replayOrderTail; +570 replayOrderTail = other.replayOrderTail; +571 +572 // merge rootHead +573 if (rootHead == null) { +574 rootHead = other.rootHead; +575 } else if (other.rootHead != null) { +576 Entry otherTail = findLinkListTail(other.rootHead); +577 otherTail.linkNext = rootHead; +578 rootHead.linkPrev = otherTail; +579 rootHead = other.rootHead; +580 } +581 +582 // merge childUnlinkedHead +583 if (childUnlinkedHead == null) { +584 childUnlinkedHead = other.childUnlinkedHead; +585 } else if (other.childUnlinkedHead != null) { +586 Entry otherTail = findLinkListTail(other.childUnlinkedHead); +587 otherTail.linkNext = childUnlinkedHead; +588 childUnlinkedHead.linkPrev = otherTail; +589 childUnlinkedHead = other.childUnlinkedHead; +590 } +591 } +592 maxProcId = Math.max(maxProcId, other.maxProcId); +593 minProcId = Math.max(minProcId, other.minProcId); +594 +595 other.clear(); +596 } +597 +598 /* +599 * Returns an EntryIterator with the list of procedures ready +600 * to be added to the executor. +601 * A Procedure is ready if its children and parent are ready. +602 */ +603 public EntryIterator fetchReady() { +604 buildGraph(); +605 +606 Entry readyHead = null; +607 Entry readyTail = null; +608 Entry p = replayOrderHead; +609 while (p != null) { +610 Entry next = p.replayNext; +611 if (p.isReady()) { +612 unlinkFromReplayList(p); +613 if (readyTail != null) { +614 readyTail.replayNext = p; +615 p.replayPrev = readyTail; +616 } else { +617 p.replayPrev = null; +618 readyHead = p; +619 } +620 readyTail = p; +621 p.replayNext = null; +622 } +623 p = next; +624 } +625 // we need the hash-table lookups for parents, so this must be done +626 // out of the loop where we check isReadyToRun() +627 for (p = readyHead; p != null; p = p.replayNext) { +628 removeFromMap(p.getProcId()); +629 unlinkFromLinkList(p); +630 } +631 return readyHead != null ? new EntryIterator(readyHead) : null; +632 } +633 +634 /* +635 * Drain this map and return all procedures in it. +636 */ +637 public EntryIterator fetchAll() { +638 Entry head = replayOrderHead; +639 for (Entry p = head; p != null; p = p.replayNext) { +640 removeFromMap(p.getProcId()); +641 } +642 for (int i = 0; i < procedureMap.length; ++i) { +643 assert procedureMap[i] == null : "map not empty i=" + i; +644 } +645 replayOrderHead = null; +646 replayOrderTail = null; +647 childUnlinkedHead = null; +648 rootHead = null; +649 return head != null ? new EntryIterator(head) : null; +650 } +651 +652 private void buildGraph() { +653 Entry p = childUnlinkedHead; +654 while (p != null) { +655 Entry next = p.linkNext; +656 Entry rootProc = getRootProcedure(p); +657 if (rootProc != null) { +658 rootProc.childHead = addToLinkList(p, rootProc.childHead); +659 } +660 p = next; 661 } -662 } -663 -664 private Entry getRootProcedure(Entry entry) { -665 while (entry != null && entry.hasParent()) { -666 entry = getProcedure(entry.getParentId()); -667 } -668 return entry; -669 } -670 -671 /* -672 * (see the comprehensive explanation in the beginning of the file) -673 * A Procedure is ready when parent and children are ready. -674 * "ready" means that we all the information that we need in-memory. -675 * -676 * Example-1: -677 * We have two WALs, we start reading from the newest (wal-2) -678 * wal-2 | C B | -679 * wal-1 | A B C | -680 * -681 * If C and B don't depend on A (A is not the parent), we can start them -682 * before reading wal-1. If B is the only one with parent A we can start C. -683 * We have to read one more WAL before being able to start B. +662 +663 for (p = rootHead; p != null; p = p.linkNext) { +664 checkReadyToRun(p); +665 } +666 } +667 +668 private Entry getRootProcedure(Entry entry) { +669 while (entry != null && entry.hasParent()) { +670 entry = getProcedure(entry.getParentId()); +671 } +672 return entry; +673 } +674 +675 /* +676 * (see the comprehensive explanation in the beginning of the file) +677 * A Procedure is ready when parent and children are ready. +678 * "ready" means that we all the information that we need in-memory. +679 * +680 * Example-1: +681 * We have two WALs, we start reading from the newest (wal-2) +682 * wal-2 | C B | +683 * wal-1 | A B C | 684 * -685 * How do we know with the only information in B that we are not ready. -686 * - easy case, the parent is missing from the global map -687 * - more complex case we look at the Stack IDs. +685 * If C and B don't depend on A (A is not the parent), we can start them +686 * before reading wal-1. If B is the only one with parent A we can start C. +687 * We have to read one more WAL before being able to start B. 688 * -689 * The Stack-IDs are added to the procedure order as an incremental index -690 * tracking how many times that procedure was executed, which is equivalent -691 * to the number of times we wrote the procedure to the WAL. -692 * In the example above: -693 * wal-2: B has stackId = [1, 2] -694 * wal-1: B has stackId = [1] -695 * wal-1: A has stackId = [0] -696 * -697 * Since we know that the Stack-IDs are incremental for a Procedure, -698 * we notice that there is a gap in the stackIds of B, so something was -699 * executed before. -700 * To identify when a Procedure is ready we do the sum of the stackIds of -701 * the procedure and the parent. if the stackIdSum is equal to the -702 * sum of {1..maxStackId} then everything we need is available. -703 * -704 * Example-2 -705 * wal-2 | A | A stackIds = [0, 2] -706 * wal-1 | A B | B stackIds = [1] +689 * How do we know with the only information in B that we are not ready. +690 * - easy case, the parent is missing from the global map +691 * - more complex case we look at the Stack IDs. +692 * +693 * The Stack-IDs are added to the procedure order as an incremental index +694 * tracking how many times that procedure was executed, which is equivalent +695 * to the number of times we wrote the procedure to the WAL. +696 * In the example above: +697 * wal-2: B has stackId = [1, 2] +698 * wal-1: B has stackId = [1] +699 * wal-1: A has stackId = [0] +700 * +701 * Since we know that the Stack-IDs are incremental for a Procedure, +702 * we notice that there is a gap in the stackIds of B, so something was +703 * executed before. +704 * To identify when a Procedure is ready we do the sum of the stackIds of +705 * the procedure and the parent. if the stackIdSum is equal to the +706 * sum of {1..maxStackId} then everything we need is available. 707 * -708 * There is a gap between A stackIds so something was executed in between. -709 */ -710 private boolean checkReadyToRun(Entry rootEntry) { -711 assert !rootEntry.hasParent() : "expected root procedure, got " + rootEntry; -712 -713 if (rootEntry.isFinished()) { -714 // If the root procedure is finished, sub-procedures should be gone -715 if (rootEntry.childHead != null) { -716 LOG.error("unexpected active children for root-procedure: " + rootEntry); -717 for (Entry p = rootEntry.childHead; p != null; p = p.linkNext) { -718 LOG.error("unexpected active children: " + p); -719 } -720 } -721 -722 assert rootEntry.childHead == null : "unexpected children on root completion. " + rootEntry; -723 rootEntry.ready = true; -724 return true; -725 } -726 -727 int stackIdSum = 0; -728 int maxStackId = 0; -729 for (int i = 0; i < rootEntry.proto.getStackIdCount(); ++i) { -730 int stackId = 1 + rootEntry.proto.getStackId(i); -731 maxStackId = Math.max(maxStackId, stackId); -732 stackIdSum += stackId; -733 if (LOG.isTraceEnabled()) { -734 LOG.trace("stackId=" + stackId + " stackIdSum=" + stackIdSum + -735 " maxStackid=" + maxStackId + " " + rootEntry); -736 } -737 } -738 -739 for (Entry p = rootEntry.childHead; p != null; p = p.linkNext) { -740 for (int i = 0; i < p.proto.getStackIdCount(); ++i) { -741 int stackId = 1 + p.proto.getStackId(i); -742 maxStackId = Math.max(maxStackId, stackId); -743 stackIdSum += stackId; -744 if (LOG.isTraceEnabled()) { -745 LOG.trace("stackId=" + stackId + " stackIdSum=" + stackIdSum + -746 " maxStackid=" + maxStackId + " " + p); -747 } -748 } -749 } -750 // The cmpStackIdSum is this formula for finding the sum of a series of numbers: -751 // http://www.wikihow.com/Sum-the-Integers-from-1-to-N#/Image:Sum-the-Integers-from-1-to-N-Step-2-Version-3.jpg -752 final int cmpStackIdSum = (maxStackId * (maxStackId + 1) / 2); -753 if (cmpStackIdSum == stackIdSum) { -754 rootEntry.ready = true; -755 for (Entry p = rootEntry.childHead; p != null; p = p.linkNext) { -756 p.ready = true; -757 } -758 return true; -759 } -760 return false; -761 } -762 -763 private void unlinkFromReplayList(Entry entry) { -764 if (replayOrderHead == entry) { -765 replayOrderHead = entry.replayNext; -766 } -767 if (replayOrderTail == entry) { -768 replayOrderTail = entry.replayPrev; -769 } -770 if (entry.replayPrev != null) { -771 entry.replayPrev.replayNext = entry.replayNext; -772 } -773 if (entry.replayNext != null) { -774 entry.replayNext.replayPrev = entry.replayPrev; -775 } -776 } -777 -778 private void addToReplayList(final Entry entry) { -779 unlinkFromReplayList(entry); -780 entry.replayNext = replayOrderHead; -781 entry.replayPrev = null; -782 if (replayOrderHead != null) { -783 replayOrderHead.replayPrev = entry; -784 } else { -785 replayOrderTail = entry; -786 } -787 replayOrderHead = entry; -788 } -789 -790 private void unlinkFromLinkList(Entry entry) { -791 if (entry == rootHead) { -792 rootHead = entry.linkNext; -793 } else if (entry == childUnlinkedHead) { -794 childUnlinkedHead = entry.linkNext; -795 } -796 if (entry.linkPrev != null) { -797 entry.linkPrev.linkNext = entry.linkNext; -798 } -799 if (entry.linkNext != null) { -800 entry.linkNext.linkPrev = entry.linkPrev; -801 } -802 } -803 -804 private Entry addToLinkList(Entry entry, Entry linkHead) { -805 unlinkFromLinkList(entry); -806 entry.linkNext = linkHead; -807 entry.linkPrev = null; -808 if (linkHead != null) { -809 linkHead.linkPrev = entry; -810 } -811 return entry; -812 } -813 -814 private Entry findLinkListTail(Entry linkHead) { -815 Entry tail = linkHead; -816 while (tail.linkNext != null) { -817 tail = tail.linkNext; -818 } -819 return tail; -820 } -821 -822 private Entry addToMap(final long procId, final boolean hasParent) { -823 int slotIndex = getMapSlot(procId); -824 Entry entry = getProcedure(slotIndex, procId); -825 if (entry != null) return entry; -826 -827 entry = new Entry(procedureMap[slotIndex]); -828 procedureMap[slotIndex] = entry; -829 return entry; -830 } -831 -832 private Entry removeFromMap(final long procId) { -833 int slotIndex = getMapSlot(procId); -834 Entry prev = null; -835 Entry entry = procedureMap[slotIndex]; -836 while (entry != null) { -837 if (procId == entry.getProcId()) { -838 if (prev != null) { -839 prev.hashNext = entry.hashNext; -840 } else { -841 procedureMap[slotIndex] = entry.hashNext; -842 } -843 entry.hashNext = null; -844 return entry; -845 } -846 prev = entry; -847 entry = entry.hashNext; -848 } -849 return null; -850 } -851 -852 private Entry getProcedure(final long procId) { -853 return getProcedure(getMapSlot(procId), procId); +708 * Example-2 +709 * wal-2 | A | A stackIds = [0, 2] +710 * wal-1 | A B | B stackIds = [1] +711 * +712 * There is a gap between A stackIds so something was executed in between. +713 */ +714 private boolean checkReadyToRun(Entry rootEntry) { +715 assert !rootEntry.hasParent() : "expected root procedure, got " + rootEntry; +716 +717 if (rootEntry.isFinished()) { +718 // If the root procedure is finished, sub-procedures should be gone +719 if (rootEntry.childHead != null) { +720 LOG.error("unexpected active children for root-procedure: " + rootEntry); +721 for (Entry p = rootEntry.childHead; p != null; p = p.linkNext) { +722 LOG.error("unexpected active children: " + p); +723 } +724 } +725 +726 assert rootEntry.childHead == null : "unexpected children on root completion. " + rootEntry; +727 rootEntry.ready = true; +728 return true; +729 } +730 +731 int stackIdSum = 0; +732 int maxStackId = 0; +733 for (int i = 0; i < rootEntry.proto.getStackIdCount(); ++i) { +734 int stackId = 1 + rootEntry.proto.getStackId(i); +735 maxStackId = Math.max(maxStackId, stackId); +736 stackIdSum += stackId; +737 if (LOG.isTraceEnabled()) { +738 LOG.trace("stackId=" + stackId + " stackIdSum=" + stackIdSum + +739 " maxStackid=" + maxStackId + " " + rootEntry); +740 } +741 } +742 +743 for (Entry p = rootEntry.childHead; p != null; p = p.linkNext) { +744 for (int i = 0; i < p.proto.getStackIdCount(); ++i) { +745 int stackId = 1 + p.proto.getStackId(i); +746 maxStackId = Math.max(maxStackId, stackId); +747 stackIdSum += stackId; +748 if (LOG.isTraceEnabled()) { +749 LOG.trace("stackId=" + stackId + " stackIdSum=" + stackIdSum + +750 " maxStackid=" + maxStackId + " " + p); +751 } +752 } +753 } +754 // The cmpStackIdSum is this formula for finding the sum of a series of numbers: +755 // http://www.wikihow.com/Sum-the-Integers-from-1-to-N#/Image:Sum-the-Integers-from-1-to-N-Step-2-Version-3.jpg +756 final int cmpStackIdSum = (maxStackId * (maxStackId + 1) / 2); +757 if (cmpStackIdSum == stackIdSum) { +758 rootEntry.ready = true; +759 for (Entry p = rootEntry.childHead; p != null; p = p.linkNext) { +760 p.ready = true; +761 } +762 return true; +763 } +764 return false; +765 } +766 +767 private void unlinkFromReplayList(Entry entry) { +768 if (replayOrderHead == entry) { +769 replayOrderHead = entry.replayNext; +770 } +771 if (replayOrderTail == entry) { +772 replayOrderTail = entry.replayPrev; +773 } +774 if (entry.replayPrev != null) { +775 entry.replayPrev.replayNext = entry.replayNext; +776 } +777 if (entry.replayNext != null) { +778 entry.replayNext.replayPrev = entry.replayPrev; +779 } +780 } +781 +782 private void addToReplayList(final Entry entry) { +783 unlinkFromReplayList(entry); +784 entry.replayNext = replayOrderHead; +785 entry.replayPrev = null; +786 if (replayOrderHead != null) { +787 replayOrderHead.replayPrev = entry; +788 } else { +789 replayOrderTail = entry; +790 } +791 replayOrderHead = entry; +792 } +793 +794 private void unlinkFromLinkList(Entry entry) { +795 if (entry == rootHead) { +796 rootHead = entry.linkNext; +797 } else if (entry == childUnlinkedHead) { +798 childUnlinkedHead = entry.linkNext; +799 } +800 if (entry.linkPrev != null) { +801 entry.linkPrev.linkNext = entry.linkNext; +802 } +803 if (entry.linkNext != null) { +804 entry.linkNext.linkPrev = entry.linkPrev; +805 } +806 } +807 +808 private Entry addToLinkList(Entry entry, Entry linkHead) { +809 unlinkFromLinkList(entry); +810 entry.linkNext = linkHead; +811 entry.linkPrev = null; +812 if (linkHead != null) { +813 linkHead.linkPrev = entry; +814 } +815 return entry; +816 } +817 +818 private Entry findLinkListTail(Entry linkHead) { +819 Entry tail = linkHead; +820 while (tail.linkNext != null) { +821 tail = tail.linkNext; +822 } +823 return tail; +824 } +825 +826 private Entry addToMap(final long procId, final boolean hasParent) { +827 int slotIndex = getMapSlot(procId); +828 Entry entry = getProcedure(slotIndex, procId); +829 if (entry != null) return entry; +830 +831 entry = new Entry(procedureMap[slotIndex]); +832 procedureMap[slotIndex] = entry; +833 return entry; +834 } +835 +836 private Entry removeFromMap(final long procId) { +837 int slotIndex = getMapSlot(procId); +838 Entry prev = null; +839 Entry entry = procedureMap[slotIndex]; +840 while (entry != null) { +841 if (procId == entry.getProcId()) { +842 if (prev != null) { +843 prev.hashNext = entry.hashNext; +844 } else { +845 procedureMap[slotIndex] = entry.hashNext; +846 } +847 entry.hashNext = null; +848 return entry; +849 } +850 prev = entry; +851 entry = entry.hashNext; +852 } +853 return null; 854 } 855 -856 private Entry getProcedure(final int slotIndex, final long procId) { -857 Entry entry = procedureMap[slotIndex]; -858 while (entry != null) { -859 if (procId == entry.getProcId()) { -860 return entry; -861 } -862 entry = entry.hashNext; -863 } -864 return null; -865 } -866 -867 private int getMapSlot(final long procId) { -868 return (int)(Procedure.getProcIdHashCode(procId) % procedureMap.length); +856 private Entry getProcedure(final long procId) { +857 return getProcedure(getMapSlot(procId), procId); +858 } +859 +860 private Entry getProcedure(final int slotIndex, final long procId) { +861 Entry entry = procedureMap[slotIndex]; +862 while (entry != null) { +863 if (procId == entry.getProcId()) { +864 return entry; +865 } +866 entry = entry.hashNext; +867 } +868 return null; 869 } -870 } -871} +870 +871 private int getMapSlot(final long procId) { +872 return (int)(Procedure.getProcIdHashCode(procId) % procedureMap.length); +873 } +874 } +875}