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 */
017package org.apache.kahadb.index;
018
019import java.io.DataInput;
020import java.io.DataOutput;
021import java.io.IOException;
022import java.util.Iterator;
023import java.util.Map.Entry;
024import java.util.NoSuchElementException;
025
026import org.apache.kahadb.page.Page;
027import org.apache.kahadb.page.Transaction;
028import org.apache.kahadb.util.LinkedNode;
029import org.apache.kahadb.util.LinkedNodeList;
030import org.apache.kahadb.util.Marshaller;
031import 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 */
037public 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}