001: /*
002: This source file is part of Smyle, a database library.
003: For up-to-date information, see http://www.drjava.de/smyle
004: Copyright (C) 2001 Stefan Reich (doc@drjava.de)
005:
006: This library is free software; you can redistribute it and/or
007: modify it under the terms of the GNU Lesser General Public
008: License as published by the Free Software Foundation; either
009: version 2.1 of the License, or (at your option) any later version.
010:
011: This library is distributed in the hope that it will be useful,
012: but WITHOUT ANY WARRANTY; without even the implied warranty of
013: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: Lesser General Public License for more details.
015:
016: You should have received a copy of the GNU Lesser General Public
017: License along with this library; if not, write to the Free Software
018: Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
019:
020: For full license text, see doc/license/lgpl.txt in this distribution
021: */
022:
023: package drjava.smyle.core;
024:
025: import java.util.*;
026: import org.artsProject.mcop.*;
027: import com.go.trove.util.*;
028: import drjava.smyle.*;
029:
030: /*
031: Requirements:
032: -little memory consumption on startup
033: -efficient storage (more than one entry per chunk)
034: -quick access to any index
035: -quick adding (finding vacancy)
036: -individual changes should not invalidate large data structures
037:
038: Architecture:
039: -linear list of blocks with 32 entries each
040:
041: In memory:
042: -chunkref array, one for every block
043: -vacancy bit array (one bit per block)
044: -changed blocks are held in HashMap
045: => approx. 33 bits per entry
046:
047: On disk:
048: -one chunk per block
049: -master chunk contains vacancy and chunkref arrays
050: */
051:
052: public final class ScalablePool<A> {
053: static final int CLEANCACHE_MINSIZE = 64;
054:
055: // block sources
056: static final int DIRTY = 0, CLEAN = 1, DISK = 2, EMPTY = 3,
057: UNKNOWN = 4;
058:
059: BitSet vacancy = new BitSet();
060: FastIntVector blocks = new FastIntVector();
061: int firstVacancy;
062: MarDemar<A> marDemar;
063: ChunkManager cm;
064: ChunkRef master;
065: Cache<Integer, Block> cleanCache = new Cache<Integer, Block>(
066: CLEANCACHE_MINSIZE);
067: HashMap<Integer, Block> dirtyCache = new HashMap<Integer, Block>();
068: int blockSource; // temp var
069: final Block emptyBlock = new Block(); // dummy entry for empty blocks in dirtyCache
070:
071: // stats
072: int chunksCreated, dirtyCacheHit, cleanCacheHit, cacheMiss,
073: emptyHit;
074:
075: final class Block implements Marshallable {
076: A[] data = new A[32];
077: int elements;
078:
079: boolean empty() {
080: return elements == 0;
081: }
082:
083: boolean vacancies() {
084: return elements < 32;
085: }
086:
087: int insert(A a) {
088: for (int i = elements; i < elements + 32; i++)
089: if (data[i & 31] == null) {
090: ++elements;
091: data[i & 31] = a;
092: return i & 31;
093: }
094: throw new RuntimeException("No vacancy");
095: }
096:
097: void release(int i) {
098: data[i] = null;
099: --elements;
100: }
101:
102: void replace(int i, A a) {
103: data[i] = a;
104: }
105:
106: public void marshal(Buffer b) {
107: int pattern = 0;
108: for (int i = 0; i < 32; i++)
109: if (data[i] != null)
110: pattern |= 1 << i;
111: b.writeLong(pattern);
112: for (int i = 0; i < 32; i++)
113: if (data[i] != null)
114: marDemar.marshal(b, data[i]);
115: }
116:
117: Block() {
118: }
119:
120: Block(Buffer b) {
121: int pattern = b.readLong();
122: for (int i = 0; i < 32; i++)
123: if ((pattern & (1 << i)) != 0) {
124: data[i] = marDemar.read(b);
125: ++elements;
126: }
127: }
128: }
129:
130: class BlockMarDemar implements MarDemar<Block> {
131: public void marshal(Buffer b, Block block) {
132: block.marshal(b);
133: }
134:
135: public Block read(Buffer b) {
136: return new Block(b);
137: }
138: }
139:
140: public ScalablePool(MarDemar<A> marDemar, ChunkManager cm,
141: ChunkRef master) {
142: this .marDemar = marDemar;
143: this .cm = cm;
144: if (master != null)
145: loadMaster(master);
146: }
147:
148: public int insert(A a) {
149: master = null;
150: for (int b = firstVacancy; b < blocks.size(); b++) {
151: if (!vacancy.get(b))
152: continue;
153: Integer B = new Integer(b);
154: Block block = getBlock(B);
155: if (block == null)
156: block = new Block();
157: if (!block.vacancies())
158: throw new InternalSmyleError("Block " + b
159: + " in vacancy list, but not vacant");
160: int ofs = block.insert(a);
161: setBlock(B, block, blockSource);
162: if (!block.vacancies()) {
163: vacancy.clear(b);
164: firstVacancy = b + 1;
165: } else
166: firstVacancy = b;
167: //System.out.println("Elements in block "+b+" now: "+block.elements+" (vacancy: "+vacancy.get(b)+")");
168: return (b << 5) + ofs;
169: }
170: Block block = new Block();
171: int ofs = block.insert(a);
172: int n = blocks.size();
173: blocks.add(0);
174: vacancy.set(n);
175: setBlock(n, block);
176: return (n << 5) + ofs;
177: }
178:
179: public void replace(int i, A a) {
180: while ((i >> 5) >= blocks.size())
181: blocks.add(0);
182: Block b = getBlock(i >> 5);
183: if (b == null)
184: b = new Block();
185: b.replace(i & 31, a);
186: setBlock(i >> 5, b);
187: master = null;
188: }
189:
190: private void setBlock(int i, Block b) {
191: setBlock(new Integer(i), b, UNKNOWN);
192: }
193:
194: private void setBlock(Integer I, Block b, int blockSource) {
195: if (blockSource == UNKNOWN || blockSource == CLEAN)
196: cleanCache.remove(I);
197: if (blockSource != DIRTY)
198: dirtyCache.put(I, b == null ? emptyBlock : b);
199: }
200:
201: private void flushCache() {
202: for (Iterator<Map.Entry<Integer, Block>> i = dirtyCache
203: .entrySet().iterator(); i.hasNext();) {
204: Map.Entry<Integer, Block> e = i.next();
205: int index = e.getKey().intValue();
206: Block block = e.getValue();
207: if (block == emptyBlock)
208: blocks.set(index, 0);
209: else {
210: blocks.set(index, cm.createChunk(block).index);
211: chunksCreated++;
212: }
213: }
214: dirtyCache.clear();
215: }
216:
217: public A get(int i) {
218: if (i < 0 || i >= blocks.size() * 32)
219: return null;
220: Block block = getBlock(i >> 5);
221: return block == null ? null : block.data[i & 31];
222: }
223:
224: public void release(int i) {
225: int b = i >> 5;
226: Block block = getBlock(b);
227: block.release(i & 31);
228: vacancy.set(b);
229: if (b < firstVacancy)
230: firstVacancy = b;
231: if (block.empty()) {
232: flushCache();
233: blocks.set(b, 0);
234: while (blocks.size() != 0
235: && blocks.get(blocks.size() - 1) == 0)
236: blocks.remove(blocks.size() - 1);
237: } else
238: setBlock(b, block);
239: master = null;
240: }
241:
242: private void loadMaster(ChunkRef master) {
243: Buffer b = cm.readChunk(master);
244: blocks.read(b);
245: for (int i = 0; i < blocks.size(); i += 32) {
246: int val = b.readLong();
247: for (int j = 0; j < 32; j++)
248: if ((val & (1 << j)) != 0)
249: vacancy.set(i + j);
250: }
251: this .master = master;
252: }
253:
254: public ChunkRef flush() {
255: if (master == null) {
256: flushCache();
257: Buffer b = new Buffer();
258: blocks.marshal(b);
259: for (int i = 0; i < blocks.size(); i += 32) {
260: int val = 0;
261: for (int j = 0; j < 32; j++)
262: if (vacancy.get(i + j))
263: val |= 1 << j;
264: b.writeLong(val);
265: }
266: master = cm.createChunk(b);
267: /*System.out.println("ScalablePool: created "+chunksCreated+" chunks, dirty/clean/miss/empty: "
268: +dirtyCacheHit+"/"+cleanCacheHit+"/"+cacheMiss+"/"+emptyHit);*/
269: chunksCreated = dirtyCacheHit = cleanCacheHit = cacheMiss = 0;
270: }
271: return master;
272: }
273:
274: private Block getBlock(int i) {
275: return getBlock(new Integer(i));
276: }
277:
278: private Block getBlock(Integer I) {
279: //new Throwable().printStackTrace();
280: Block b = dirtyCache.get(I);
281: if (b != null) {
282: dirtyCacheHit++;
283: blockSource = DIRTY;
284: return b == emptyBlock ? null : b;
285: }
286:
287: int chunk = blocks.get(I.intValue());
288: if (chunk == 0) {
289: emptyHit++;
290: blockSource = EMPTY;
291: return null;
292: }
293:
294: b = cleanCache.get(I);
295: if (b != null) {
296: cleanCacheHit++;
297: blockSource = CLEAN;
298: return b;
299: }
300:
301: b = new Block(cm.readChunk(chunk));
302: cleanCache.put(I, b);
303: cacheMiss++;
304: blockSource = DISK;
305: //if (cacheBlock != null) System.out.println("ScalablePool: loaded block "+i);
306: return b;
307: }
308:
309: public int size() {
310: return blocks.size() * 32;
311: }
312:
313: public void collectChunks(BitSet whiteList) {
314: whiteList.set(master.index);
315: for (int i = 0; i < blocks.size(); i++)
316: whiteList.set(blocks.get(i));
317: }
318:
319: public void checkConsistency() {
320: for (int i = 0; i < blocks.size(); i++) {
321: if (vacancy.get(i) != getBlock(i).vacancies())
322: throw new RuntimeException("Inconsistent at block " + i);
323: if (vacancy.get(i) && i < firstVacancy)
324: throw new RuntimeException("firstVacancy too high");
325: }
326: }
327: }
|