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    }