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}