1 /***
2 * Copyright 2003-2010 Terracotta, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 package net.sf.ehcache.store.disk.ods;
17
18 /***
19 * A region set based on an augmented AA-Tree.
20 *
21 * @author Chris Dennis
22 */
23 class RegionSet extends AATreeSet<Region> {
24
25 private final long size;
26
27 /***
28 * Construct the tree.
29 */
30 protected RegionSet(long size) {
31 super();
32 add(new Region(0, size - 1));
33 this.size = size;
34 }
35
36 @Override
37 public Region removeAndReturn(Object o) {
38 Region r = super.removeAndReturn(o);
39 if (r != null) {
40 return new Region(r);
41 } else {
42 return null;
43 }
44 }
45
46 @Override
47 public Region find(Object o) {
48 Region r = super.find(o);
49 if (r != null) {
50 return new Region(r);
51 } else {
52 return null;
53 }
54 }
55
56 /***
57 * Find a region of the the given size.
58 */
59 public Region find(long size) {
60 Node<Region> currentNode = getRoot();
61 Region currentRegion = currentNode.getPayload();
62
63 if (currentRegion == null || size > currentRegion.contiguous()) {
64 throw new IllegalArgumentException("Need to grow the region set");
65 } else {
66 while (true) {
67 if (currentRegion.size() >= size) {
68 return new Region(currentRegion.start(), currentRegion.start() + size - 1);
69 } else {
70 Region left = currentNode.getLeft().getPayload();
71 Region right = currentNode.getRight().getPayload();
72 if (left != null && left.contiguous() >= size) {
73 currentNode = currentNode.getLeft();
74 currentRegion = currentNode.getPayload();
75 } else if (right != null && right.contiguous() >= size) {
76 currentNode = currentNode.getRight();
77 currentRegion = currentNode.getPayload();
78 } else {
79 throw new IllegalArgumentException("Couldn't find a " + size + " sized free area in " + currentRegion);
80 }
81 }
82 }
83 }
84 }
85 }