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