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
17 package net.sf.ehcache.store.disk.ods;
18
19 import java.util.ArrayList;
20 import java.util.BitSet;
21 import java.util.List;
22 import java.util.Random;
23
24 import org.junit.Test;
25
26 import junit.framework.Assert;
27
28 public class FileAllocationTreeTest {
29
30 @Test
31 public void testUniformSizedAllocations() {
32 FileAllocationTree test = new FileAllocationTree(100, null);
33
34 for (int i = 0; i < 100; i++) {
35 Assert.assertEquals(i, test.alloc(1).start());
36 }
37 Assert.assertEquals(100, test.getFileSize());
38 }
39
40 @Test
41 public void testUniformSizedFrees() {
42 FileAllocationTree test = new FileAllocationTree(100, null);
43 test.alloc(100);
44 Assert.assertEquals(100, test.getFileSize());
45
46 for (int i = 0; i < 100; i++) {
47 Assert.assertEquals(100, test.getFileSize());
48 test.free(new Region(i));
49 }
50 Assert.assertEquals(0, test.getFileSize());
51 }
52
53 @Test
54 public void testUniformRepeatedAllocFree() {
55 FileAllocationTree test = new FileAllocationTree(100, null);
56
57 for (int i = 1; i < 100; i++) {
58 int count = (int) Math.floor(100d / i);
59 for (int j = 1; j <= count; j++) {
60 List<Region> regions = new ArrayList<Region>();
61 for (int k = 0; k < j; k++) {
62 Region r = test.alloc(i);
63 Assert.assertEquals("Testing " + j + " Regions of size " + i + ": Alloc " + k, i, r.size());
64 Assert.assertEquals("Testing " + j + " Regions of size " + i + ": Alloc " + k, k * i, r.start());
65 regions.add(r);
66 }
67 for (Region r : regions) {
68 test.free(r);
69 }
70 Assert.assertEquals("Testing " + j + " Regions of size " + i, 0, test.getFileSize());
71 }
72 }
73 }
74
75 @Test
76 public void testRandomAllocFree() {
77 for (int n = 0; n < 100; n++) {
78 FileAllocationTree test = new FileAllocationTree(10000, null);
79 BitSet reference = new BitSet();
80 Random rndm = new Random();
81
82 for (int i = 0; i < 100; i++) {
83 if (rndm.nextBoolean()) {
84 Region r = test.alloc(rndm.nextInt(100));
85 BitSet ref = reference.get((int) r.start(), (int) r.end() + 1);
86 reference.set((int) r.start(), (int) r.end() + 1);
87 } else {
88 int length = reference.length();
89 if (length > 0) {
90 int random = rndm.nextInt(length);
91 int start = reference.nextSetBit(random);
92 if (start >= 0) {
93 int max = reference.nextClearBit(start);
94 int end = start + rndm.nextInt(max - start);
95 Region r = new Region(start, end);
96 test.free(r);
97 reference.clear(start, end + 1);
98 }
99 }
100 }
101 }
102 }
103 }
104 }