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}