001: /*
002: * ====================================================================
003: * Copyright (c) 2004-2008 TMate Software Ltd. All rights reserved.
004: *
005: * This software is licensed as described in the file COPYING, which
006: * you should have received as part of this distribution. The terms
007: * are also available at http://svnkit.com/license.html
008: * If newer versions of this license are posted there, you may use a
009: * newer version instead, at your option.
010: * ====================================================================
011: */
012: package org.tmatesoft.svn.core.internal.delta;
013:
014: /**
015: * @version 1.1.1
016: * @author TMate Software Ltd.
017: */
018: public class SVNRangeTree {
019:
020: private SVNRangeTreeNode myRoot = null;
021:
022: private SVNRangeTreeNode myFreeTreeNodes;
023: private SVNRangeTreeNode myAllocatedTreeNodes;
024: private SVNRangeListNode myFreeListNodes;
025:
026: public static class SVNRangeTreeNode {
027:
028: public SVNRangeTreeNode(int offset, int limit, int target) {
029: this .offset = offset;
030: this .limit = limit;
031: this .targetOffset = target;
032: }
033:
034: public String toString() {
035: String str = offset + ":" + limit + ":" + targetOffset;
036: return str;
037: }
038:
039: public int offset;
040: public int limit;
041: public int targetOffset;
042:
043: public SVNRangeTreeNode left;
044: public SVNRangeTreeNode right;
045: public SVNRangeTreeNode prev;
046: public SVNRangeTreeNode next;
047:
048: public SVNRangeTreeNode nextFree;
049: }
050:
051: private SVNRangeTreeNode allocateTreeNode(int offset, int limit,
052: int target) {
053: if (myFreeTreeNodes == null) {
054: SVNRangeTreeNode node = new SVNRangeTreeNode(offset, limit,
055: target);
056: node.nextFree = myAllocatedTreeNodes;
057: myAllocatedTreeNodes = node;
058: return node;
059: }
060: SVNRangeTreeNode node = myFreeTreeNodes;
061: myFreeTreeNodes = node.nextFree;
062: node.left = node.right = node.next = node.prev = null;
063: node.offset = offset;
064: node.limit = limit;
065: node.targetOffset = target;
066:
067: // make it head of the allocated list.
068: node.nextFree = myAllocatedTreeNodes;
069: myAllocatedTreeNodes = node;
070: return node;
071: }
072:
073: private void freeTreeNode(SVNRangeTreeNode node) {
074: if (node.next != null) {
075: node.next.prev = node.prev;
076: node.next = null;
077: }
078: if (node.prev != null) {
079: node.prev.next = node.next;
080: node.prev = null;
081: }
082: // remove if from the allocated list, it has to be there.
083: if (myAllocatedTreeNodes == node) {
084: myAllocatedTreeNodes = myAllocatedTreeNodes.nextFree;
085: } else {
086: SVNRangeTreeNode allocated = myAllocatedTreeNodes;
087: while (allocated.nextFree != node) {
088: allocated = allocated.nextFree;
089: }
090: allocated.nextFree = node.nextFree;
091: }
092: // make it head of the free nodes list.
093: node.nextFree = myFreeTreeNodes;
094: myFreeTreeNodes = node;
095: }
096:
097: private SVNRangeListNode allocateListNode(int kind, int offset,
098: int limit, int target) {
099: if (myFreeListNodes == null) {
100: return new SVNRangeListNode(kind, offset, limit, target);
101: }
102: SVNRangeListNode node = myFreeListNodes;
103: myFreeListNodes = node.next;
104: node.offset = offset;
105: node.limit = limit;
106: node.targetOffset = target;
107: node.kind = kind;
108: node.prev = node.next = null;
109: node.head = node;
110: return node;
111: }
112:
113: public void disposeList(SVNRangeListNode head) {
114: SVNRangeListNode n = head;
115: while (head.next != null) {
116: head = head.next;
117: }
118: head.next = myFreeListNodes;
119: myFreeListNodes = n;
120: }
121:
122: public void dispose() {
123: SVNRangeTreeNode node = myFreeTreeNodes;
124: if (node == null) {
125: myFreeTreeNodes = myAllocatedTreeNodes;
126: } else {
127: while (node.nextFree != null) {
128: node = node.nextFree;
129: }
130: node.nextFree = myAllocatedTreeNodes;
131: }
132: myAllocatedTreeNodes = null;
133: myRoot = null;
134: }
135:
136: public static class SVNRangeListNode {
137:
138: public static int FROM_SOURCE = 0;
139: public static int FROM_TARGET = 1;
140:
141: public SVNRangeListNode(int kind, int offset, int limit,
142: int target) {
143: this .kind = kind;
144: this .offset = offset;
145: this .limit = limit;
146: this .targetOffset = target;
147: this .head = this ;
148: }
149:
150: public SVNRangeListNode append(SVNRangeListNode node) {
151: this .next = node;
152: node.prev = this ;
153: node.head = this .head;
154: return node;
155: }
156:
157: public int kind;
158: public int offset;
159: public int limit;
160: public int targetOffset;
161:
162: public SVNRangeListNode prev;
163: public SVNRangeListNode next;
164: public SVNRangeListNode head;
165: }
166:
167: public SVNRangeListNode buildRangeList(int offset, int limit) {
168: SVNRangeListNode tail = null;
169: SVNRangeTreeNode node = myRoot;
170:
171: while (offset < limit) {
172: if (node == null) {
173: return appendToRangeList(SVNRangeListNode.FROM_SOURCE,
174: offset, limit, 0, tail);
175: }
176:
177: if (offset < node.offset) {
178: if (limit <= node.offset) {
179: return appendToRangeList(
180: SVNRangeListNode.FROM_SOURCE, offset,
181: limit, 0, tail);
182: }
183: tail = appendToRangeList(SVNRangeListNode.FROM_SOURCE,
184: offset, node.offset, 0, tail);
185: offset = node.offset;
186: } else {
187: if (offset >= node.limit) {
188: node = node.next;
189: } else {
190: int targetOffset = offset - node.offset
191: + node.targetOffset;
192: if (limit <= node.limit) {
193: return appendToRangeList(
194: SVNRangeListNode.FROM_TARGET, offset,
195: limit, targetOffset, tail);
196: }
197: tail = appendToRangeList(
198: SVNRangeListNode.FROM_TARGET, offset,
199: node.limit, targetOffset, tail);
200: offset = node.limit;
201: node = node.next;
202: }
203: }
204: }
205: SVNDeltaCombiner.assertCondition(false, "assert #6");
206: return tail;
207: }
208:
209: private SVNRangeListNode appendToRangeList(int kind, int offset,
210: int limit, int tOffset, SVNRangeListNode tail) {
211: if (tail == null) {
212: return allocateListNode(kind, offset, limit, tOffset);
213: }
214: return tail.append(allocateListNode(kind, offset, limit,
215: tOffset));
216: }
217:
218: private SVNRangeTreeNode myScratchNode = new SVNRangeTreeNode(0, 0,
219: 0);
220:
221: public void splay(int offset) {
222: if (myRoot == null) {
223: return;
224: }
225: SVNRangeTreeNode root = myRoot;
226: SVNRangeTreeNode scratch = myScratchNode;
227: scratch.left = scratch.right = null;
228: SVNRangeTreeNode left = scratch;
229: SVNRangeTreeNode right = scratch;
230:
231: while (true) {
232: if (offset < root.offset) {
233: if (root.left == null) {
234: break;
235: }
236: if (offset < root.left.offset) {
237: SVNRangeTreeNode node = root.left;
238: root.left = node.right;
239: node.right = root;
240: root = node;
241: if (root.left == null) {
242: break;
243: }
244: }
245: right.left = root;
246: right = root;
247: root = root.left;
248: } else if (offset > root.offset) {
249: if (root.right == null) {
250: break;
251: }
252: if (offset > root.right.offset) {
253: SVNRangeTreeNode node = root.right;
254: root.right = node.left;
255: node.left = root;
256: root = node;
257: if (root.right == null) {
258: break;
259: }
260: }
261: left.right = root;
262: left = root;
263: root = root.right;
264: } else {
265: break;
266: }
267: }
268: left.right = root.left;
269: right.left = root.right;
270: root.left = scratch.right;
271: root.right = scratch.left;
272:
273: if (offset < root.offset && root.left != null) {
274: if (root.left.right == null) {
275: SVNRangeTreeNode node = root.left;
276: root.left = node.right;
277: SVNDeltaCombiner.assertCondition(root.left == null,
278: "not null I");
279: node.right = root;
280: root = node;
281: } else {
282: SVNRangeTreeNode node = root.left;
283: SVNRangeTreeNode prevNode = node;
284: while (node.right != null) {
285: prevNode = node;
286: node = node.right;
287: }
288: // node should now become root.
289: right = root;
290: left = root.left;
291: root = node;
292: //node = root.left;
293: prevNode.right = root.left;
294: right.left = null;
295: root.left = left;
296: root.right = right;
297: }
298: }
299: myRoot = root;
300: SVNDeltaCombiner.assertCondition((offset >= root.offset)
301: || (root.left == null && root.prev == null),
302: "assert #4");
303: }
304:
305: public void insert(int offset, int limit, int targetOffset) {
306: if (myRoot == null) {
307: myRoot = allocateTreeNode(offset, limit, targetOffset);
308: return;
309: }
310: if (offset == myRoot.offset && limit > myRoot.limit) {
311: myRoot.limit = limit;
312: myRoot.targetOffset = targetOffset;
313: cleanTree(limit);
314: } else if (offset > myRoot.offset && limit > myRoot.limit) {
315: boolean haveToInsertRange = myRoot.next == null
316: || myRoot.limit < myRoot.next.offset
317: || limit > myRoot.next.limit;
318: if (haveToInsertRange) {
319: if (myRoot.prev != null && myRoot.prev.limit > offset) {
320: myRoot.offset = offset;
321: myRoot.limit = limit;
322: myRoot.targetOffset = targetOffset;
323: } else {
324: SVNRangeTreeNode node = allocateTreeNode(offset,
325: limit, targetOffset);
326: node.next = myRoot.next;
327: if (node.next != null) {
328: node.next.prev = node;
329: }
330: myRoot.next = node;
331: node.prev = myRoot;
332:
333: node.right = myRoot.right;
334: myRoot.right = null;
335: node.left = myRoot;
336: myRoot = node;
337: }
338: cleanTree(limit);
339: }
340: } else if (offset < myRoot.offset) {
341: SVNDeltaCombiner.assertCondition(myRoot.left == null,
342: "assert #5");
343: SVNRangeTreeNode node = allocateTreeNode(offset, limit,
344: targetOffset);
345:
346: node.left = node.prev = null;
347: node.right = node.next = myRoot;
348: myRoot = node.next.prev = node;
349: cleanTree(limit);
350: }
351: }
352:
353: private void cleanTree(int limit) {
354: int topOffset = limit + 1;
355: SVNRangeTreeNode parent = myRoot;
356: SVNRangeTreeNode node = myRoot.right;
357: while (node != null) {
358: int offset = node.right != null
359: && node.right.offset < topOffset ? node.right.offset
360: : topOffset;
361: if (node.limit <= limit
362: || (node.offset < limit && offset < limit)) {
363: parent.right = null;
364: parent = node;
365: deleteSubtree(node);
366: node = null;
367: } else {
368: topOffset = node.offset;
369: node = node.left;
370: }
371: }
372: }
373:
374: private void deleteSubtree(SVNRangeTreeNode node) {
375: if (node != null) {
376: deleteSubtree(node.left);
377: deleteSubtree(node.right);
378: freeTreeNode(node);
379: }
380: }
381: }
|