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.activemq.store.kahadb.disk.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.activemq.store.kahadb.disk.page.Page;
027import org.apache.activemq.store.kahadb.disk.page.Transaction;
028import org.apache.activemq.store.kahadb.disk.util.LinkedNode;
029import org.apache.activemq.store.kahadb.disk.util.LinkedNodeList;
030import org.apache.activemq.store.kahadb.disk.util.Marshaller;
031import org.apache.activemq.store.kahadb.disk.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                        currentNode = previousNode;
229                    }
230                }
231                targetList.onRemove();
232
233                if (toRemoveNode != null) {
234                    tx.free(toRemoveNode.getPage());
235                } else {
236                    currentNode.store(tx);
237                }
238            } catch (IOException unexpected) {
239                IllegalStateException e = new IllegalStateException(unexpected.getLocalizedMessage());
240                e.initCause(unexpected);
241                throw e;
242            }
243        }
244
245        ListNode<Key, Value> getCurrent() {
246            return this.currentNode;
247        }
248    }
249
250    /**
251     * The Marshaller is used to store and load the data in the ListNode into a Page.
252     *
253     * @param <Key>
254     * @param <Value>
255     */
256    static public final class NodeMarshaller<Key, Value> extends VariableMarshaller<ListNode<Key, Value>> {
257        private final Marshaller<Key> keyMarshaller;
258        private final Marshaller<Value> valueMarshaller;
259
260        public NodeMarshaller(Marshaller<Key> keyMarshaller, Marshaller<Value> valueMarshaller) {
261            this.keyMarshaller = keyMarshaller;
262            this.valueMarshaller = valueMarshaller;
263        }
264
265        public void writePayload(ListNode<Key, Value> node, DataOutput os) throws IOException {
266            os.writeLong(node.next);
267            short count = (short) node.entries.size(); // cast may truncate
268                                                       // value...
269            if (count != node.entries.size()) {
270                throw new IOException("short over flow, too many entries in list: " + node.entries.size());
271            }
272
273            os.writeShort(count);
274            KeyValueEntry<Key, Value> entry = node.entries.getHead();
275            while (entry != null) {
276                keyMarshaller.writePayload((Key) entry.getKey(), os);
277                valueMarshaller.writePayload((Value) entry.getValue(), os);
278                entry = entry.getNext();
279            }
280        }
281
282        @SuppressWarnings({ "unchecked", "rawtypes" })
283        public ListNode<Key, Value> readPayload(DataInput is) throws IOException {
284            ListNode<Key, Value> node = new ListNode<Key, Value>();
285            node.setNext(is.readLong());
286            final short size = is.readShort();
287            for (short i = 0; i < size; i++) {
288                node.entries.addLast(new KeyValueEntry(keyMarshaller.readPayload(is), valueMarshaller.readPayload(is)));
289            }
290            return node;
291        }
292    }
293
294    public Value put(Transaction tx, Key key, Value value) throws IOException {
295        if (key == null) {
296            throw new IllegalArgumentException("Key cannot be null");
297        }
298        entries.addLast(new KeyValueEntry<Key, Value>(key, value));
299        store(tx, ADD_LAST);
300        return null;
301    }
302
303    public Value addFirst(Transaction tx, Key key, Value value) throws IOException {
304        if (key == null) {
305            throw new IllegalArgumentException("Key cannot be null");
306        }
307        entries.addFirst(new KeyValueEntry<Key, Value>(key, value));
308        store(tx, ADD_FIRST);
309        return null;
310    }
311
312    public void storeUpdate(Transaction tx) throws IOException {
313        store(tx, ADD_LAST);
314    }
315
316    private void store(Transaction tx, boolean addFirst) throws IOException {
317        try {
318            // keeping splitting till we get down to a single entry
319            // then we need to overflow the value
320            getContainingList().storeNode(tx, this, entries.size() == 1);
321
322            if (this.next == -1) {
323                getContainingList().setTailPageId(getPageId());
324            }
325
326        } catch (Transaction.PageOverflowIOException e) {
327            // If we get an overflow
328            split(tx, addFirst);
329        }
330    }
331
332    private void store(Transaction tx) throws IOException {
333        getContainingList().storeNode(tx, this, true);
334    }
335
336    private void split(Transaction tx, boolean isAddFirst) throws IOException {
337        ListNode<Key, Value> extension = getContainingList().createNode(tx);
338        if (isAddFirst) {
339            // head keeps the first entry, insert extension with the rest
340            extension.setEntries(entries.getHead().splitAfter());
341            extension.setNext(this.getNext());
342            extension.store(tx, isAddFirst);
343            this.setNext(extension.getPageId());
344        } else {
345            extension.setEntries(entries.getTail().getPrevious().splitAfter());
346            extension.setNext(this.getNext());
347            extension.store(tx, isAddFirst);
348            getContainingList().setTailPageId(extension.getPageId());
349            this.setNext(extension.getPageId());
350        }
351        store(tx, true);
352    }
353
354    // called after a split
355    private void setEntries(LinkedNodeList<KeyValueEntry<Key, Value>> list) {
356        this.entries = list;
357    }
358
359    public Value get(Transaction tx, Key key) {
360        if (key == null) {
361            throw new IllegalArgumentException("Key cannot be null");
362        }
363        Value result = null;
364        KeyValueEntry<Key, Value> nextEntry = entries.getTail();
365        while (nextEntry != null) {
366            if (nextEntry.getKey().equals(key)) {
367                result = nextEntry.getValue();
368                break;
369            }
370            nextEntry = nextEntry.getPrevious();
371        }
372        return result;
373    }
374
375    public boolean isEmpty(final Transaction tx) {
376        return entries.isEmpty();
377    }
378
379    public Entry<Key, Value> getFirst(Transaction tx) {
380        return entries.getHead();
381    }
382
383    public Entry<Key, Value> getLast(Transaction tx) {
384        return entries.getTail();
385    }
386
387    public Iterator<Entry<Key, Value>> iterator(final Transaction tx, long pos) throws IOException {
388        return new ListIterator(tx, this, pos);
389    }
390
391    public Iterator<Entry<Key, Value>> iterator(final Transaction tx) throws IOException {
392        return new ListIterator(tx, this, 0);
393    }
394
395    Iterator<ListNode<Key, Value>> listNodeIterator(final Transaction tx) throws IOException {
396        return new ListNodeIterator(tx, this);
397    }
398
399    public void clear(Transaction tx) throws IOException {
400        entries.clear();
401        tx.free(this.getPageId());
402    }
403
404    public boolean contains(Transaction tx, Key key) {
405        if (key == null) {
406            throw new IllegalArgumentException("Key cannot be null");
407        }
408        boolean found = false;
409        KeyValueEntry<Key, Value> nextEntry = entries.getTail();
410        while (nextEntry != null) {
411            if (nextEntry.getKey().equals(key)) {
412                found = true;
413                break;
414            }
415            nextEntry = nextEntry.getPrevious();
416        }
417        return found;
418    }
419
420    // /////////////////////////////////////////////////////////////////
421    // Implementation methods
422    // /////////////////////////////////////////////////////////////////
423
424    public long getPageId() {
425        return page.getPageId();
426    }
427
428    public Page<ListNode<Key, Value>> getPage() {
429        return page;
430    }
431
432    public void setPage(Page<ListNode<Key, Value>> page) {
433        this.page = page;
434    }
435
436    public long getNext() {
437        return next;
438    }
439
440    public void setNext(long next) {
441        this.next = next;
442    }
443
444    public void setContainingList(ListIndex<Key, Value> list) {
445        this.containingList = list;
446    }
447
448    public ListIndex<Key, Value> getContainingList() {
449        return containingList;
450    }
451
452    public boolean isHead() {
453        return getPageId() == containingList.getHeadPageId();
454    }
455
456    public boolean isTail() {
457        return getPageId() == containingList.getTailPageId();
458    }
459
460    public int size(Transaction tx) {
461        return entries.size();
462    }
463
464    @Override
465    public String toString() {
466        return "[ListNode(" + (page != null ? page.getPageId() + "->" + next : "null") + ")[" + entries.size() + "]]";
467    }
468}