Issues with BlockAccess::ba_linearSearch()
Closed this issue · 7 comments
There are a few modifications to be made to the algorithm
- slot = previous record id's slot + 1
- Add the while loop around the part that loops
- Make use of return values E_OUTOFBOUND and E_FREESLOT of getRecord() to get the next slot and block. Change to next block on getting E_OUTOFBOUND and break the loop on getting E_FREESLOT
- Mention how to get attribute offset from attribute name
- Replace
OpenRelTable::setPrevRecId()withRelCacheTable::setSearchIndex()
Linear search function was mistakenly not synced from the implementation repo to documentation.
The updated algorithm for ba_linearSearch has now been pushed to doc website. Please check it out @SaintNerevar.
slot = previous record id's slot + 1 -> DONE
Add the while loop around the part that loops -> DONE
Make use of return values E_OUTOFBOUND and E_FREESLOT of getRecord() to get the next slot and block. Change to next block on getting E_OUTOFBOUND and break the loop on getting E_FREESLOT
--- The same functionality is explicitly done using slot map and right block field of header.
E_OUTOFBOUND can be used but it is returned in 2 cases from the getRecord function
- when block number is invalid
- when slot number is invalid
This might make it hard to understand if the current slot is the last slot + 1 or if the block is invalid(right block of the last linked list element)
Mention how to get attribute offset from attribute name -> DONE
Replace OpenRelTable::setPrevRecId() with RelCacheTable::setSearchIndex() -> DONE
This might make it hard to understand if the current slot is the last slot + 1 or if the block is invalid(right block of the last linked list element)
This actually isn't a problem if the loop checks for block number != -1. Then inside the loop, the only other possibility is slot number being last slot + 1. I think it makes the algorithm simpler. As for breaking the loop on getting E_FREESLOT, I realized it's wrong because the Catalogs can have gaps in between the records. So we just increase the slot number and continue. I have attached my implementation for clarity. Check it out and tell me if it's more understandable
// Get the current search index
RecId currSearchIndex;
RelCacheTable::getSearchIndex(relId, &currSearchIndex);
// Set the block, slot based on whether current search index exists
int block, slot;
if (currSearchIndex.block == -1 && currSearchIndex.slot == -1) {
RelCatEntry relCatEntry;
RelCacheTable::getRelCatEntry(relId, &relCatEntry);
block = relCatEntry.firstBlk;
slot = 0;
} else {
block = currSearchIndex.block;
slot = currSearchIndex.slot + 1;
}
// Loop to find the next hit based on attrval.
while (block != -1) { // This works even when there are no records in the relation
RecBuffer recBuffer{block};
Attribute record[6];
int retval;
retval = recBuffer.getRecord(record, slot);
if (retval == E_FREESLOT) {
slot++;
continue;
}
if (retval == E_OUTOFBOUND) {
HeadInfo header;
recBuffer.getHeader(&header);
block = header.rblock;
slot = 0;
continue;
}
int cond = 0;
AttrCatEntry attrCatEntry;
AttrCacheTable::getAttrCatEntry(relId, attrName, &attrCatEntry);
int offset = attrCatEntry.offset;
int attrType = attrCatEntry.attrType;
int flag = compare(attrval, record[offset], attrType);
switch (op) {
case NE:
if (flag != 0) cond = 1;
break;
case LT:
if (flag < 0) cond = 1;
break;
case LE:
if (flag <= 0) cond = 1;
break;
case GT:
if (flag > 0) cond = 1;
break;
case GE:
if (flag >= 0) cond = 1;
break;
case EQ:
if (flag == 0) cond = 1;
break;
}
if (cond == 1) {
RecId recId{block, slot};
RelCacheTable::setSearchIndex(relId, &recId);
return recId;
}
slot++;
}
// No hits
return RecId{-1, -1};
This seems more clear. Will update the algorithm this way.
I just realised that there is an error in my impementation in #42 (comment).
Attribute record[6] is wrong. It should be Attribute record[#Attributes]. This should also be noted in the algorithm. We need to get the #Attributes from RelCacheTable beforehand.
Also, RST and PRJCT operators are not mentioned in the algorithm. These are referenced in the Arguments section and in ba_search()
Updated Algorithm for linearSearch:
Please check it out @SaintNerevar
RecId BlockAccess::linearSearch(int relId, char attrName[ATTR_SIZE], union Attribute attrVal, int op) {
// get the previous search index of the relation relId from the relation cache
// (use RelCacheTable::getSearchIndex() function)
// let block and slot denote the record id of the record being currently checked
// if the current search index record is invalid(i.e. both block and slot = -1)
if (prevRecId.block == -1 && prevRecId.slot == -1)
{
// (no hits from previous search; search should start from the first record itself)
// get the first record block of the relation from the relation cache
// (use RelCacheTable::getRelCatEntry() function of Cache Layer)
// block = first record block of the relation
// slot = 0
}
else
{
// (there is a hit from previous search; search should start from the record next to the search index record)
// block = search index's block
// slot = search index's slot + 1
}
// The following code searches for the next record in the relation that satisfies the given condition
// Start from the record id (block, slot) and iterate over the remaining records of the relation
while (block != -1)
{
// create a RecBuffer object for block (use RecBuffer Constructor for existing block)
// get the record with id (block, slot) using RecBuffer::getRecord() function
// get header of the block using RecBuffer::getHeader() function
// get slot map of the block using RecBuffer::getSlotMap() function
// If slot >= the number of slots per block(i.e. no more slots in this block)
{
// update block = right block of block
// update slot = 0
}
// if slot is free skip the loop
// (i.e. check if slot'th entry in slot map of block contains SLOT_UNOCCUPIED)
{
// and continue to the next record slot
// (i.e. increment slot and continue)
}
// let cond be a variable of int type
if ( op != PRJCT )
{
// compare record's attribute value to the the given attrVal as below:
/*
firstly get the attribute offset for the attrName attribute
from the attribute cache entry of the relation using AttrCacheTable::getAttrCatEntry
*/
// use the attribute offset to get the value of the attribute from current record
// perform comparison using compare function and store the outcome of comparison in the variable flag
// initialize cond = UNSET
// Next task is to check whether this record satisfies the given condition.
// It is determined based on the output of previous comparison and the op value received.
// The following code sets the cond variable if the condition is satisfied.
switch (op) {
case NE:
// if op is "not equal to"
// if the record's attribute value is not equal to the given attrVal
if (flag != 0) {
// SET the cond variable (i.e. cond = SET)
}
break;
case LT:
// if op is "less than"
// if the record's attribute value is less than the given attrVal
if (flag < 0) {
// SET the cond variable (i.e. cond = SET)
}
break;
case LE:
// if op is "less than or equal to"
// if the record's attribute value is less than or equal to the given attrVal
if (flag <= 0) {
// SET the cond variable (i.e. cond = SET)
}
break;
case EQ:
// op is "equal to"
// if the record's attribute value is equal to the given attrVal
if (flag == 0) {
// SET the cond variable (i.e. cond = SET)
}
break;
case GT:
// if op is "greater than"
// if the record's attribute value is greater than the given attrVal
if (flag > 0) {
// SET the cond variable (i.e. cond = SET)
}
break;
case GE:
// if op is "greater than or equal to"
// if the record's attribute value is greater than or equal to the given attrVal
if (flag >= 0) {
// SET the cond variable (i.e. cond = SET)
}
break;
}
}
if (cond == SET || op == PRJCT) {
/*
set the search index in the relation cache as
the record id of the record that satisfies the given condition
(use RelCacheTable::setSearchIndex function)
*/
return RecId{block, slot};
}
}
// no record in the relation with Id relid satisfies the given condition
return {-1, -1};
}// If slot >= the number of slots per block(i.e. no more slots in this block)
{
// update block = right block of block
// update slot = 0
}
@jessiyajoy Just add a continue inside this and remove RST from op description in Arguments section