1 /* Copyright (C) 2014 InfiniDB, Inc.
2
3 This program is free software; you can redistribute it and/or
4 modify it under the terms of the GNU General Public License
5 as published by the Free Software Foundation; version 2 of
6 the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
16 MA 02110-1301, USA. */
17
18 /* ========================================================================== */
19 /* */
20 /* Filename.c */
21 /* (c) 2001 Author */
22 /* */
23 /* Description */
24 /* */
25 /* ========================================================================== */
26 #include <stdio.h>
27 #include <string.h>
28 #ifndef _MSC_VER
29 #include <inttypes.h>
30 #endif
31 #include "we_indextree.h"
32 #include "we_indexlist.h"
33
34
35 using namespace std;
36
37 namespace WriteEngine
38 {
39
40 /************************************************
41 * Description:
42 * Find a entry for the given rowId and Key
43 * Then Delete it from the list
44 * Move the rest of the row id up in the same
45 * sub block an decrement the count in that subblock
46 * decrement the header size
47 * Converted
48 * input
49 * pFile -- File Handler
50 * rowId -- row id
51 * key -- value
52 * curIdxRidListHdrPtr - point to the header
53 *
54 * return value
55 * Success -- 0
56 * Fail -- ERR_IDX_LIST_INVALID_DELETE
57 ************************************************/
deleteInSub(const RID & rowId)58 const int IndexList::deleteInSub( const RID& rowId)
59 {
60
61 int rc = ERR_IDX_LIST_INVALID_DELETE;
62 DataBlock prevDataBlock;
63 int pos = 0, totalbytes = 0;
64 IdxRidListPtr* lastIdxRidListPtr;
65 int type;
66
67 CommBlock cb;
68 cb.file.oid = m_oid;
69 cb.file.pFile = m_pFile;
70
71 //get thelbid sbid and entry out from the header last entry
72 //First Sub-block
73 m_lbid = ((IdxEmptyListEntry*) & (m_curIdxRidListHdr.nextIdxRidListPtr))->fbo;
74 m_sbid = ((IdxEmptyListEntry*) & (m_curIdxRidListHdr.nextIdxRidListPtr))->sbid;
75 m_entry = ((IdxEmptyListEntry*) & (m_curIdxRidListHdr.nextIdxRidListPtr))->entry;
76 //Read the pointer entry at LIST_SUB_LLP_POS location
77
78 IdxRidListEntry rowIdArray[MAX_BLOCK_ENTRY];
79 IdxRidListEntry newRowIdArray[MAX_BLOCK_ENTRY];
80 memset(rowIdArray, 0, BYTE_PER_BLOCK);
81 memset(newRowIdArray, 0, BYTE_PER_BLOCK);
82 //First link
83 pos = LIST_SUB_LLP_POS;
84 totalbytes = SUBBLOCK_TOTAL_BYTES;
85 m_entryGroup = ENTRY_32;
86
87 if (m_lbid != m_hdrLbid)
88 {
89 rc = readDBFile(cb, &m_curBlock, m_lbid );
90
91 if (rc != NO_ERROR)
92 return rc;
93
94 rc = readSubBlockEntry(cb, &m_curBlock, m_lbid,
95 m_sbid, 0, totalbytes,
96 rowIdArray);
97
98 if (rc != NO_ERROR)
99 return rc;
100
101 m_curBlock.dirty = true;
102 m_curBlock.lbid = m_lbid;
103 m_curBlock.state = BLK_READ;
104 }
105 else
106 {
107 if (m_hdrBlock.state >= BLK_READ)
108 getSubBlockEntry(m_hdrBlock.data, m_sbid,
109 0, totalbytes, rowIdArray );
110 else
111 return ERR_IDX_LIST_INVALID_DELETE;
112 }
113
114 lastIdxRidListPtr = (IdxRidListPtr*)&rowIdArray[pos];
115 int count;
116 type = lastIdxRidListPtr->type; //next type
117 count = lastIdxRidListPtr->count;//current count
118
119 for (int i = 0; i < count; i++)
120 {
121 if (rowIdArray[i].rid == rowId)
122 {
123 //found
124 m_dLbid = m_lbid;
125 m_dSbid = m_sbid;
126 m_dEntry = i;
127 rc = NO_ERROR;
128 memcpy(&newRowIdArray[0],
129 &rowIdArray[0], totalbytes);
130 lastIdxRidListPtr->count--;
131
132 if (lastIdxRidListPtr->count == 0)
133 {
134 if (type == LIST_SIZE_TYPE)
135 {
136 //header has no link
137 m_curIdxRidListHdr.nextIdxRidListPtr.type
138 = LIST_NOT_USED_TYPE;
139 m_curIdxRidListHdr.nextIdxRidListPtr.llp = 0;
140
141 }
142 }//header's link block has nothing now
143 else //still have more
144 {
145 memcpy(&rowIdArray[i], &newRowIdArray[i + 1], (count - (i + 1))*LIST_ENTRY_WIDTH);
146 }
147
148 //last row id entry now moved up, so not used
149 rowIdArray[count - 1].type = LIST_NOT_USED_TYPE;
150 rowIdArray[count - 1].rid = 0;
151 rowIdArray[count - 1].spare = 0;
152 //header update the size
153 m_curIdxRidListHdr.idxRidListSize.size--;
154
155 if (m_lbid != m_hdrLbid)
156 {
157 setSubBlockEntry( m_curBlock.data,
158 m_sbid, 0, totalbytes,
159 rowIdArray );
160 rc = writeDBFile( cb, m_curBlock.data, m_lbid);
161
162 if (rc != NO_ERROR)
163 return rc;
164
165 m_curBlock.state = BLK_READ;
166 rc = writeSubBlockEntry(cb, &m_hdrBlock,
167 m_hdrLbid, m_hdrSbid,
168 m_hdrEntry,
169 LIST_HDR_SIZE,
170 &m_curIdxRidListHdr );
171
172 if (rc != NO_ERROR)
173 return rc;
174
175 m_hdrBlock.state = BLK_READ;
176 }
177 else
178 {
179 //m_lbid==m_hdrLbid
180 setSubBlockEntry( m_hdrBlock.data,
181 m_sbid, 0, totalbytes,
182 rowIdArray );
183 setSubBlockEntry( m_hdrBlock.data,
184 m_hdrSbid, m_hdrEntry,
185 LIST_HDR_SIZE,
186 &m_curIdxRidListHdr);
187 m_hdrBlock.state = BLK_WRITE;
188 rc = writeDBFile( cb, m_hdrBlock.data,
189 m_hdrLbid);
190
191 if (rc != NO_ERROR)
192 return rc;
193
194 m_hdrBlock.state = BLK_READ;
195 } //end if m_lbid==m_hdrHdrLbid
196
197 m_dEntry = i;
198 return rc;
199 }//endif found
200 }//end for
201
202 return rc;
203 }
204 /************************************************
205 * Description:
206 * Find a entry for the given rowId and Key
207 * Then Delete it from the list
208 * Move the rest of the row id up in the same
209 * sub block an decrement the count in that subblock
210 * decrement the header size
211 * Converted
212 * input
213 * pFile -- File Handler
214 * rowId -- row id
215 * key -- value
216 * curIdxRidListHdrPtr - point to the header
217 *
218 * return value
219 * Success -- 0
220 * Fail -- ERR_IDX_LIST_INVALID_DELETE
221 ************************************************/
222
deleteInBlock(const RID & rowId)223 const int IndexList::deleteInBlock(const RID& rowId)
224 {
225 int width = LIST_ENTRY_WIDTH;
226 int rc = ERR_IDX_LIST_INVALID_DELETE;
227 IdxRidListPtr* lastIdxRidListPtr;
228 IdxRidListPtr lastSubIdxRidListPtr;
229 bool found;
230 int type, count;
231 IdxRidListPtr prevIdxRidListPtr;
232 int prevSbid, prevEntry, prevType;
233 uint64_t prevLbid;
234 DataBlock prevDataBlock;
235 int pos = 0, totalbytes = 0;
236 int preTotalBytes, prevPos ;
237 //IdxRidNextListPtr *nextIdxListPtr;
238
239 IdxRidListEntry rowIdArray[MAX_BLOCK_ENTRY];
240 IdxRidListEntry newRowIdArray[MAX_BLOCK_ENTRY];
241
242 CommBlock cb;
243 cb.file.oid = m_oid;
244 cb.file.pFile = m_pFile;
245 //This is the sub block info
246 prevLbid = m_lbid;
247 prevSbid = m_sbid;
248 prevEntry = m_entry;
249 prevPos = LIST_SUB_LLP_POS;
250 preTotalBytes = SUBBLOCK_TOTAL_BYTES;
251
252 if (prevLbid == m_hdrLbid)
253 {
254 if (m_hdrBlock.state >= BLK_READ)
255 getSubBlockEntry(m_hdrBlock.data, m_sbid,
256 prevPos, LIST_ENTRY_WIDTH, &lastSubIdxRidListPtr );
257 else
258 return ERR_IDX_LIST_INVALID_DELETE;
259 }
260 else
261 {
262 if (m_curBlock.state >= BLK_READ)
263 getSubBlockEntry(m_curBlock.data, m_sbid,
264 prevPos, LIST_ENTRY_WIDTH, &lastSubIdxRidListPtr );
265 else
266 return ERR_IDX_LIST_INVALID_DELETE;
267 }
268
269 found = false;
270 m_lbid = ((IdxEmptyListEntry*)&lastSubIdxRidListPtr)->fbo;
271 m_sbid = 0;
272 m_entry = 0;
273
274 type = lastSubIdxRidListPtr.type;
275 count = lastSubIdxRidListPtr.count;
276 pos = LIST_BLOCK_LLP_POS;
277 totalbytes = BYTE_PER_BLOCK;
278
279 //Not found in the first sub
280 while ((!found) && (type == LIST_BLOCK_TYPE))
281 {
282 rc = readSubBlockEntry(cb, &m_curBlock, m_lbid, 0, 0,
283 totalbytes, rowIdArray);
284
285 if (rc != NO_ERROR)
286 return rc;
287
288 m_curBlock.dirty = true;
289 m_curBlock.state = BLK_READ;
290 m_curBlock.lbid = m_lbid;
291 prevType = type; //Save it just in case not found here
292 lastIdxRidListPtr = (IdxRidListPtr*) &rowIdArray[pos];
293 type = lastIdxRidListPtr->type;
294 count = lastIdxRidListPtr->count;
295
296 //prepared for not found in current block
297 //find out what is the next type
298 //Next Type is needed here
299 for (int i = 0; i < count; i++)
300 {
301 if (rowIdArray[i].rid == rowId)
302 {
303 //found the rowid
304 memcpy(&newRowIdArray[0], &rowIdArray[0], totalbytes);
305 found = true;
306 m_dLbid = m_lbid;
307 m_dSbid = m_sbid;
308 m_dEntry = i;
309 lastIdxRidListPtr->count--;
310
311 if (lastIdxRidListPtr->count == 0)
312 {
313 if (!m_useNarray)
314 {
315 //get the previous value out, could be a sub block
316 if (prevLbid == m_hdrLbid)
317 getSubBlockEntry(m_hdrBlock.data, prevSbid,
318 prevPos, LIST_ENTRY_WIDTH,
319 &prevIdxRidListPtr);
320 else if (prevLbid == m_lbid)
321 getSubBlockEntry(m_curBlock.data, prevSbid,
322 prevPos, LIST_ENTRY_WIDTH,
323 &prevIdxRidListPtr);
324 else
325 rc = readSubBlockEntry(cb, &prevDataBlock, prevLbid,
326 prevSbid, prevPos, LIST_ENTRY_WIDTH,
327 &prevIdxRidListPtr);
328
329 if (rc != NO_ERROR)
330 return rc;
331
332 //check the type before set
333 if (type == LIST_BLOCK_TYPE)
334 {
335 ((IdxEmptyListEntry*)&prevIdxRidListPtr)->fbo
336 = ((IdxEmptyListEntry*)lastIdxRidListPtr)->fbo;
337 ((IdxEmptyListEntry*)&prevIdxRidListPtr)->sbid
338 = ((IdxEmptyListEntry*)lastIdxRidListPtr)->sbid;
339 ((IdxEmptyListEntry*)&prevIdxRidListPtr)->entry
340 = ((IdxEmptyListEntry*)lastIdxRidListPtr)->entry;
341 //safety check
342 prevIdxRidListPtr.type = type;
343 }
344 else // If no more links, the current one is gone also
345 {
346 if (prevIdxRidListPtr.count > 0)
347 {
348 prevIdxRidListPtr.type = 0;
349 prevIdxRidListPtr.llp = 0;
350 }
351 else
352 {
353 //In case it is a sub block, not released with 0 count
354 prevIdxRidListPtr.type = LIST_NOT_USED_TYPE;
355 prevIdxRidListPtr.llp = 0;
356 }
357 }//end if type =LIST_SUBBLOCK_TYPE,LIST_BLOCK_TYPE
358
359 //;set to LIST_NOT_USED_TYPE--unused before release
360 lastIdxRidListPtr->type = LIST_NOT_USED_TYPE;
361 lastIdxRidListPtr->llp = 0;
362
363 if (prevPos == LIST_BLOCK_LLP_POS)
364 {
365 if (prevLbid < m_lastLbid)
366 rc = setLastLbid(prevLbid);
367 }
368 }
369 } //end if count==0
370 else
371 {
372 memcpy(&rowIdArray[i], &newRowIdArray[i + 1], (count - (i + 1))*LIST_ENTRY_WIDTH);
373
374 if (m_lastLbid > m_lbid)
375 rc = setLastLbid(m_lbid);
376
377 }//count check
378
379 //Found rowId
380 rowIdArray[count - 1].type = LIST_NOT_USED_TYPE;
381 rowIdArray[count - 1].rid = 0;
382
383 m_curIdxRidListHdr.idxRidListSize.size--;
384 //Write Out Put in another routine
385
386 if ((prevLbid == m_hdrLbid) && (m_lbid != m_hdrLbid))
387 {
388 // AAC --3
389 if (!m_useNarray)
390 {
391 if (lastIdxRidListPtr->count == 0)
392 {
393 setSubBlockEntry( m_hdrBlock.data, prevSbid,
394 prevPos, width,
395 &prevIdxRidListPtr );
396 }
397 }
398
399 setSubBlockEntry( m_curBlock.data, m_sbid,
400 0, totalbytes,
401 rowIdArray );
402 setSubBlockEntry( m_hdrBlock.data, m_hdrSbid,
403 m_hdrEntry, LIST_HDR_SIZE,
404 &m_curIdxRidListHdr );
405 rc = writeDBFile( cb, m_hdrBlock.data, m_hdrLbid);
406
407 if (rc != NO_ERROR)
408 return rc;
409
410 rc = writeDBFile( cb, m_curBlock.data, m_lbid);
411
412 if (rc != NO_ERROR)
413 return rc;
414
415 m_hdrBlock.state = BLK_READ;
416 m_curBlock.state = BLK_READ;
417 }
418 else
419 {
420 //ABC --
421 if (!m_useNarray)
422 {
423 if (lastIdxRidListPtr->count == 0)
424 {
425 setSubBlockEntry( prevDataBlock.data, prevSbid,
426 prevPos, LIST_ENTRY_WIDTH,
427 &prevIdxRidListPtr );
428 rc = writeDBFile( cb, prevDataBlock.data, prevLbid);
429
430 if (rc != NO_ERROR)
431 return rc;
432 }
433 }
434
435 setSubBlockEntry( m_curBlock.data, m_sbid,
436 0, totalbytes,
437 rowIdArray );
438 setSubBlockEntry( m_hdrBlock.data, m_hdrSbid,
439 m_hdrEntry, LIST_HDR_SIZE,
440 &m_curIdxRidListHdr );
441 rc = writeDBFile( cb, m_hdrBlock.data, m_hdrLbid);
442
443 if (rc != NO_ERROR)
444 return rc;
445
446 rc = writeDBFile( cb, m_curBlock.data, m_lbid);
447 memset(m_hdrBlock.data, 0,
448 sizeof(m_hdrBlock.data));
449
450 if (rc != NO_ERROR)
451 return rc;
452
453 m_hdrBlock.state = BLK_READ;
454 m_curBlock.state = BLK_READ;
455 } //last case A B C --end 5
456
457 //Done with writing to disk
458 // Now we need to release the segment
459 if (!m_useNarray)
460 {
461 if (lastIdxRidListPtr->count == 0)
462 {
463 rc = releaseSegment();
464
465 if (rc != NO_ERROR)
466 return rc;
467 }// end release segment when count ==0
468 }
469
470 m_entry = i; //for use in findRow ID
471 return rc; //DONE !!!found then we return, no need to go on
472 }//FOUND THE ROWID returned !!!!
473 }//for loop i not found continue to i++
474
475 //NOT FOUND in this block go to next block
476 //assigning the current llp as previous llp:lbid, sbid, entry
477 prevLbid = m_lbid;
478 prevSbid = 0;
479 prevEntry = 0;
480 prevPos = pos;
481 preTotalBytes = totalbytes;
482
483 m_lbid = ((IdxEmptyListEntry*)lastIdxRidListPtr)->fbo;
484 m_sbid = 0;
485 m_entry = 0;
486 }// end while
487
488 if (!found)
489 rc = ERR_IDX_LIST_INVALID_DELETE;
490
491 return rc;
492 }
493
494
495 /************************************************
496 * Description:
497 * Converted
498 * Find an entry for the given rowId and Key
499 * Then Delete it from the list
500 * Move the rest of the row id up in the same
501 * sub block an decrement the count in that subblock
502 * decrement the header size
503 * input
504 * pFile -- File Handler
505 * rowId -- row id
506 * key -- value
507 * curIdxRidListHdrPtr - point to the header
508 *
509 * return value
510 * Success -- 0
511 * Fail -- ERR_IDX_LIST_INVALID_DELETE
512 ************************************************/
deleteIndexList(FILE * pFile,const RID & rowId,const uint64_t & key,IdxEmptyListEntry * curIdxRidListHdrPtr,uint64_t & lbid,int & sbid,int & entry)513 const int IndexList::deleteIndexList( FILE* pFile, const RID& rowId,
514 const uint64_t& key, IdxEmptyListEntry* curIdxRidListHdrPtr,
515 uint64_t& lbid, int& sbid, int& entry)
516 {
517 int rc = ERR_IDX_LIST_INVALID_DELETE;
518 bool found = false;
519
520 m_pFile = pFile;
521 getHdrInfo(curIdxRidListHdrPtr);
522
523 if (key != m_curIdxRidListHdr.key)
524 {
525 return ERR_IDX_LIST_INVALID_KEY;
526 }
527
528 uint64_t dlbid = -1LL;
529 int dsbid = -1;
530 int dentry = -1;
531 rc = deleteIndexList(rowId, key, dlbid, dsbid, dentry);
532
533 if (rc != NO_ERROR)
534 {
535 lbid = -1LL;
536 sbid = -1;
537 entry = -1;
538 found = false;
539 return rc;
540 }
541 else
542 {
543 lbid = dlbid;
544 sbid = dsbid;
545 entry = dentry;
546 }
547
548 return rc;
549 }
550 /************************************************
551 * Description:
552 * No change
553 * Find a entry for the given rowId and Key
554 * Then Delete it from the list
555 * Move the rest of the row id up in the same
556 * sub block an decrement the count in that subblock
557 * decrement the header size
558 * input
559 * pFile -- File Handler
560 * rowId -- row id
561 * key -- value
562 * curIdxRidListHdrPtr - point to the header
563 *
564 * return value
565 * Success -- 0
566 * Fail -- ERR_IDX_LIST_INVALID_DELETE
567 ************************************************/
deleteIndexList(const RID & rowId,const uint64_t & key,uint64_t & lbid,int & sbid,int & entry)568 const int IndexList::deleteIndexList(const RID& rowId,
569 const uint64_t& key,
570 uint64_t& lbid, int& sbid, int& entry)
571 {
572 int rc = ERR_IDX_LIST_INVALID_DELETE;
573 rc = deleteIndexList(rowId, key);
574
575 lbid = m_dLbid;
576 sbid = m_dSbid;
577 entry = m_dEntry;
578 return rc;
579 }
580 /************************************************
581 * Description:
582 * Converted
583 * Find all of the row Id or toke from list
584 * input
585 * pFile -- File Handler
586 * curIdxRidListHdrPtr - point to the header
587 *
588 * return value
589 * Success -- 0
590 * Fail -- ERR_IDX_LIST_INVALID_DELETE
591 ************************************************/
getRIDArrayFromListHdr(FILE * pFile,uint64_t & key,IdxEmptyListEntry * curIdxRidListHdrPtr,RID * ridArray,int & size)592 const int IndexList::getRIDArrayFromListHdr(FILE* pFile, uint64_t& key,
593 IdxEmptyListEntry* curIdxRidListHdrPtr,
594 RID* ridArray, int& size)
595 {
596 int rc = NO_ERROR;
597 int arrayCount = 0;
598 IdxRidNextListPtr* nextIdxListPtr = NULL;
599
600 m_pFile = pFile;
601 CommBlock cb;
602 cb.file.oid = m_oid;
603 cb.file.pFile = m_pFile;
604
605 rc = getHdrInfo(curIdxRidListHdrPtr);
606
607 if (m_curIdxRidListHdr.idxRidListSize.size == 0)
608 {
609 size = 0;
610 return NO_ERROR;
611 }
612
613 if (key != m_curIdxRidListHdr.key)
614 {
615 return ERR_IDX_LIST_WRONG_KEY;
616 }
617
618 // cout << "IndexList::getRIDArrayFromListHdr->KEY ------>" << key << endl;
619 //Check the first row location, 3rd enty
620 if (m_curIdxRidListHdr.firstIdxRidListEntry.type == (int)LIST_RID_TYPE)
621 {
622 ridArray[arrayCount] = (RID)m_curIdxRidListHdr.firstIdxRidListEntry.rid;
623 //cout<<" IndexList::getRIDArrayFromListHdr->header Lbid->" << m_hdrLbid <<" count->" << arrayCount <<endl;
624
625 arrayCount++;
626 //cout << "RID = " << (RID)m_curIdxRidListHdr.firstIdxRidListEntry.rid << endl;
627 };
628
629 //Check Header last entry's type
630 int type = m_curIdxRidListHdr.nextIdxRidListPtr.type;
631
632 switch (type)
633 {
634 case LIST_RID_TYPE:// There is a row id here, Check!
635 ridArray[arrayCount] = (RID)m_curIdxRidListHdr.nextIdxRidListPtr.llp;
636 //cout<<"arrayCount->" << arrayCount << "rid->" << ridArray[arrayCount]<<endl;
637 arrayCount++;
638 //cout << "RID = " << (RID)m_curIdxRidListHdr.nextIdxRidListPtr.llp << endl;
639
640 size = arrayCount;
641 return NO_ERROR;
642
643 case LIST_SUBBLOCK_TYPE://Not found in header, so go to the sub-block
644 //get thelbid sbid and entry out from the header last entry
645
646 m_lbid = ((IdxEmptyListEntry*) & (m_curIdxRidListHdr.nextIdxRidListPtr))->fbo;
647 m_sbid = ((IdxEmptyListEntry*) & (m_curIdxRidListHdr.nextIdxRidListPtr))->sbid;
648 m_entry = ((IdxEmptyListEntry*) & (m_curIdxRidListHdr.nextIdxRidListPtr))->entry;
649 m_curType = type;
650 //Read the pointer entry at LIST_SUB_LLP_POS location
651 IdxRidListPtr* lastIdxRidListPtr;
652 IdxRidListEntry rowIdArray[MAX_BLOCK_ENTRY];
653 memset(rowIdArray, 0, BYTE_PER_BLOCK);
654 int pos = 0, totalbytes = 0;
655 pos = LIST_SUB_LLP_POS;
656 totalbytes = SUBBLOCK_TOTAL_BYTES;
657
658 if (m_lbid != m_hdrLbid)
659 {
660 rc = readSubBlockEntry(cb, &m_curBlock, m_lbid,
661 m_sbid, 0, totalbytes,
662 rowIdArray);
663 m_curBlock.lbid = m_lbid;
664 m_curBlock.state = BLK_READ;
665 m_curBlock.dirty = true;
666 }
667 else
668 getSubBlockEntry(m_hdrBlock.data, m_sbid,
669 0, totalbytes,
670 rowIdArray );
671
672 int type, count;
673
674 lastIdxRidListPtr = (IdxRidListPtr*) &rowIdArray[pos];
675 type = lastIdxRidListPtr->type;
676 count = lastIdxRidListPtr->count;
677
678 //cout << "count->" << count << endl;
679 //type should be LIST_BLOCK_TYPE from now on
680 for (int i = 0; i < count; i++)
681 {
682 ridArray[arrayCount] = (RID)(rowIdArray[i].rid);
683 //cout << "RID =" << (RID)(rowIdArray[i].rid) << endl;
684 //cout<<"arrayCount->" << arrayCount << "rid->" << ridArray[arrayCount]<<endl;
685 arrayCount++;
686 }
687
688 //cout << " Lbid->" << m_lbid ;
689 //cout << " count->" << count << endl;
690 m_lbid = ((IdxEmptyListEntry*)lastIdxRidListPtr)->fbo;
691
692 while (type == LIST_BLOCK_TYPE)
693 {
694 //cout << " Lbid->" << m_lbid ;
695
696 pos = LIST_BLOCK_LLP_POS;
697 totalbytes = BYTE_PER_BLOCK;
698 rc = readSubBlockEntry(cb, &m_curBlock, m_lbid, 0, 0,
699 totalbytes, rowIdArray);
700 m_curBlock.lbid = m_lbid;
701 m_curBlock.state = BLK_READ;
702 m_curBlock.dirty = true;
703
704 if (!m_useNarray)
705 {
706 lastIdxRidListPtr = (IdxRidListPtr*) &rowIdArray[pos];
707 type = lastIdxRidListPtr->type;
708 count = lastIdxRidListPtr->count;
709 }
710 else
711 {
712 nextIdxListPtr = (IdxRidNextListPtr*)&rowIdArray[pos];
713 type = nextIdxListPtr->type;
714 count = nextIdxListPtr->count;
715 }
716
717 //cout << " count->" << count << endl;
718 for (int i = 0; i < count; i++)
719 {
720 ridArray[arrayCount] = (RID)(rowIdArray[i].rid) ;
721 //cout << "RID =" << (RID)(rowIdArray[i].rid) << endl;
722 //cout<<"arrayCount->" << arrayCount << "rid->" << ridArray[arrayCount]<<endl;
723 arrayCount++;
724 }
725
726 if (type == LIST_BLOCK_TYPE)
727 {
728 if (m_useNarray)
729 m_lbid = nextIdxListPtr->nextLbid;
730 else
731 m_lbid = ((IdxEmptyListEntry*)lastIdxRidListPtr)->fbo;
732 }
733
734 }//end while
735 };//end of switch
736
737 size = arrayCount;
738
739 return rc;
740 }//end getRIDArrayFromListHdr
741
getRIDArrayFromListHdrNarray(FILE * pFile,uint64_t & key,IdxEmptyListEntry * curIdxRidListHdrPtr,RID * ridArray,int & size,bool flag)742 const int IndexList::getRIDArrayFromListHdrNarray(FILE* pFile, uint64_t& key,
743 IdxEmptyListEntry* curIdxRidListHdrPtr,
744 RID* ridArray, int& size, bool flag)
745 {
746 int rc = NO_ERROR;
747 IdxRidNextListPtr* nextIdxListPtr;
748 int pos = 0, totalbytes = 0;
749 IdxRidListPtr* lastIdxRidListPtr;
750 IdxRidListEntry rowIdArray[MAX_BLOCK_ENTRY * 10];
751 int type = 0, count = 0;
752
753
754
755 m_pFile = pFile;
756 CommBlock cb;
757 cb.file.oid = m_oid;
758 cb.file.pFile = m_pFile;
759
760 if (flag)
761 {
762 rc = getHdrInfo(curIdxRidListHdrPtr);
763
764 if (m_curIdxRidListHdr.idxRidListSize.size == 0)
765 {
766 size = 0;
767 return NO_ERROR;
768 }
769
770 if (key != m_curIdxRidListHdr.key)
771 {
772 return ERR_IDX_LIST_WRONG_KEY;
773 }
774
775 // cout << "IndexList::getRIDArrayFromListHdr->KEY ------>" << key << endl;
776 //Check the first row location, 3rd enty
777 if (m_curIdxRidListHdr.firstIdxRidListEntry.type == (int)LIST_RID_TYPE)
778 {
779 ridArray[size] = (RID)m_curIdxRidListHdr.firstIdxRidListEntry.rid;
780 //cout<<" IndexList::getRIDArrayFromListHdr->header Lbid->" << m_hdrLbid <<" count->" << arrayCount <<endl;
781
782 size++;
783 //cout << "RID = " << (RID)m_curIdxRidListHdr.firstIdxRidListEntry.rid << endl;
784 };
785
786 //Check Header last entry's type
787 int type = m_curIdxRidListHdr.nextIdxRidListPtr.type;
788
789 switch (type)
790 {
791 case LIST_RID_TYPE:// There is a row id here, Check!
792 ridArray[size] = (RID)m_curIdxRidListHdr.nextIdxRidListPtr.llp;
793 //cout<<"arrayCount->" << arrayCount << "rid->" << ridArray[arrayCount]<<endl;
794 size++;
795 //cout << "RID = " << (RID)m_curIdxRidListHdr.nextIdxRidListPtr.llp << endl;
796 return NO_ERROR;
797
798 case LIST_SUBBLOCK_TYPE://Not found in header, so go to the sub-block
799 //get thelbid sbid and entry out from the header last entry
800
801 m_lbid = ((IdxEmptyListEntry*) & (m_curIdxRidListHdr.nextIdxRidListPtr))->fbo;
802 m_sbid = ((IdxEmptyListEntry*) & (m_curIdxRidListHdr.nextIdxRidListPtr))->sbid;
803 m_entry = ((IdxEmptyListEntry*) & (m_curIdxRidListHdr.nextIdxRidListPtr))->entry;
804 m_curType = type;
805 //Read the pointer entry at LIST_SUB_LLP_POS location
806
807 memset(rowIdArray, 0, BYTE_PER_BLOCK);
808
809 pos = LIST_SUB_LLP_POS;
810 totalbytes = SUBBLOCK_TOTAL_BYTES;
811
812 if (m_lbid != m_hdrLbid)
813 {
814 rc = readSubBlockEntry(cb, &m_curBlock, m_lbid,
815 m_sbid, 0, totalbytes,
816 rowIdArray);
817 m_curBlock.lbid = m_lbid;
818 m_curBlock.state = BLK_READ;
819 m_curBlock.dirty = true;
820 }
821 else
822 getSubBlockEntry(m_hdrBlock.data, m_sbid,
823 0, totalbytes,
824 rowIdArray );
825
826 lastIdxRidListPtr = (IdxRidListPtr*) &rowIdArray[pos];
827 type = lastIdxRidListPtr->type;
828 count = lastIdxRidListPtr->count;
829
830 //cout << "count->" << count << endl;
831 //type should be LIST_BLOCK_TYPE from now on
832 for (int i = 0; i < count; i++)
833 {
834 ridArray[size] = (RID)(rowIdArray[i].rid);
835 //cout << "RID =" << (RID)(rowIdArray[i].rid) << endl;
836 //cout<<"arrayCount->" << arrayCount << "rid->" << ridArray[arrayCount]<<endl;
837 size++;
838 }
839
840 //cout << " Lbid->" << m_lbid ;
841 //cout << " count->" << count << endl;
842 m_lbid = ((IdxEmptyListEntry*)lastIdxRidListPtr)->fbo;
843 m_curType = type;
844 }//end of switch
845 }//end if flag
846
847 if (m_curType == LIST_BLOCK_TYPE)
848 {
849 pos = LIST_BLOCK_LLP_POS;
850 totalbytes = BYTE_PER_BLOCK;
851 rc = readSubBlockEntry(cb, &m_curBlock, m_lbid, 0, 0,
852 totalbytes, rowIdArray);
853 m_curBlock.lbid = m_lbid;
854 m_curBlock.state = BLK_READ;
855 m_curBlock.dirty = true;
856
857 nextIdxListPtr = (IdxRidNextListPtr*)&rowIdArray[pos];
858 type = nextIdxListPtr->type;
859
860 count = nextIdxListPtr->count;
861
862 for (int i = 0; i < count; i++)
863 {
864 ridArray[size] = (RID)(rowIdArray[i].rid) ;
865 size++;
866 }
867
868 IdxRidListArrayPtr idxRidListArrayPtr;
869 int curLevel = 0, curCount = 0;
870
871 memset(&idxRidListArrayPtr, 0, sizeof(idxRidListArrayPtr));
872 getSubBlockEntry(m_curBlock.data, 0,
873 BEGIN_LIST_BLK_LLP_POS,
874 LIST_BLK_LLP_ENTRY_WIDTH,
875 &idxRidListArrayPtr);
876 curLevel = idxRidListArrayPtr.nextIdxListPtr.curLevel;
877 curCount = idxRidListArrayPtr.nextIdxListPtr.count;
878
879 for (int i = 0; i < TOTAL_NUM_ARRAY_PTR; i++)
880 {
881 m_lbid = idxRidListArrayPtr.childIdxRidListPtr[i].childLbid;
882 int type = idxRidListArrayPtr.childIdxRidListPtr[i].type;
883
884 if ((m_lbid != (uint64_t)INVALID_LBID) && (type == LIST_BLOCK_TYPE))
885 {
886 m_curType = LIST_BLOCK_TYPE;
887 getRIDArrayFromListHdrNarray(pFile, key, curIdxRidListHdrPtr,
888 ridArray, size, false);
889 }
890
891 }
892
893 }//end if block
894
895 return rc;
896 }//end getRIDArrayFromListHdrNarray
897
898
899 /*---------------------------------------------------------------------
900 * Description: Output the info of this company to an abstract stream
901 *
902 * Input: None
903 *
904 * Output: None
905 *
906 * Comments: None
907 *
908 * Return Code: the abstract output stream
909 *------------------------------------------------------------------*/
operator <<(ostream & os,IndexList & rhs)910 ostream& operator<<(ostream& os, IndexList& rhs)
911 {
912 os << rhs.m_curIdxRidListHdr.idxRidListSize.size << "\t"
913 << rhs.m_curIdxRidListHdr.key << "\t"
914 << rhs.m_curIdxRidListHdr.firstIdxRidListEntry.type << "\t"
915 << rhs.m_curIdxRidListHdr.firstIdxRidListEntry.rid << "\t"
916 << rhs.m_curIdxRidListHdr.nextIdxRidListPtr.type << "\t"
917 << rhs.m_curIdxRidListHdr.nextIdxRidListPtr.llp << "\t"
918 << endl;
919 return os;
920 }
921 /************************************************
922 * Description:
923 * Find a entry for the given rowId and Key
924 * Converted
925 * input
926 * pFile -- File Handler
927 * rowId -- row id
928 * key -- value
929 * curIdxRidListHdrPtr - point to the header
930 * output
931 * lbid -- File block id
932 * sbid -- Sub Block id
933 * entry -- Entry id
934 *
935 *
936 * return value
937 * true --found
938 * false--not found
939 ************************************************/
findRowId(FILE * pFile,const RID & rowId,const uint64_t & key,IdxEmptyListEntry * curIdxRidListHdrPtr,uint64_t & lbid,int & sbid,int & entry)940 bool IndexList::findRowId(FILE* pFile, const RID& rowId, const uint64_t& key,
941 IdxEmptyListEntry* curIdxRidListHdrPtr,
942 uint64_t& lbid, int& sbid, int& entry)
943 {
944 bool found = false;
945 int rc;
946
947 m_pFile = pFile;
948 rc = getHdrInfo(curIdxRidListHdrPtr);
949
950 if (key != m_curIdxRidListHdr.key)
951 {
952 return false;
953 }
954
955 found = findRowId(rowId, key, lbid, sbid, entry);
956 return found;
957 }
958
959 /************************************************
960 * Description:
961 * Find a entry for the given rowId and Key
962 * Converted
963 * input
964 * pFile -- File Handler
965 * rowId -- row id
966 * key -- value
967 * curIdxRidListHdrPtr - point to the header
968 * output --
969 * lbid -- File block id
970 * sbid -- Sub Block id
971 * entry -- Entry id
972 *
973 * return value
974 * true --found
975 * false--not found
976 ************************************************/
findRowId(const RID & rowId,const int64_t & key,int64_t & lbid,int & sbid,int & entry)977 bool IndexList::findRowId(const RID& rowId, const int64_t& key,
978 int64_t& lbid, int& sbid, int& entry)
979 {
980 bool found = false;
981 int rc;
982 RID savedRid;
983 CommBlock cb;
984 int count;
985 uint64_t prevLbid;
986 int prevType;
987
988 cb.file.oid = m_oid;
989 cb.file.pFile = m_pFile;
990 //Check the first row location, 3rd enty--0,1,2
991
992 if (m_curIdxRidListHdr.firstIdxRidListEntry.type == (int)LIST_RID_TYPE)
993 {
994 if (m_curIdxRidListHdr.firstIdxRidListEntry.rid == rowId)
995 {
996 lbid = m_hdrLbid;
997 sbid = m_hdrSbid;
998 entry = m_hdrEntry + 2;
999 found = true;
1000 return found;
1001 }
1002 }; //endif type=LIST_RID_TYPE
1003
1004 //Check Header last entry's type
1005 int type = m_curIdxRidListHdr.nextIdxRidListPtr.type;
1006
1007 int pos = 0, totalbytes = 0;
1008
1009 switch (type)
1010 {
1011 case LIST_NOT_USED_TYPE://Header is not full, no sub-block linked
1012 //No RowId here then on
1013 lbid = -1LL;
1014 sbid = -1;
1015 entry = -1;
1016 found = false;
1017 return found; //not found
1018
1019 case LIST_RID_TYPE:// There is a row id here, Check!
1020
1021 savedRid = (RID)m_curIdxRidListHdr.nextIdxRidListPtr.llp;
1022
1023 if (savedRid == rowId)
1024 {
1025 lbid = m_hdrLbid;
1026 sbid = m_hdrSbid;
1027 entry = m_hdrEntry + 3;
1028 found = true;
1029 return found;
1030 }
1031 else
1032 {
1033 lbid = -1LL;
1034 sbid = -1;
1035 entry = -1;
1036 found = false;
1037 return found;
1038 }
1039
1040 case LIST_SUBBLOCK_TYPE://Not found in header
1041 //get the lbid sbid and entry out from the header last entry
1042
1043 m_lbid = ((IdxEmptyListEntry*)
1044 & (m_curIdxRidListHdr.nextIdxRidListPtr))->fbo;
1045 m_sbid = ((IdxEmptyListEntry*)
1046 & (m_curIdxRidListHdr.nextIdxRidListPtr))->sbid;
1047 m_entry = ((IdxEmptyListEntry*)
1048 & (m_curIdxRidListHdr.nextIdxRidListPtr))->entry;
1049
1050 //Read the pointer entry at LIST_SUB_LLP_POS
1051 //reserve enough space for rowIdArray
1052 IdxRidListPtr* lastIdxRidListPtr;
1053 IdxRidListEntry rowIdArray[MAX_BLOCK_ENTRY];
1054 memset(rowIdArray, 0, BYTE_PER_BLOCK);
1055 //first link
1056 pos = LIST_SUB_LLP_POS;
1057 totalbytes = SUBBLOCK_TOTAL_BYTES;
1058
1059 //check if the sub block is on the header block
1060 if (m_lbid != m_hdrLbid)
1061 {
1062 rc = readSubBlockEntry( cb, &m_curBlock, m_lbid, m_sbid, 0,
1063 totalbytes, rowIdArray);
1064 m_curBlock.dirty = true;
1065 m_curBlock.state = BLK_READ;
1066 }
1067 else
1068 {
1069 getSubBlockEntry(m_hdrBlock.data, m_sbid,
1070 0, totalbytes, rowIdArray );
1071
1072 }
1073
1074 lastIdxRidListPtr = (IdxRidListPtr*) &rowIdArray[pos];
1075
1076 prevLbid = m_lbid; //sub block
1077 prevType = type; //sub block
1078 count = lastIdxRidListPtr->count; //current count
1079 type = lastIdxRidListPtr->type; //block
1080 found = false;
1081
1082 //look inside the first sub block
1083 for (int i = 0; i < count; i++)
1084 {
1085 if (rowIdArray[i].rid == rowId)
1086 {
1087 found = true;
1088 lbid = m_lbid;
1089 sbid = m_sbid;
1090 entry = i;
1091 return found;
1092 }
1093 }
1094
1095 while ((!found) && (type == LIST_BLOCK_TYPE))
1096 {
1097 //There are more to check on the next link
1098 m_lbid = ((IdxEmptyListEntry*)lastIdxRidListPtr)->fbo;
1099 m_sbid = 0;
1100 m_entry = 0;
1101
1102 pos = LIST_BLOCK_LLP_POS;
1103 totalbytes = BYTE_PER_BLOCK;
1104
1105 if ((m_lbid != m_hdrLbid) && (m_lbid != prevLbid))
1106 {
1107 // the only case for block
1108 rc = readSubBlockEntry( cb, &m_curBlock, m_lbid,
1109 m_sbid, 0, totalbytes,
1110 rowIdArray);
1111 m_curBlock.dirty = true;
1112 }
1113 else
1114 {
1115 printf("error in findRowID\n");
1116 return false;
1117 }
1118
1119 prevType = type;
1120 lastIdxRidListPtr = (IdxRidListPtr*) &rowIdArray[pos];
1121 type = lastIdxRidListPtr->type;
1122 count = lastIdxRidListPtr->count;
1123 found = false;
1124
1125 for (int i = 0; i < count; i++)
1126 {
1127 if (rowIdArray[i].rid == rowId)
1128 {
1129 found = true;
1130 lbid = m_lbid;
1131 sbid = m_sbid;
1132 entry = i;
1133 return found;
1134 }
1135 }//end for i
1136
1137 prevLbid = m_lbid;
1138 } //end while
1139
1140 break;
1141
1142 default:
1143 printf ("FIND ROWID got no where, error out !! \n");
1144 break;
1145 }; //end switch
1146
1147 lbid = INVALID_LBID;
1148
1149 sbid = INVALID_NUM;
1150
1151 entry = INVALID_NUM;
1152
1153 found = false;
1154
1155 return found;
1156 } //end function
1157
1158 } //end of namespace
1159
1160
1161