diff options
Diffstat (limited to 'src/classes/com/sun/opengl/impl')
4 files changed, 256 insertions, 58 deletions
diff --git a/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java b/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java index ba4b0cf30..0c4636063 100755 --- a/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java +++ b/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java @@ -49,16 +49,37 @@ public interface BackingStoreManager { public Object allocateBackingStore(int w, int h); public void deleteBackingStore(Object backingStore); - // Notification that movement is starting + /** Notification that expansion of the backing store is about to be + done due to addition of the given rectangle. Gives the manager a + chance to do some compaction and potentially remove old entries + from the backing store, if it acts like a least-recently-used + cache. This method receives as argument the number of attempts + so far to add the given rectangle. Manager should return true if + the RectanglePacker should retry the addition (which may result + in this method being called again, with an increased attempt + number) or false if the RectanglePacker should just expand the + backing store. The caller should not call RectanglePacker.add() + in its preExpand() method. */ + public boolean preExpand(Rect cause, int attemptNumber); + + /** Notification that addition of the given Rect failed because a + maximum size was set in the RectanglePacker and the backing + store could not be expanded. */ + public void additionFailed(Rect cause, int attemptNumber); + + /** Notification that movement is starting. */ public void beginMovement(Object oldBackingStore, Object newBackingStore); - // Can the backing stores be identical? I think so, in the case of - // compacting the existing backing store as opposed to reallocating it... + /** Tells the manager to move the contents of the given rect from + the old location on the old backing store to the new location on + the new backing store. The backing stores can be identical in + the case of compacting the existing backing store instead of + reallocating it. */ public void move(Object oldBackingStore, Rect oldLocation, Object newBackingStore, Rect newLocation); - // Notification that movement is ending + /** Notification that movement is ending. */ public void endMovement(Object oldBackingStore, Object newBackingStore); } diff --git a/src/classes/com/sun/opengl/impl/packrect/Level.java b/src/classes/com/sun/opengl/impl/packrect/Level.java index e7eab9ca7..12a09cd9a 100755 --- a/src/classes/com/sun/opengl/impl/packrect/Level.java +++ b/src/classes/com/sun/opengl/impl/packrect/Level.java @@ -129,8 +129,7 @@ public class Level { freeList.add(candidate); } - if (freeList.isEmpty()) - freeList = null; + coalesceFreeList(); return true; } @@ -148,38 +147,22 @@ public class Level { // to the free list, we can just decrease the nextAddX if (rect.maxX() + 1 == nextAddX) { nextAddX -= rect.w(); - - // Now try to coalesce additional free space at the end of the - // free list - if (freeList != null) { - boolean found = true; - while (found) { - found = false; - for (Iterator iter = freeList.iterator(); iter.hasNext(); ) { - Rect cur = (Rect) iter.next(); - if (cur.maxX() + 1 == nextAddX) { - nextAddX -= cur.w(); - found = true; - freeList.remove(cur); - break; - } - } - } - if (freeList.isEmpty()) - freeList = null; + } else { + if (freeList == null) { + freeList = new ArrayList/*<Rect>*/(); } - - return true; + freeList.add(new Rect(rect.x(), rect.y(), rect.w(), height, null)); + coalesceFreeList(); } - // Else, add the space consumed by this rectangle to the free list - if (freeList == null) { - freeList = new ArrayList/*<Rect>*/(); - } - freeList.add(new Rect(rect.x(), rect.y(), rect.w(), height, null)); return true; } + /** Indicates whether this Level contains no rectangles. */ + public boolean isEmpty() { + return rects.isEmpty(); + } + /** Indicates whether this Level could satisfy an allocation request if it were compacted. */ public boolean couldAllocateIfCompacted(Rect rect) { @@ -211,6 +194,7 @@ public class Level { nextCompactionDest += cur.w(); } nextAddX = nextCompactionDest; + freeList.clear(); manager.endMovement(backingStore, backingStore); } @@ -240,4 +224,52 @@ public class Level { rects.set(i, next); } } + + private void coalesceFreeList() { + if (freeList == null) + return; + if (freeList.isEmpty()) + return; + + // Try to coalesce adjacent free blocks in the free list + Collections.sort(freeList, rectXComparator); + int i = 0; + while (i < freeList.size() - 1) { + Rect r1 = (Rect) freeList.get(i); + Rect r2 = (Rect) freeList.get(i+1); + if (r1.maxX() + 1 == r2.x()) { + // Coalesce r1 and r2 into one block + freeList.remove(i+1); + r1.setSize(r1.w() + r2.w(), r1.h()); + } else { + ++i; + } + } + // See whether the last block bumps up against the addition point + Rect last = (Rect) freeList.get(freeList.size() - 1); + if (last.maxX() + 1 == nextAddX) { + nextAddX -= last.w(); + freeList.remove(freeList.size() - 1); + } + if (freeList.isEmpty()) { + freeList = null; + } + } + + //---------------------------------------------------------------------- + // Debugging functionality + // + + public void dumpFreeSpace() { + int freeListWidth = 0; + for (Iterator iter = freeList.iterator(); iter.hasNext(); ) { + Rect cur = (Rect) iter.next(); + System.err.println(" Free rectangle at " + cur); + freeListWidth += cur.w(); + } + // Add on the remaining space at the end + System.err.println(" Remaining free space " + (width - nextAddX)); + freeListWidth += (width - nextAddX); + System.err.println(" Total free space " + freeListWidth); + } } diff --git a/src/classes/com/sun/opengl/impl/packrect/LevelSet.java b/src/classes/com/sun/opengl/impl/packrect/LevelSet.java index 561a3fe14..97a1f2e74 100755 --- a/src/classes/com/sun/opengl/impl/packrect/LevelSet.java +++ b/src/classes/com/sun/opengl/impl/packrect/LevelSet.java @@ -149,6 +149,39 @@ public class LevelSet { nextAddY += (newHeight - oldHeight); } + /** Gets the used height of the levels in this LevelSet. */ + public int getUsedHeight() { + return nextAddY; + } + + /** Sets the height of this LevelSet. It is only legal to reduce the + height to greater than or equal to the currently used height. */ + public void setHeight(int height) throws IllegalArgumentException { + if (height < getUsedHeight()) { + throw new IllegalArgumentException("May not reduce height below currently used height"); + } + h = height; + } + + /** Returns the vertical fragmentation ratio of this LevelSet. This + is defined as the ratio of the sum of the heights of all + completely empty Levels divided by the overall used height of + the LevelSet. A high vertical fragmentation ratio indicates that + it may be profitable to perform a compaction. */ + public float verticalFragmentationRatio() { + int freeHeight = 0; + int usedHeight = getUsedHeight(); + if (usedHeight == 0) + return 0.0f; + for (Iterator iter = iterator(); iter.hasNext(); ) { + Level level = (Level) iter.next(); + if (level.isEmpty()) { + freeHeight += level.h(); + } + } + return (float) freeHeight / (float) usedHeight; + } + public Iterator iterator() { return levels.iterator(); } @@ -171,4 +204,10 @@ public class LevelSet { level.updateRectangleReferences(); } } + + /** Clears out all Levels stored in this LevelSet. */ + public void clear() { + levels.clear(); + nextAddY = 0; + } } diff --git a/src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java b/src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java index 453f5e1e2..6057f7bb9 100755 --- a/src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java +++ b/src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java @@ -52,6 +52,13 @@ public class RectanglePacker { private Object backingStore; private LevelSet levels; private float EXPANSION_FACTOR = 0.5f; + private float SHRINK_FACTOR = 0.3f; + + private int initialWidth; + private int initialHeight; + + private int maxWidth = -1; + private int maxHeight = -1; static class RectHComparator implements Comparator { public int compare(Object o1, Object o2) { @@ -71,6 +78,8 @@ public class RectanglePacker { int initialHeight) { this.manager = manager; levels = new LevelSet(initialWidth, initialHeight); + this.initialWidth = initialWidth; + this.initialHeight = initialHeight; } public Object getBackingStore() { @@ -81,6 +90,16 @@ public class RectanglePacker { return backingStore; } + /** Sets up a maximum width and height for the backing store. These + are optional and if not specified the backing store will grow as + necessary. Setting up a maximum width and height introduces the + possibility that additions will fail; these are handled with the + BackingStoreManager's allocationFailed notification. */ + public void setMaxSize(int maxWidth, int maxHeight) { + this.maxWidth = maxWidth; + this.maxHeight = maxHeight; + } + /** Decides upon an (x, y) position for the given rectangle (leaving its width and height unchanged) and places it on the backing store. May provoke re-layout of other Rects already added. */ @@ -89,29 +108,89 @@ public class RectanglePacker { if (backingStore == null) backingStore = manager.allocateBackingStore(levels.w(), levels.h()); - // Try to allocate - if (levels.add(rect)) - return; + int attemptNumber = 0; + boolean tryAgain = false; + + do { + // Try to allocate + if (levels.add(rect)) + return; + + // Try to allocate with horizontal compaction + if (levels.compactAndAdd(rect, backingStore, manager)) + return; + + // Let the manager have a chance at potentially evicting some entries + tryAgain = manager.preExpand(rect, attemptNumber++); + } while (tryAgain); + + compactImpl(rect); + + // Retry the addition of the incoming rectangle + add(rect); + // Done + } + + /** Removes the given rectangle from this RectanglePacker. */ + public void remove(Rect rect) { + levels.remove(rect); + } + + /** Visits all Rects contained in this RectanglePacker. */ + public void visit(RectVisitor visitor) { + levels.visit(visitor); + } - // Try to allocate with compaction - if (levels.compactAndAdd(rect, backingStore, manager)) - return; + /** Returns the vertical fragmentation ratio of this + RectanglePacker. This is defined as the ratio of the sum of the + heights of all completely empty Levels divided by the overall + used height of the LevelSet. A high vertical fragmentation ratio + indicates that it may be profitable to perform a compaction. */ + public float verticalFragmentationRatio() { + return levels.verticalFragmentationRatio(); + } - // Have to expand. Need to figure out what direction to go. Prefer - // to expand vertically. Expand horizontally only if rectangle - // being added is too wide. FIXME: may want to consider - // rebalancing the width and height to be more equal if it turns - // out we keep expanding in the vertical direction. + /** Forces a compaction cycle, which typically results in allocating + a new backing store and copying all entries to it. */ + public void compact() { + compactImpl(null); + } + + // The "cause" rect may be null + private void compactImpl(Rect cause) { + // Have to either expand, compact or both. Need to figure out what + // direction to go. Prefer to expand vertically. Expand + // horizontally only if rectangle being added is too wide. FIXME: + // may want to consider rebalancing the width and height to be + // more equal if it turns out we keep expanding in the vertical + // direction. boolean done = false; int newWidth = levels.w(); int newHeight = levels.h(); LevelSet nextLevelSet = null; + int attemptNumber = 0; + boolean needAdditionFailureNotification = false; + while (!done) { - if (rect.w() > newWidth) { - newWidth = rect.w(); - } else { - newHeight = (int) (newHeight * (1.0f + EXPANSION_FACTOR)); + if (cause != null) { + if (cause.w() > newWidth) { + newWidth = cause.w(); + } else { + newHeight = (int) (newHeight * (1.0f + EXPANSION_FACTOR)); + } } + + // Clamp to maximum values + needAdditionFailureNotification = false; + if (maxWidth > 0 && newWidth > maxWidth) { + newWidth = maxWidth; + needAdditionFailureNotification = true; + } + if (maxHeight > 0 && newHeight > maxHeight) { + newHeight = maxHeight; + needAdditionFailureNotification = true; + } + nextLevelSet = new LevelSet(newWidth, newHeight); // Make copies of all existing rectangles @@ -138,7 +217,42 @@ public class RectanglePacker { break; } } + + if (done && cause != null) { + // Try to add the new rectangle as well + if (nextLevelSet.add(cause)) { + // We're OK + } else { + done = false; + } + } + + // Don't send addition failure notifications if we're only doing + // a compaction + if (!done && needAdditionFailureNotification && cause != null) { + manager.additionFailed(cause, attemptNumber); + } + ++attemptNumber; } + + // See whether the implicit compaction that just occurred has + // yielded excess empty space. + if (nextLevelSet.getUsedHeight() > 0 && + nextLevelSet.getUsedHeight() < nextLevelSet.h() * SHRINK_FACTOR) { + int shrunkHeight = Math.max(initialHeight, + (int) (nextLevelSet.getUsedHeight() * (1.0f + EXPANSION_FACTOR))); + if (maxHeight > 0 && shrunkHeight > maxHeight) { + shrunkHeight = maxHeight; + } + nextLevelSet.setHeight(shrunkHeight); + } + + // If we temporarily added the new rectangle to the new LevelSet, + // take it out since we don't "really" add it here but in add(), above + if (cause != null) { + nextLevelSet.remove(cause); + } + // OK, now we have a new layout and a mapping from the old to the // new locations of rectangles on the backing store. Allocate a // new backing store, move the contents over and deallocate the @@ -162,19 +276,11 @@ public class RectanglePacker { // Update to new versions of backing store and LevelSet backingStore = newBackingStore; levels = nextLevelSet; - // Retry the addition of the incoming rectangle - add(rect); - // Done } - /** Removes the given rectangle from this RectanglePacker. */ - public void remove(Rect rect) { - levels.remove(rect); - } - - /** Visits all Rects contained in this RectanglePacker. */ - public void visit(RectVisitor visitor) { - levels.visit(visitor); + /** Clears all Rects contained in this RectanglePacker. */ + public void clear() { + levels.clear(); } /** Disposes the backing store allocated by the |