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