· 7 years ago · Oct 17, 2018, 07:12 AM
1package edu.berkeley.cs186.database.table;
2
3import java.util.Arrays;
4import java.io.Closeable;
5import java.nio.ByteBuffer;
6import java.util.Iterator;
7import java.util.List;
8import java.util.NoSuchElementException;
9import java.util.TreeSet;
10
11import edu.berkeley.cs186.database.DatabaseException;
12import edu.berkeley.cs186.database.common.ArrayBacktrackingIterator;
13import edu.berkeley.cs186.database.common.BacktrackingIterator;
14import edu.berkeley.cs186.database.common.Bits;
15import edu.berkeley.cs186.database.databox.DataBox;
16import edu.berkeley.cs186.database.io.Page;
17import edu.berkeley.cs186.database.io.PageAllocator;
18import edu.berkeley.cs186.database.io.PageAllocator.PageIterator;
19import edu.berkeley.cs186.database.table.stats.TableStats;
20
21/**
22 * # Overview
23 * A Table represents a database table with which users can insert, get,
24 * update, and delete records:
25 *
26 * // Create a brand new table t(x: int, y: int) which is persisted in the
27 * // file "t.table".
28 * List<String> fieldNames = Arrays.asList("x", "y");
29 * List<String> fieldTypes = Arrays.asList(Type.intType(), Type.intType());
30 * Schema schema = new Schema(fieldNames, fieldTypes);
31 * Table t = new Table(schema, "t", "t.table");
32 *
33 * // Insert, get, update, and delete records.
34 * List<DataBox> a = Arrays.asList(new IntDataBox(1), new IntDataBox(2));
35 * List<DataBox> b = Arrays.asList(new IntDataBox(3), new IntDataBox(4));
36 * RecordId rid = t.addRecord(a);
37 * Record ra = t.getRecord(rid);
38 * t.updateRecord(b, rid);
39 * Record rb = t.getRecord(rid);
40 * t.deleteRecord(rid);
41 *
42 * // Close the table. All tables must be closed.
43 * t.close();
44 *
45 * # Persistence
46 * Every table constructs a new PageAllocator which it uses to persist its data
47 * into a file. For example, the table above persists itself into a file
48 * "t.table". We can later run the following code to reload the table:
49 *
50 * // Load the table t from the file "t.table". Unlike above, we do not have
51 * // to specify the schema of t because it will be parsed from "t.table".
52 * Table t = new Table("t", "t.table");
53 * // Don't forget to close the table.
54 * t.close();
55 *
56 * # Storage Format
57 * Now, we discuss how tables serialize their data into files.
58 *
59 * 1. Each file begins with a header page into which tables serialize their
60 * schema.
61 * 2. All remaining pages are data pages. Every data page begins with an
62 * n-byte bitmap followed by m records. The bitmap indicates which records
63 * in the page are valid. The values of n and m are set to maximize the
64 * number of records per page (see computeDataPageNumbers for details).
65 *
66 * For example, here is a cartoon of what a table's file would look like if we
67 * had 5-byte pages and 1-byte records:
68 *
69 * Serialized Schema___________________________________
70 * / \
71 * +----------+----------+----------+----------+----------+ \
72 * Page 0 | 00000001 | 00000001 | 01111111 | 00000001 | 00000100 | |- header
73 * +----------+----------+----------+----------+----------+ /
74 * +----------+----------+----------+----------+----------+ \
75 * Page 1 | 1001xxxx | 01111010 | xxxxxxxx | xxxxxxxx | 01100001 | |
76 * +----------+----------+----------+----------+----------+ |
77 * Page 2 | 1101xxxx | 01110010 | 01100100 | xxxxxxxx | 01101111 | |- data
78 * +----------+----------+----------+----------+----------+ |
79 * Page 3 | 0011xxxx | xxxxxxxx | xxxxxxxx | 01111010 | 00100001 | |
80 * +----------+----------+----------+----------+----------+ /
81 * \________/ \________/ \________/ \________/ \________/
82 * bitmap record 0 record 1 record 2 record 3
83 *
84 * - The first page (Page 0) is the header page and contains the serialized
85 * schema.
86 * - The second page (Page 1) is a data page. The first byte of this data page
87 * is a bitmap, and the next four bytes are each records. The first and
88 * fourth bit are set indicating that record 0 and record 3 are valid.
89 * Record 1 and record 2 are invalid, so we ignore their contents.
90 * Similarly, the last four bits of the bitmap are unused, so we ignore
91 * their contents.
92 * - The third and fourth page (Page 2 and 3) are also data pages and are
93 * formatted similar to Page 1.
94 *
95 * When we add a record to a table, we add it to the very first free slot in
96 * the table. See addRecord for more information.
97 */
98public class Table implements Iterable<Record>, Closeable {
99 public static final String FILENAME_PREFIX = "db";
100 public static final String FILENAME_EXTENSION = ".table";
101
102 // The name of the database.
103 private String name;
104
105 // The filename of the file in which this table is persisted.
106 private String filename;
107
108 // The schema of the database.
109 private Schema schema;
110
111 // The allocator used to persist the database.
112 private PageAllocator allocator;
113
114 // The size (in bytes) of the bitmap found at the beginning of each data page.
115 private int bitmapSizeInBytes;
116
117 // The number of records on each data page.
118 private int numRecordsPerPage;
119
120 // Statistics about the contents of the database.
121 private TableStats stats;
122
123 // The page numbers of all allocated pages which have room for more records.
124 private TreeSet<Integer> freePageNums;
125
126 // The number of records in the table.
127 private long numRecords;
128
129 // Constructors //////////////////////////////////////////////////////////////
130 /**
131 * Construct a brand new table named `name` with schema `schema` persisted in
132 * file `filename`.
133 */
134 public Table(String name, Schema schema, String filename) {
135 this.name = name;
136 this.filename = filename;
137 this.schema = schema;
138 this.allocator = new PageAllocator(filename, true);
139 this.bitmapSizeInBytes = computeBitmapSizeInBytes(Page.pageSize, schema);
140 numRecordsPerPage = computeNumRecordsPerPage(Page.pageSize, schema);
141 this.stats = new TableStats(this.schema);
142 this.freePageNums = new TreeSet<Integer>();
143 this.numRecords = 0;
144
145 writeSchemaToHeaderPage(allocator, schema);
146 }
147
148 /**
149 * Load a table named `name` from the file `filename`. The schema of the
150 * table will be read from the header page of the file.
151 */
152 public Table(String name, String filename) throws DatabaseException {
153 this.name = name;
154 this.filename = filename;
155 this.allocator = new PageAllocator(filename, false);
156 this.schema = readSchemaFromHeaderPage(this.allocator);
157 this.bitmapSizeInBytes = computeBitmapSizeInBytes(Page.pageSize, this.schema);
158 this.numRecordsPerPage = computeNumRecordsPerPage(Page.pageSize, this.schema);
159
160 // We compute the stats, free pages, and number of records naively. We
161 // iterate through every single data page of the file, and for each data
162 // data page, we use the bitmap to read every single record.
163 this.stats = new TableStats(this.schema);
164 this.freePageNums = new TreeSet<Integer>();
165 this.numRecords = 0;
166
167 Iterator<Page> iter = this.allocator.iterator();
168 iter.next(); // Skip the header page.
169 while(iter.hasNext()) {
170 Page page = iter.next();
171 byte[] bitmap = getBitMap(page);
172
173 for (short i = 0; i < numRecordsPerPage; ++i) {
174 if (Bits.getBit(bitmap, i) == Bits.Bit.ONE) {
175 Record r = getRecord(new RecordId(page.getPageNum(), i));
176 stats.addRecord(r);
177 numRecords++;
178 }
179 }
180
181 if (numRecordsOnPage(page) != numRecordsPerPage) {
182 freePageNums.add(page.getPageNum());
183 }
184 }
185 }
186
187 // Accessors /////////////////////////////////////////////////////////////////
188 public String getName() {
189 return name;
190 }
191
192 public String getFilename() {
193 return filename;
194 }
195
196 public Schema getSchema() {
197 return schema;
198 }
199
200 public PageAllocator getAllocator() {
201 return allocator;
202 }
203
204 public int getBitmapSizeInBytes() {
205 return bitmapSizeInBytes;
206 }
207
208 public int getNumRecordsPerPage() {
209 return numRecordsPerPage;
210 }
211
212 public TableStats getStats() {
213 return stats;
214 }
215
216 public long getNumRecords() {
217 return numRecords;
218 }
219
220 public int getNumDataPages() {
221 // All pages but the first are data pages.
222 return allocator.getNumPages() - 1;
223 }
224
225 // TODO(mwhittaker): This should not be public. Right now, other code
226 // elsewhere reads the bitmap of tables, so we're forced to make it public.
227 // We should refactor to avoid this.
228 public byte[] getBitMap(Page page) {
229 byte[] bytes = new byte[bitmapSizeInBytes];
230 page.getByteBuffer().get(bytes);
231 return bytes;
232 }
233
234 public static int computeBitmapSizeInBytes(int pageSize, Schema schema) {
235 // Dividing by 8 simultaneously (a) rounds down the number of records to a
236 // multiple of 8 and (b) converts bits to bytes.
237 return computeUnroundedNumRecordsPerPage(pageSize, schema) / 8;
238 }
239
240 public static int computeNumRecordsPerPage(int pageSize, Schema schema) {
241 // Dividing by 8 and then multiplying by 8 rounds down to the nearest
242 // multiple of 8.
243 return computeUnroundedNumRecordsPerPage(pageSize, schema) / 8 * 8;
244 }
245
246
247 // Modifiers /////////////////////////////////////////////////////////////////
248 /**
249 * buildStatistics builds histograms on each of the columns of a table. Running
250 * it multiple times refreshes the statistics
251 */
252 public TableStats buildStatistics(int buckets){
253 this.stats.refreshHistograms(buckets, this);
254 return this.stats;
255 }
256
257 // Modifiers /////////////////////////////////////////////////////////////////
258 private synchronized void insertRecord(Page page, int entryNum, Record record) {
259 int offset = bitmapSizeInBytes + (entryNum * schema.getSizeInBytes());
260 byte[] bytes = record.toBytes(schema);
261 ByteBuffer buf = page.getByteBuffer();
262 buf.position(offset);
263 buf.put(bytes);
264 }
265
266 /**
267 * addRecord adds a record to this table and returns the record id of the
268 * newly added record. stats, freePageNums, and numRecords are updated
269 * accordingly. The record is added to the first free slot of the first free
270 * page (if one exists, otherwise one is allocated). For example, if the
271 * first free page has bitmap 0b11101000, then the record is inserted into
272 * the page with index 3 and the bitmap is updated to 0b11111000.
273 */
274 public synchronized RecordId addRecord(List<DataBox> values) throws DatabaseException {
275 Record record = schema.verify(values);
276
277 // Get a free page, allocating a new one if necessary.
278 if (freePageNums.isEmpty()) {
279 freePageNums.add(allocator.allocPage());
280 }
281 Page page = allocator.fetchPage(freePageNums.first());
282
283 // Find the first empty slot in the bitmap.
284 // entry number of the first free slot and store it in entryNum; and (2) we
285 // count the total number of entries on this page.
286 byte[] bitmap = getBitMap(page);
287 int entryNum = 0;
288 for (; entryNum < numRecordsPerPage; ++entryNum) {
289 if (Bits.getBit(bitmap, entryNum) == Bits.Bit.ZERO) {
290 break;
291 }
292 }
293 assert(entryNum < numRecordsPerPage);
294
295 // Insert the record and update the bitmap.
296 insertRecord(page, entryNum, record);
297 Bits.setBit(page.getByteBuffer(), entryNum, Bits.Bit.ONE);
298
299 // Update the metadata.
300 stats.addRecord(record);
301 if (numRecordsOnPage(page) == numRecordsPerPage) {
302 freePageNums.pollFirst();
303 }
304 numRecords++;
305
306 return new RecordId(page.getPageNum(), (short) entryNum);
307 }
308
309 /**
310 * Retrieves a record from the table, throwing an exception if no such record
311 * exists.
312 */
313 public synchronized Record getRecord(RecordId rid) throws DatabaseException {
314 validateRecordId(rid);
315 Page page = allocator.fetchPage(rid.getPageNum());
316 byte[] bitmap = getBitMap(page);
317 if (Bits.getBit(bitmap, rid.getEntryNum()) == Bits.Bit.ZERO) {
318 String msg = String.format("Record %s does not exist.", rid);
319 throw new DatabaseException(msg);
320 }
321
322 int offset = bitmapSizeInBytes + (rid.getEntryNum() * schema.getSizeInBytes());
323 ByteBuffer buf = page.getByteBuffer();
324 buf.position(offset);
325 return Record.fromBytes(buf, schema);
326 }
327
328 /**
329 * Overwrites an existing record with new values and returns the existing
330 * record. stats is updated accordingly. An exception is thrown if rid does
331 * not correspond to an existing record in the table.
332 */
333 public synchronized Record updateRecord(List<DataBox> values, RecordId rid) throws DatabaseException {
334 validateRecordId(rid);
335 Record newRecord = schema.verify(values);
336 Record oldRecord = getRecord(rid);
337
338 Page page = allocator.fetchPage(rid.getPageNum());
339 insertRecord(page, rid.getEntryNum(), newRecord);
340 this.stats.removeRecord(oldRecord);
341 this.stats.addRecord(newRecord);
342 return oldRecord;
343 }
344
345 /**
346 * Deletes and returns the record specified by rid from the table and updates
347 * stats, freePageNums, and numRecords as necessary. An exception is thrown
348 * if rid does not correspond to an existing record in the table.
349 */
350 public synchronized Record deleteRecord(RecordId rid) throws DatabaseException {
351 validateRecordId(rid);
352 Page page = allocator.fetchPage(rid.getPageNum());
353 Record record = getRecord(rid);
354 Bits.setBit(page.getByteBuffer(), rid.getEntryNum(), Bits.Bit.ZERO);
355
356 stats.removeRecord(record);
357 if(numRecordsOnPage(page) == numRecordsPerPage - 1) {
358 freePageNums.add(page.getPageNum());
359 }
360 numRecords--;
361
362 return record;
363 }
364
365 public void close() {
366 allocator.close();
367 }
368
369 // Helpers ///////////////////////////////////////////////////////////////////
370 private static Schema readSchemaFromHeaderPage(PageAllocator allocator) {
371 Page headerPage = allocator.fetchPage(0);
372 ByteBuffer buf = headerPage.getByteBuffer();
373 return Schema.fromBytes(buf);
374 }
375
376 private static void writeSchemaToHeaderPage(PageAllocator allocator, Schema schema) {
377 Page headerPage = allocator.fetchPage(allocator.allocPage());
378 assert(0 == headerPage.getPageNum());
379 ByteBuffer buf = headerPage.getByteBuffer();
380 buf.put(schema.toBytes());
381 }
382
383 /**
384 * Recall that every data page contains an m-byte bitmap followed by n
385 * records. The following three functions computes m and n such that n is
386 * maximized. To simplify things, we round n down to the nearest multiple of
387 * 8 if necessary. m and n are stored in bitmapSizeInBytes and
388 * numRecordsPerPage respectively.
389 *
390 * Some examples:
391 *
392 * | Page Size | Record Size | bitmapSizeInBytes | numRecordsPerPage |
393 * | --------- | ----------- | ----------------- | ----------------- |
394 * | 9 bytes | 1 byte | 1 | 8 |
395 * | 10 bytes | 1 byte | 1 | 8 |
396 * ...
397 * | 17 bytes | 1 byte | 1 | 8 |
398 * | 18 bytes | 2 byte | 2 | 16 |
399 * | 19 bytes | 2 byte | 2 | 16 |
400 */
401 private static int computeUnroundedNumRecordsPerPage(int pageSize, Schema schema) {
402 // Storing each record requires 1 bit for the bitmap and 8 *
403 // schema.getSizeInBytes() bits for the record.
404 int recordOverheadInBits = 1 + 8 * schema.getSizeInBytes();
405 int pageSizeInBits = pageSize * 8;
406 return pageSizeInBits / recordOverheadInBits;
407 }
408
409 private int numRecordsOnPage(Page page) {
410 byte[] bitmap = getBitMap(page);
411 int numRecords = 0;
412 for (int i = 0; i < numRecordsPerPage; ++i) {
413 if (Bits.getBit(bitmap, i) == Bits.Bit.ONE) {
414 numRecords++;
415 }
416 }
417 return numRecords;
418 }
419
420 private void validateRecordId(RecordId rid) throws DatabaseException {
421 int p = rid.getPageNum();
422 int e = rid.getEntryNum();
423
424 if (p == 0) {
425 throw new DatabaseException("Page 0 is a header page, not a data page.");
426 }
427
428 if (e < 0) {
429 String msg = String.format("Invalid negative entry number %d.", e);
430 throw new DatabaseException(msg);
431 }
432
433 if (e >= numRecordsPerPage) {
434 String msg = String.format(
435 "There are only %d records per page, but record %d was requested.",
436 numRecordsPerPage, e);
437 throw new DatabaseException(msg);
438 }
439 }
440
441 // Iterators /////////////////////////////////////////////////////////////////
442 public TableIterator ridIterator() {
443 return new TableIterator();
444 }
445
446 public RecordIterator iterator() {
447 return new RecordIterator(this, ridIterator());
448 }
449
450 public BacktrackingIterator<Record> blockIterator(Page[] block) {
451 return new RecordIterator(this, new RIDBlockIterator(block));
452 }
453
454 public BacktrackingIterator<Record> blockIterator(BacktrackingIterator<Page> block) {
455 return new RecordIterator(this, new RIDBlockIterator(block));
456 }
457
458 public BacktrackingIterator<Record> blockIterator(Iterator<Page> block, int maxRecords) {
459 return new RecordIterator(this, new RIDBlockIterator(block, maxRecords));
460 }
461
462 /**
463 * RIDPageIterator is a BacktrackingIterator over the RecordIds of a single
464 * page of the table.
465 *
466 * See comments on the BacktrackingIterator interface for how mark and reset
467 * should function.
468 */
469 public class RIDPageIterator implements BacktrackingIterator<RecordId> {
470 //member variables go here
471 int pageNum;
472 short entryNum;
473 byte[] bitmap;
474 short markIdx;
475
476 /**
477 * The following method signature is provided for guidance, but not necessary. Feel free to
478 * implement your own solution using whatever helper methods you would like.
479 */
480
481 public RIDPageIterator(Page page) {
482 pageNum = page.getPageNum();
483 bitmap = getBitMap(page);
484
485 //throw new UnsupportedOperationException("TODO(hw3): implement");
486 }
487
488 public boolean hasNext() {
489 for (int i = entryNum; i < 8* bitmap.length; i++) {
490 if (Bits.getBit(bitmap, i) == Bits.Bit.ONE) {
491 return true;
492 }
493 }
494 return false;
495 //throw new UnsupportedOperationException("TODO(hw3): implement");
496 }
497
498 public RecordId next() {
499 if (Bits.getBit(bitmap, entryNum) == Bits.Bit.ZERO) {
500 entryNum++;
501 }
502 RecordId r = new RecordId(pageNum,entryNum);
503 entryNum++;
504 return r;
505 //throw new UnsupportedOperationException("TODO(hw3): implement");
506 }
507
508 public void mark() {
509 if(entryNum - 1 < 0){
510 markIdx = 0;
511 }else{
512 markIdx = (short) (entryNum -1);
513 }
514 //throw new UnsupportedOperationException("TODO(hw3): implement");
515 }
516
517 public void reset() {
518 entryNum = markIdx;
519 //throw new UnsupportedOperationException("TODO(hw3): implement");
520 }
521 }
522
523 /**
524 * Helper function to create a BacktrackingIterator from an Iterator of
525 * Pages, and a maximum number of pages.
526 *
527 * At most maxPages pages will be loaded into the iterator; if there are
528 * not enough pages available, then fewer pages will be used.
529 */
530 private static BacktrackingIterator<Page> getBlockFromIterator(Iterator<Page> pageIter, int maxPages) {
531 Page[] block = new Page[maxPages];
532 int numPages;
533 for (numPages = 0; numPages < maxPages && pageIter.hasNext(); ++numPages) {
534 block[numPages] = pageIter.next();
535 }
536 if (numPages < maxPages) {
537 Page[] temp = new Page[numPages];
538 System.arraycopy(block, 0, temp, 0, numPages);
539 block = temp;
540 }
541 return new ArrayBacktrackingIterator(block);
542 }
543
544 /**
545 * RIDBlockIterator is a BacktrackingIterator yielding RecordIds of a block
546 * of pages.
547 *
548 * A "block" is specified by a BacktrackingIterator of Pages: every single
549 * Page returned by the iterator is part of the block. Your code should only
550 * utilize this iterator's functionality for fetching pages, i.e. you should
551 * *not* fetch every Page from the block iterator into an array or collection.
552 *
553 * The mark and reset methods have been provided for you already, and work by
554 * saving a BacktrackingIterator of RecordIds over the appropriate page.
555 *
556 * The iterator maintains a few pieces of state:
557 * - block is simply the BacktrackingIterator<Page> specifying the pages in
558 * the block.
559 * - blockIter is a BacktrackingIterator over RecordIds of the current page we
560 * are iterating over.
561 * - prevRecordId is the last RecordId that next() returned.
562 * - nextRecordId is the next RecordId that next() will return.
563 *
564 * In addition to these, we maintain some state to help with the
565 * implementation of mark() and reset(); you should not need to use these
566 * for implementing next() and hasNext().
567 */
568 public class RIDBlockIterator implements BacktrackingIterator<RecordId> {
569 private BacktrackingIterator<Page> block = null;
570 private BacktrackingIterator<RecordId> blockIter = null;
571
572 private BacktrackingIterator<RecordId> markedBlockIter = null;
573 private RecordId markedPrevRecordId = null;
574
575 private RecordId prevRecordId = null;
576 private RecordId nextRecordId = null;
577
578 public RIDBlockIterator(BacktrackingIterator<Page> block) {
579 this.block = block;
580 //throw new UnsupportedOperationException("TODO(hw3): implement");
581 //if you want to add anything to this constructor, feel free to
582 }
583
584 /**
585 * This is an extra constructor that allows one to create an
586 * RIDBlockIterator by taking the first maxPages of an iterator of Pages.
587 *
588 * If there are fewer than maxPages number of Pages available in pageIter,
589 * then all remaining pages shall be used in the "block"; otherwise,
590 * only the first maxPages number of pages shall be used.
591 *
592 * Note that this also advances pageIter by maxPages, so you can do the
593 * following:
594 *
595 * Iterator<Page> pageIter = // ...
596 * RIDBlockIterator firstBlock = new RIDBlockIterator(pageIter, 100);
597 * RIDBlockIterator secondBlock = new RIDBlockIterator(pageIter, 100);
598 * RIDBlockIterator thirdBlock = new RIDBlockIterator(pageIter, 100);
599 *
600 * to get iterators over the first 100 pages, second 100 pages, and third
601 * 100 pages.
602 */
603 public RIDBlockIterator(Iterator<Page> pageIter, int maxPages) {
604 this(Table.getBlockFromIterator(pageIter, maxPages));
605 }
606
607 /**
608 * This is an extra constructor that allows one to create an
609 * RIDBlockIterator over an array of Pages.
610 *
611 * Every page in the pages array will be used in the block of pages.
612 */
613 public RIDBlockIterator(Page[] pages) {
614 this(new ArrayBacktrackingIterator(pages));
615 }
616
617 public boolean hasNext() {
618 if (blockIter != null && blockIter.hasNext()) {
619 return true;
620 } else if(block.hasNext()) {
621 blockIter = new RIDPageIterator(block.next());
622 return blockIter.hasNext();
623 } else {
624 return false;
625 }
626 //throw new UnsupportedOperationException("TODO(hw3): implement");
627 }
628
629 public RecordId next() {
630 return blockIter.next();
631 //throw new UnsupportedOperationException("TODO(hw3): implement");
632 }
633
634 /**
635 * Marks the last recordId returned by next().
636 *
637 * This implementation of mark simply marks and saves the current page's
638 * iterator of RecordIds.
639 */
640 public void mark() {
641 if (this.prevRecordId == null) {
642 return;
643 }
644
645 this.block.mark();
646 this.blockIter.mark();
647 this.markedBlockIter = this.blockIter;
648 this.markedPrevRecordId = this.prevRecordId;
649 }
650
651 /**
652 * Resets to the marked recordId.
653 *
654 * This implementation of reset restores the marked page's iterator,
655 * and calls reset() on it to move it to the correct record. Some extra
656 * care is taken to ensure that we properly reset the block page iterator.
657 */
658 public void reset() {
659 if (this.markedPrevRecordId == null) {
660 return;
661 }
662 this.block.reset();
663 // We don't want to get the current page again
664 this.block.next();
665 this.blockIter = this.markedBlockIter;
666 this.blockIter.reset();
667 // If we're at the end of the block, we don't want to repeat the record
668 if (!this.block.hasNext()) {
669 this.blockIter.next();
670 if (this.blockIter.hasNext()) {
671 this.blockIter.reset();
672 }
673 }
674
675 this.prevRecordId = null;
676 this.nextRecordId = this.markedPrevRecordId;
677 }
678 }
679
680 /**
681 * A helper function that returns the same iterator passed in, but with
682 * a single page skipped.
683 */
684 private static Iterator<Page> iteratorSkipPage(Iterator<Page> iter) {
685 iter.next();
686 return iter;
687 }
688
689 /**
690 * TableIterator is an Iterator over the record IDs of a table.
691 *
692 * This is just a very thin wrapper around RIDBlockIterator, where the "block"
693 * is an iterator of all the pages of the table (minus the header page). Once
694 * RIDBlockIterator is filled in, all tests on TableIterator should
695 * automatically pass.
696 */
697 public class TableIterator extends RIDBlockIterator {
698 public TableIterator() {
699 super((BacktrackingIterator<Page>) Table.iteratorSkipPage(Table.this.allocator.iterator()));
700 }
701 }
702 }