001 /**
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.kahadb.index;
018
019 import java.io.DataInput;
020 import java.io.DataOutput;
021 import java.io.IOException;
022 import java.util.Iterator;
023 import java.util.Map.Entry;
024 import java.util.NoSuchElementException;
025
026 import org.apache.kahadb.page.Page;
027 import org.apache.kahadb.page.Transaction;
028 import org.apache.kahadb.util.LinkedNode;
029 import org.apache.kahadb.util.LinkedNodeList;
030 import org.apache.kahadb.util.Marshaller;
031 import org.apache.kahadb.util.VariableMarshaller;
032
033 /**
034 * The ListNode class represents a node in the List object graph. It is stored
035 * in one overflowing Page of a PageFile.
036 */
037 public final class ListNode<Key, Value> {
038
039 private final static boolean ADD_FIRST = true;
040 private final static boolean ADD_LAST = false;
041
042 // The index that this node is part of.
043 private ListIndex<Key, Value> containingList;
044
045 // The page associated with this node
046 private Page<ListNode<Key, Value>> page;
047
048 private LinkedNodeList<KeyValueEntry<Key, Value>> entries = new LinkedNodeList<KeyValueEntry<Key, Value>>() {
049
050 @Override
051 public String toString() {
052 return "PageId:" + page.getPageId() + ", index:" + containingList + super.toString();
053 }
054 };
055
056 // The next page after this one.
057 private long next = ListIndex.NOT_SET;
058
059 static final class KeyValueEntry<Key, Value> extends LinkedNode<KeyValueEntry<Key, Value>> implements Entry<Key, Value> {
060
061 private final Key key;
062 private Value value;
063
064 public KeyValueEntry(Key key, Value value) {
065 this.key = key;
066 this.value = value;
067 }
068
069 public Key getKey() {
070 return key;
071 }
072
073 public Value getValue() {
074 return value;
075 }
076
077 public Value setValue(Value value) {
078 Value oldValue = this.value;
079 this.value = value;
080 return oldValue;
081 }
082
083 @Override
084 public String toString() {
085 return "{" + key + ":" + value + "}";
086 }
087 }
088
089 private final class ListNodeIterator implements Iterator<ListNode<Key, Value>> {
090
091 private final Transaction tx;
092 private final ListIndex<Key, Value> index;
093 ListNode<Key, Value> nextEntry;
094
095 private ListNodeIterator(Transaction tx, ListNode<Key, Value> current) {
096 this.tx = tx;
097 nextEntry = current;
098 index = current.getContainingList();
099 }
100
101 public boolean hasNext() {
102 return nextEntry != null;
103 }
104
105 public ListNode<Key, Value> next() {
106 ListNode<Key, Value> current = nextEntry;
107 if (current != null) {
108 if (current.next != ListIndex.NOT_SET) {
109 try {
110 nextEntry = index.loadNode(tx, current.next);
111 } catch (IOException unexpected) {
112 IllegalStateException e = new IllegalStateException("failed to load next: " + current.next + ", reason: "
113 + unexpected.getLocalizedMessage());
114 e.initCause(unexpected);
115 throw e;
116 }
117 } else {
118 nextEntry = null;
119 }
120 }
121 return current;
122 }
123
124 public void remove() {
125 throw new UnsupportedOperationException();
126 }
127 }
128
129 final class ListIterator implements Iterator<Entry<Key, Value>> {
130
131 private final Transaction tx;
132 private final ListIndex<Key, Value> targetList;
133 ListNode<Key, Value> currentNode, previousNode;
134 KeyValueEntry<Key, Value> nextEntry;
135 KeyValueEntry<Key, Value> entryToRemove;
136
137 private ListIterator(Transaction tx, ListNode<Key, Value> current, long start) {
138 this.tx = tx;
139 this.currentNode = current;
140 this.targetList = current.getContainingList();
141 nextEntry = current.entries.getHead();
142 if (start > 0) {
143 moveToRequestedStart(start);
144 }
145 }
146
147 private void moveToRequestedStart(final long start) {
148 long count = 0;
149 while (hasNext() && count < start) {
150 next();
151 count++;
152 }
153 if (!hasNext()) {
154 throw new NoSuchElementException("Index " + start + " out of current range: " + count);
155 }
156 }
157
158 private KeyValueEntry<Key, Value> getFromNextNode() {
159 KeyValueEntry<Key, Value> result = null;
160 if (currentNode.getNext() != ListIndex.NOT_SET) {
161 try {
162 previousNode = currentNode;
163 currentNode = targetList.loadNode(tx, currentNode.getNext());
164 } catch (IOException unexpected) {
165 NoSuchElementException e = new NoSuchElementException(unexpected.getLocalizedMessage());
166 e.initCause(unexpected);
167 throw e;
168 }
169 result = currentNode.entries.getHead();
170 }
171 return result;
172 }
173
174 public boolean hasNext() {
175 if (nextEntry == null) {
176 nextEntry = getFromNextNode();
177 }
178 return nextEntry != null;
179 }
180
181 public Entry<Key, Value> next() {
182 if (nextEntry != null) {
183 entryToRemove = nextEntry;
184 nextEntry = entryToRemove.getNext();
185 return entryToRemove;
186 } else {
187 throw new NoSuchElementException();
188 }
189 }
190
191 public void remove() {
192 if (entryToRemove == null) {
193 throw new IllegalStateException("can only remove once, call hasNext();next() again");
194 }
195 try {
196 entryToRemove.unlink();
197 entryToRemove = null;
198 ListNode<Key, Value> toRemoveNode = null;
199 if (currentNode.entries.isEmpty()) {
200 // may need to free this node
201 if (currentNode.isHead() && currentNode.isTail()) {
202 // store empty list
203 } else if (currentNode.isHead()) {
204 // merge next node into existing headNode as we don't want to
205 // change our headPageId b/c that is our identity
206 ListNode<Key, Value> headNode = currentNode;
207 nextEntry = getFromNextNode(); // will move currentNode
208
209 if (currentNode.isTail()) {
210 targetList.setTailPageId(headNode.getPageId());
211 }
212 // copy next/currentNode into head
213 headNode.setEntries(currentNode.entries);
214 headNode.setNext(currentNode.getNext());
215 headNode.store(tx);
216 toRemoveNode = currentNode;
217 currentNode = headNode;
218
219 } else if (currentNode.isTail()) {
220 toRemoveNode = currentNode;
221 previousNode.setNext(ListIndex.NOT_SET);
222 previousNode.store(tx);
223 targetList.setTailPageId(previousNode.getPageId());
224 } else {
225 toRemoveNode = currentNode;
226 previousNode.setNext(toRemoveNode.getNext());
227 previousNode.store(tx);
228 }
229 }
230 targetList.onRemove();
231
232 if (toRemoveNode != null) {
233 tx.free(toRemoveNode.getPage());
234 } else {
235 currentNode.store(tx);
236 }
237 } catch (IOException unexpected) {
238 IllegalStateException e = new IllegalStateException(unexpected.getLocalizedMessage());
239 e.initCause(unexpected);
240 throw e;
241 }
242 }
243
244 ListNode<Key, Value> getCurrent() {
245 return this.currentNode;
246 }
247 }
248
249 /**
250 * The Marshaller is used to store and load the data in the ListNode into a Page.
251 *
252 * @param <Key>
253 * @param <Value>
254 */
255 static public final class NodeMarshaller<Key, Value> extends VariableMarshaller<ListNode<Key, Value>> {
256 private final Marshaller<Key> keyMarshaller;
257 private final Marshaller<Value> valueMarshaller;
258
259 public NodeMarshaller(Marshaller<Key> keyMarshaller, Marshaller<Value> valueMarshaller) {
260 this.keyMarshaller = keyMarshaller;
261 this.valueMarshaller = valueMarshaller;
262 }
263
264 public void writePayload(ListNode<Key, Value> node, DataOutput os) throws IOException {
265 os.writeLong(node.next);
266 short count = (short) node.entries.size(); // cast may truncate
267 // value...
268 if (count != node.entries.size()) {
269 throw new IOException("short over flow, too many entries in list: " + node.entries.size());
270 }
271
272 os.writeShort(count);
273 KeyValueEntry<Key, Value> entry = node.entries.getHead();
274 while (entry != null) {
275 keyMarshaller.writePayload((Key) entry.getKey(), os);
276 valueMarshaller.writePayload((Value) entry.getValue(), os);
277 entry = entry.getNext();
278 }
279 }
280
281 @SuppressWarnings({ "unchecked", "rawtypes" })
282 public ListNode<Key, Value> readPayload(DataInput is) throws IOException {
283 ListNode<Key, Value> node = new ListNode<Key, Value>();
284 node.setNext(is.readLong());
285 final short size = is.readShort();
286 for (short i = 0; i < size; i++) {
287 node.entries.addLast(new KeyValueEntry(keyMarshaller.readPayload(is), valueMarshaller.readPayload(is)));
288 }
289 return node;
290 }
291 }
292
293 public Value put(Transaction tx, Key key, Value value) throws IOException {
294 if (key == null) {
295 throw new IllegalArgumentException("Key cannot be null");
296 }
297 entries.addLast(new KeyValueEntry<Key, Value>(key, value));
298 store(tx, ADD_LAST);
299 return null;
300 }
301
302 public Value addFirst(Transaction tx, Key key, Value value) throws IOException {
303 if (key == null) {
304 throw new IllegalArgumentException("Key cannot be null");
305 }
306 entries.addFirst(new KeyValueEntry<Key, Value>(key, value));
307 store(tx, ADD_FIRST);
308 return null;
309 }
310
311 public void storeUpdate(Transaction tx) throws IOException {
312 try {
313 if (this.entries.size() == 1) {
314 getContainingList().storeNode(tx, this, true);
315 } else {
316 getContainingList().storeNode(tx, this, false);
317 }
318 } catch (Transaction.PageOverflowIOException e) {
319 split(tx, ADD_FIRST);
320 }
321 }
322
323 private void store(Transaction tx, boolean addFirst) throws IOException {
324 try {
325 // When we split to a node of one element we can span multiple pages for that
326 // entry, otherwise we keep the entries on one page to avoid fragmented reads
327 // and segment the list traversal.
328 if (this.entries.size() == 1) {
329 getContainingList().storeNode(tx, this, true);
330 } else {
331 getContainingList().storeNode(tx, this, false);
332 }
333
334 if (this.next == -1) {
335 getContainingList().setTailPageId(getPageId());
336 }
337
338 } catch (Transaction.PageOverflowIOException e) {
339 // If we get an overflow
340 split(tx, addFirst);
341 }
342 }
343
344 private void store(Transaction tx) throws IOException {
345 if (this.entries.size() == 1) {
346 getContainingList().storeNode(tx, this, true);
347 } else {
348 getContainingList().storeNode(tx, this, false);
349 }
350 }
351
352 private void split(Transaction tx, boolean isAddFirst) throws IOException {
353 ListNode<Key, Value> extension = getContainingList().createNode(tx);
354 if (isAddFirst) {
355 // head keeps the first entry, insert extension with the rest
356 extension.setEntries(entries.getHead().splitAfter());
357 extension.setNext(this.getNext());
358 extension.store(tx, isAddFirst);
359 this.setNext(extension.getPageId());
360 } else {
361 extension.setEntries(entries.getTail().getPrevious().splitAfter());
362 extension.store(tx, isAddFirst);
363 getContainingList().setTailPageId(extension.getPageId());
364 this.setNext(extension.getPageId());
365 }
366 store(tx, true);
367 }
368
369 // called after a split
370 private void setEntries(LinkedNodeList<KeyValueEntry<Key, Value>> list) {
371 this.entries = list;
372 }
373
374 public Value get(Transaction tx, Key key) {
375 if (key == null) {
376 throw new IllegalArgumentException("Key cannot be null");
377 }
378 Value result = null;
379 KeyValueEntry<Key, Value> nextEntry = entries.getTail();
380 while (nextEntry != null) {
381 if (nextEntry.getKey().equals(key)) {
382 result = nextEntry.getValue();
383 break;
384 }
385 nextEntry = nextEntry.getPrevious();
386 }
387 return result;
388 }
389
390 public boolean isEmpty(final Transaction tx) {
391 return entries.isEmpty();
392 }
393
394 public Entry<Key, Value> getFirst(Transaction tx) {
395 return entries.getHead();
396 }
397
398 public Entry<Key, Value> getLast(Transaction tx) {
399 return entries.getTail();
400 }
401
402 public Iterator<Entry<Key, Value>> iterator(final Transaction tx, long pos) throws IOException {
403 return new ListIterator(tx, this, pos);
404 }
405
406 public Iterator<Entry<Key, Value>> iterator(final Transaction tx) throws IOException {
407 return new ListIterator(tx, this, 0);
408 }
409
410 Iterator<ListNode<Key, Value>> listNodeIterator(final Transaction tx) throws IOException {
411 return new ListNodeIterator(tx, this);
412 }
413
414 public void clear(Transaction tx) throws IOException {
415 entries.clear();
416 tx.free(this.getPageId());
417 }
418
419 public boolean contains(Transaction tx, Key key) {
420 if (key == null) {
421 throw new IllegalArgumentException("Key cannot be null");
422 }
423 boolean found = false;
424 KeyValueEntry<Key, Value> nextEntry = entries.getTail();
425 while (nextEntry != null) {
426 if (nextEntry.getKey().equals(key)) {
427 found = true;
428 break;
429 }
430 nextEntry = nextEntry.getPrevious();
431 }
432 return found;
433 }
434
435 // /////////////////////////////////////////////////////////////////
436 // Implementation methods
437 // /////////////////////////////////////////////////////////////////
438
439 public long getPageId() {
440 return page.getPageId();
441 }
442
443 public Page<ListNode<Key, Value>> getPage() {
444 return page;
445 }
446
447 public void setPage(Page<ListNode<Key, Value>> page) {
448 this.page = page;
449 }
450
451 public long getNext() {
452 return next;
453 }
454
455 public void setNext(long next) {
456 this.next = next;
457 }
458
459 public void setContainingList(ListIndex<Key, Value> list) {
460 this.containingList = list;
461 }
462
463 public ListIndex<Key, Value> getContainingList() {
464 return containingList;
465 }
466
467 public boolean isHead() {
468 return getPageId() == containingList.getHeadPageId();
469 }
470
471 public boolean isTail() {
472 return getPageId() == containingList.getTailPageId();
473 }
474
475 public int size(Transaction tx) {
476 return entries.size();
477 }
478
479 @Override
480 public String toString() {
481 return "[ListNode(" + (page != null ? page.getPageId() + "->" + next : "null") + ")[" + entries.size() + "]]";
482 }
483 }