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        @Override
070        public Key getKey() {
071            return key;
072        }
073
074        @Override
075        public Value getValue() {
076            return value;
077        }
078
079        @Override
080        public Value setValue(Value value) {
081            Value oldValue = this.value;
082            this.value = value;
083            return oldValue;
084        }
085
086        @Override
087        public String toString() {
088            return "{" + key + ":" + value + "}";
089        }
090    }
091
092    private final class ListNodeIterator implements Iterator<ListNode<Key, Value>> {
093
094        private final Transaction tx;
095        private final ListIndex<Key, Value> index;
096        ListNode<Key, Value> nextEntry;
097
098        private ListNodeIterator(Transaction tx, ListNode<Key, Value> current) {
099            this.tx = tx;
100            nextEntry = current;
101            index = current.getContainingList();
102        }
103
104        @Override
105        public boolean hasNext() {
106            return nextEntry != null;
107        }
108
109        @Override
110        public ListNode<Key, Value> next() {
111            ListNode<Key, Value> current = nextEntry;
112            if (current != null) {
113                if (current.next != ListIndex.NOT_SET) {
114                    try {
115                        nextEntry = index.loadNode(tx, current.next);
116                    } catch (IOException unexpected) {
117                        IllegalStateException e = new IllegalStateException("failed to load next: " + current.next + ", reason: "
118                                + unexpected.getLocalizedMessage());
119                        e.initCause(unexpected);
120                        throw e;
121                    }
122                } else {
123                    nextEntry = null;
124                }
125            }
126            return current;
127        }
128
129        @Override
130        public void remove() {
131            throw new UnsupportedOperationException();
132        }
133    }
134
135    final class ListIterator implements Iterator<Entry<Key, Value>> {
136
137        private final Transaction tx;
138        private final ListIndex<Key, Value> targetList;
139        ListNode<Key, Value> currentNode, previousNode;
140        KeyValueEntry<Key, Value> nextEntry;
141        KeyValueEntry<Key, Value> entryToRemove;
142
143        private ListIterator(Transaction tx, ListNode<Key, Value> current, long start) {
144            this.tx = tx;
145            this.currentNode = current;
146            this.targetList = current.getContainingList();
147            nextEntry = current.entries.getHead();
148            if (start > 0) {
149                moveToRequestedStart(start);
150            }
151        }
152
153        private void moveToRequestedStart(final long start) {
154            long count = 0;
155            while (hasNext() && count < start) {
156                next();
157                count++;
158            }
159            if (!hasNext()) {
160                throw new NoSuchElementException("Index " + start + " out of current range: " + count);
161            }
162        }
163
164        private KeyValueEntry<Key, Value> getFromNextNode() {
165            KeyValueEntry<Key, Value> result = null;
166            if (currentNode.getNext() != ListIndex.NOT_SET) {
167                try {
168                    previousNode = currentNode;
169                    currentNode = targetList.loadNode(tx, currentNode.getNext());
170                } catch (IOException unexpected) {
171                    NoSuchElementException e = new NoSuchElementException(unexpected.getLocalizedMessage());
172                    e.initCause(unexpected);
173                    throw e;
174                }
175                result = currentNode.entries.getHead();
176            }
177            return result;
178        }
179
180        @Override
181        public boolean hasNext() {
182            if (nextEntry == null) {
183                nextEntry = getFromNextNode();
184            }
185            return nextEntry != null;
186        }
187
188        @Override
189        public Entry<Key, Value> next() {
190            if (nextEntry != null) {
191                entryToRemove = nextEntry;
192                nextEntry = entryToRemove.getNext();
193                return entryToRemove;
194            } else {
195                throw new NoSuchElementException();
196            }
197        }
198
199        @Override
200        public void remove() {
201            if (entryToRemove == null) {
202                throw new IllegalStateException("can only remove once, call hasNext();next() again");
203            }
204            try {
205                entryToRemove.unlink();
206
207                ListNode<Key, Value> toRemoveNode = null;
208                if (currentNode.entries.isEmpty()) {
209                    // may need to free this node
210                    if (currentNode.isHead() && currentNode.isTail()) {
211                        // store empty list
212                    } else if (currentNode.isHead()) {
213                        // merge next node into existing headNode as we don't want to
214                        // change our headPageId b/c that is our identity
215                        ListNode<Key, Value> headNode = currentNode;
216                        nextEntry = getFromNextNode(); // will move currentNode
217
218                        if (currentNode.isTail()) {
219                            targetList.setTailPageId(headNode.getPageId());
220                        }
221                        // copy next/currentNode into head
222                        headNode.setEntries(currentNode.entries);
223                        headNode.setNext(currentNode.getNext());
224                        headNode.store(tx);
225                        toRemoveNode = currentNode;
226                        currentNode = headNode;
227
228                    } else if (currentNode.isTail()) {
229                        toRemoveNode = currentNode;
230                        previousNode.setNext(ListIndex.NOT_SET);
231                        previousNode.store(tx);
232                        targetList.setTailPageId(previousNode.getPageId());
233                    } else {
234                        toRemoveNode = currentNode;
235                        previousNode.setNext(toRemoveNode.getNext());
236                        previousNode.store(tx);
237                        currentNode = previousNode;
238                    }
239                }
240
241                targetList.onRemove(entryToRemove);
242                entryToRemove = null;
243
244                if (toRemoveNode != null) {
245                    tx.free(toRemoveNode.getPage());
246                } else {
247                    currentNode.store(tx);
248                }
249            } catch (IOException unexpected) {
250                IllegalStateException e = new IllegalStateException(unexpected.getLocalizedMessage());
251                e.initCause(unexpected);
252                throw e;
253            }
254        }
255
256        ListNode<Key, Value> getCurrent() {
257            return this.currentNode;
258        }
259    }
260
261    /**
262     * The Marshaller is used to store and load the data in the ListNode into a Page.
263     *
264     * @param <Key>
265     * @param <Value>
266     */
267    static public final class NodeMarshaller<Key, Value> extends VariableMarshaller<ListNode<Key, Value>> {
268        private final Marshaller<Key> keyMarshaller;
269        private final Marshaller<Value> valueMarshaller;
270
271        public NodeMarshaller(Marshaller<Key> keyMarshaller, Marshaller<Value> valueMarshaller) {
272            this.keyMarshaller = keyMarshaller;
273            this.valueMarshaller = valueMarshaller;
274        }
275
276        @Override
277        public void writePayload(ListNode<Key, Value> node, DataOutput os) throws IOException {
278            os.writeLong(node.next);
279            short count = (short) node.entries.size(); // cast may truncate
280                                                       // value...
281            if (count != node.entries.size()) {
282                throw new IOException("short over flow, too many entries in list: " + node.entries.size());
283            }
284
285            os.writeShort(count);
286            KeyValueEntry<Key, Value> entry = node.entries.getHead();
287            while (entry != null) {
288                keyMarshaller.writePayload((Key) entry.getKey(), os);
289                valueMarshaller.writePayload((Value) entry.getValue(), os);
290                entry = entry.getNext();
291            }
292        }
293
294        @Override
295        @SuppressWarnings({ "unchecked", "rawtypes" })
296        public ListNode<Key, Value> readPayload(DataInput is) throws IOException {
297            ListNode<Key, Value> node = new ListNode<Key, Value>();
298            node.setNext(is.readLong());
299            final short size = is.readShort();
300            for (short i = 0; i < size; i++) {
301                node.entries.addLast(new KeyValueEntry(keyMarshaller.readPayload(is), valueMarshaller.readPayload(is)));
302            }
303            return node;
304        }
305    }
306
307    public Value put(Transaction tx, Key key, Value value) throws IOException {
308        if (key == null) {
309            throw new IllegalArgumentException("Key cannot be null");
310        }
311        entries.addLast(new KeyValueEntry<Key, Value>(key, value));
312        store(tx, ADD_LAST);
313        return null;
314    }
315
316    public Value addFirst(Transaction tx, Key key, Value value) throws IOException {
317        if (key == null) {
318            throw new IllegalArgumentException("Key cannot be null");
319        }
320        entries.addFirst(new KeyValueEntry<Key, Value>(key, value));
321        store(tx, ADD_FIRST);
322        return null;
323    }
324
325    public void storeUpdate(Transaction tx) throws IOException {
326        store(tx, ADD_LAST);
327    }
328
329    private void store(Transaction tx, boolean addFirst) throws IOException {
330        try {
331            // keeping splitting till we get down to a single entry
332            // then we need to overflow the value
333            getContainingList().storeNode(tx, this, entries.size() == 1);
334
335            if (this.next == -1) {
336                getContainingList().setTailPageId(getPageId());
337            }
338
339        } catch (Transaction.PageOverflowIOException e) {
340            // If we get an overflow
341            split(tx, addFirst);
342        }
343    }
344
345    private void store(Transaction tx) throws IOException {
346        getContainingList().storeNode(tx, this, true);
347    }
348
349    private void split(Transaction tx, boolean isAddFirst) throws IOException {
350        ListNode<Key, Value> extension = getContainingList().createNode(tx);
351        if (isAddFirst) {
352            // head keeps the first entry, insert extension with the rest
353            extension.setEntries(entries.getHead().splitAfter());
354            extension.setNext(this.getNext());
355            extension.store(tx, isAddFirst);
356            this.setNext(extension.getPageId());
357        } else {
358            extension.setEntries(entries.getTail().getPrevious().splitAfter());
359            extension.setNext(this.getNext());
360            extension.store(tx, isAddFirst);
361            getContainingList().setTailPageId(extension.getPageId());
362            this.setNext(extension.getPageId());
363        }
364        store(tx, true);
365    }
366
367    // called after a split
368    private void setEntries(LinkedNodeList<KeyValueEntry<Key, Value>> list) {
369        this.entries = list;
370    }
371
372    public Value get(Transaction tx, Key key) {
373        if (key == null) {
374            throw new IllegalArgumentException("Key cannot be null");
375        }
376        Value result = null;
377        KeyValueEntry<Key, Value> nextEntry = entries.getTail();
378        while (nextEntry != null) {
379            if (nextEntry.getKey().equals(key)) {
380                result = nextEntry.getValue();
381                break;
382            }
383            nextEntry = nextEntry.getPrevious();
384        }
385        return result;
386    }
387
388    public boolean isEmpty(final Transaction tx) {
389        return entries.isEmpty();
390    }
391
392    public Entry<Key, Value> getFirst(Transaction tx) {
393        return entries.getHead();
394    }
395
396    public Entry<Key, Value> getLast(Transaction tx) {
397        return entries.getTail();
398    }
399
400    public Iterator<Entry<Key, Value>> iterator(final Transaction tx, long pos) throws IOException {
401        return new ListIterator(tx, this, pos);
402    }
403
404    public Iterator<Entry<Key, Value>> iterator(final Transaction tx) throws IOException {
405        return new ListIterator(tx, this, 0);
406    }
407
408    Iterator<ListNode<Key, Value>> listNodeIterator(final Transaction tx) throws IOException {
409        return new ListNodeIterator(tx, this);
410    }
411
412    public void clear(Transaction tx) throws IOException {
413        entries.clear();
414        tx.free(this.getPageId());
415    }
416
417    public boolean contains(Transaction tx, Key key) {
418        if (key == null) {
419            throw new IllegalArgumentException("Key cannot be null");
420        }
421        boolean found = false;
422        KeyValueEntry<Key, Value> nextEntry = entries.getTail();
423        while (nextEntry != null) {
424            if (nextEntry.getKey().equals(key)) {
425                found = true;
426                break;
427            }
428            nextEntry = nextEntry.getPrevious();
429        }
430        return found;
431    }
432
433    // /////////////////////////////////////////////////////////////////
434    // Implementation methods
435    // /////////////////////////////////////////////////////////////////
436
437    public long getPageId() {
438        return page.getPageId();
439    }
440
441    public Page<ListNode<Key, Value>> getPage() {
442        return page;
443    }
444
445    public void setPage(Page<ListNode<Key, Value>> page) {
446        this.page = page;
447    }
448
449    public long getNext() {
450        return next;
451    }
452
453    public void setNext(long next) {
454        this.next = next;
455    }
456
457    public void setContainingList(ListIndex<Key, Value> list) {
458        this.containingList = list;
459    }
460
461    public ListIndex<Key, Value> getContainingList() {
462        return containingList;
463    }
464
465    public boolean isHead() {
466        return getPageId() == containingList.getHeadPageId();
467    }
468
469    public boolean isTail() {
470        return getPageId() == containingList.getTailPageId();
471    }
472
473    public int size(Transaction tx) {
474        return entries.size();
475    }
476
477    @Override
478    public String toString() {
479        return "[ListNode(" + (page != null ? page.getPageId() + "->" + next : "null") + ")[" + entries.size() + "]]";
480    }
481}