1 /**
2  *  Copyright 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 import java.io.IOException;
19 import java.io.RandomAccessFile;
20
21 import org.slf4j.Logger;
22 import org.slf4j.LoggerFactory;
23
24 /**
25  * File allocation tree allows C-like alloc/free operations on a random access file.
26  *
27  * @author Chris Dennis
28  */
29 public final class FileAllocationTree extends RegionSet {
30
31     private static final Logger LOGGER = LoggerFactory.getLogger(FileAllocationTree.class);
32     
33     private long fileSize;
34     private final RandomAccessFile data;
35
36     /**
37      * Create a file allocation tree for the given file, capping it's size at maxSize.
38      */
39     public FileAllocationTree(long maxSize, RandomAccessFile file) {
40         super(maxSize);
41         this.data = file;
42     }
43
44     /**
45      * Allocate a new region of the given size.
46      */
47     public synchronized Region alloc(long size) {
48         Region r = find(size);
49         mark(r);
50         return r;
51     }
52
53     /**
54      * Mark this region as used
55      */
56     public synchronized void mark(Region r) {
57         Region current = removeAndReturn(Long.valueOf(r.start()));
58         if (current == null) {
59             throw new IllegalArgumentException();
60         }
61         Region newRange = current.remove(r);
62         if (newRange != null) {
63             add(current);
64             add(newRange);
65         } else if (!current.isNull()) {
66             add(current);
67         }
68         checkGrow(r);
69     }
70
71     /**
72      * Mark this region as free.
73      */
74     public synchronized void free(Region r) {
75         // Step 1 : Check if the previous number is present, if so add to the same Range.
76         Region prev = removeAndReturn(Long.valueOf(r.start() - 1));
77         if (prev != null) {
78             prev.merge(r);
79             Region next = removeAndReturn(Long.valueOf(r.end() + 1));
80             if (next != null) {
81                 prev.merge(next);
82             }
83             add(prev);
84             checkShrink(prev);
85             return;
86         }
87
88         // Step 2 : Check if the next number is present, if so add to the same Range.
89         Region next = removeAndReturn(Long.valueOf(r.end() + 1));
90         if (next != null) {
91             next.merge(r);
92             add(next);
93             checkShrink(next);
94             return;
95         }
96
97         // Step 3: Add a new range for just this number.
98         add(r);
99         checkShrink(r);
100     }
101
102     /**
103      * Mark this whole file as free
104      */
105     @Override
106     public synchronized void clear() {
107         super.clear();
108     }
109
110     private void checkGrow(Region alloc) {
111         if (alloc.end() >= fileSize) {
112             fileSize = alloc.end() + 1;
113             grow(fileSize);
114         }
115     }
116
117     private void checkShrink(Region free) {
118         if (free.end() >= fileSize - 1) {
119             fileSize = free.start();
120             shrink(fileSize);
121         }
122     }
123
124     private void grow(long size) {
125         //no-op
126     }
127
128     private void shrink(long size) {
129         if (data == null) {
130             return;
131         } else {
132             synchronized (data) {
133                 try {
134                     data.setLength(size);
135                 } catch (IOException e) {
136                     LOGGER.info("Exception while trying to shrink file", e);
137                 }
138             }
139         }
140     }
141
142     /**
143      * Return the current occupied size of this file.
144      */
145     public synchronized long getFileSize() {
146         return fileSize;
147     }
148 }
149