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.activemq.store.kahadb.disk.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.activemq.store.kahadb.disk.page.Page;
027    import org.apache.activemq.store.kahadb.disk.page.Transaction;
028    import org.apache.activemq.store.kahadb.disk.util.LinkedNode;
029    import org.apache.activemq.store.kahadb.disk.util.LinkedNodeList;
030    import org.apache.activemq.store.kahadb.disk.util.Marshaller;
031    import 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     */
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                            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    }