View Javadoc
1   /*
2    * Copyright (C) 2011, Google Inc.
3    * and other copyright owners as documented in the project's IP log.
4    *
5    * This program and the accompanying materials are made available
6    * under the terms of the Eclipse Distribution License v1.0 which
7    * accompanies this distribution, is reproduced below, and is
8    * available at http://www.eclipse.org/org/documents/edl-v10.php
9    *
10   * All rights reserved.
11   *
12   * Redistribution and use in source and binary forms, with or
13   * without modification, are permitted provided that the following
14   * conditions are met:
15   *
16   * - Redistributions of source code must retain the above copyright
17   *   notice, this list of conditions and the following disclaimer.
18   *
19   * - Redistributions in binary form must reproduce the above
20   *   copyright notice, this list of conditions and the following
21   *   disclaimer in the documentation and/or other materials provided
22   *   with the distribution.
23   *
24   * - Neither the name of the Eclipse Foundation, Inc. nor the
25   *   names of its contributors may be used to endorse or promote
26   *   products derived from this software without specific prior
27   *   written permission.
28   *
29   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
30   * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
31   * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
32   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33   * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
34   * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
36   * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
37   * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
38   * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
39   * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
40   * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
41   * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
42   */
43  
44  package org.eclipse.jgit.internal.storage.dfs;
45  
46  
47  /**
48   * Caches recently used objects for {@link DfsReader}.
49   * <p>
50   * This cache is not thread-safe. Each reader should have its own cache.
51   */
52  final class DeltaBaseCache {
53  	private static final int TABLE_BITS = 10;
54  
55  	private static final int MASK_BITS = 32 - TABLE_BITS;
56  
57  	private static int hash(long position) {
58  		return (((int) position) << MASK_BITS) >>> MASK_BITS;
59  	}
60  
61  	private int maxByteCount;
62  	private int curByteCount;
63  
64  	private final Entry[] table;
65  
66  	private Entry lruHead;
67  	private Entry lruTail;
68  
69  	DeltaBaseCache(DfsReader reader) {
70  		this(reader.getOptions().getDeltaBaseCacheLimit());
71  	}
72  
73  	DeltaBaseCache(int maxBytes) {
74  		maxByteCount = maxBytes;
75  		table = new Entry[1 << TABLE_BITS];
76  	}
77  
78  	Entry get(DfsStreamKey key, long position) {
79  		Entry e = table[hash(position)];
80  		for (; e != null; e = e.tableNext) {
81  			if (e.offset == position && key.equals(e.pack)) {
82  				moveToHead(e);
83  				return e;
84  			}
85  		}
86  		return null;
87  	}
88  
89  	void put(DfsStreamKey key, long offset, int objectType, byte[] data) {
90  		if (data.length > maxByteCount)
91  			return; // Too large to cache.
92  
93  		curByteCount += data.length;
94  		releaseMemory();
95  
96  		int tableIdx = hash(offset);
97  		Entry e = new Entry(key, offset, objectType, data);
98  		e.tableNext = table[tableIdx];
99  		table[tableIdx] = e;
100 		lruPushHead(e);
101 	}
102 
103 	private void releaseMemory() {
104 		while (curByteCount > maxByteCount && lruTail != null) {
105 			Entry e = lruTail;
106 			curByteCount -= e.data.length;
107 			lruRemove(e);
108 			removeFromTable(e);
109 		}
110 	}
111 
112 	private void removeFromTable(Entry e) {
113 		int tableIdx = hash(e.offset);
114 		Entry p = table[tableIdx];
115 
116 		if (p == e) {
117 			table[tableIdx] = e.tableNext;
118 			return;
119 		}
120 
121 		for (; p != null; p = p.tableNext) {
122 			if (p.tableNext == e) {
123 				p.tableNext = e.tableNext;
124 				return;
125 			}
126 		}
127 
128 		throw new IllegalStateException(String.format(
129 				"entry for %s:%d not in table", //$NON-NLS-1$
130 				e.pack, Long.valueOf(e.offset)));
131 	}
132 
133 	private void moveToHead(Entry e) {
134 		if (e != lruHead) {
135 			lruRemove(e);
136 			lruPushHead(e);
137 		}
138 	}
139 
140 	private void lruRemove(Entry e) {
141 		Entry p = e.lruPrev;
142 		Entry n = e.lruNext;
143 
144 		if (p != null) {
145 			p.lruNext = n;
146 		} else {
147 			lruHead = n;
148 		}
149 
150 		if (n != null) {
151 			n.lruPrev = p;
152 		} else {
153 			lruTail = p;
154 		}
155 	}
156 
157 	private void lruPushHead(Entry e) {
158 		Entry n = lruHead;
159 		e.lruNext = n;
160 		if (n != null)
161 			n.lruPrev = e;
162 		else
163 			lruTail = e;
164 
165 		e.lruPrev = null;
166 		lruHead = e;
167 	}
168 
169 	int getMemoryUsed() {
170 		return curByteCount;
171 	}
172 
173 	int getMemoryUsedByLruChainForTest() {
174 		int r = 0;
175 		for (Entry e = lruHead; e != null; e = e.lruNext) {
176 			r += e.data.length;
177 		}
178 		return r;
179 	}
180 
181 	int getMemoryUsedByTableForTest() {
182 		int r = 0;
183 		for (int i = 0; i < table.length; i++) {
184 			for (Entry e = table[i]; e != null; e = e.tableNext) {
185 				r += e.data.length;
186 			}
187 		}
188 		return r;
189 	}
190 
191 	static class Entry {
192 		final DfsStreamKey pack;
193 		final long offset;
194 		final int type;
195 		final byte[] data;
196 
197 		Entry tableNext;
198 		Entry lruPrev;
199 		Entry lruNext;
200 
201 		Entry(DfsStreamKey key, long offset, int type, byte[] data) {
202 			this.pack = key;
203 			this.offset = offset;
204 			this.type = type;
205 			this.data = data;
206 		}
207 	}
208 }