Engineering Computer Science EBK DATA STRUCTURES AND ALGORITHMS IN C

Program Plan: 1.The below mentioned variables are used: A variable totSum to store the int type of value. A variable kyLen of in ttype thst stores the length of the key. 2. The below mentioned functions are used in the program that are declared within the class. locateHash()function to find the hash value of the key. MakeAddress() function to find the address of the key. Initfile() function for initialization of the buffer. ClearField() function to clear all the fields. Various virtual functions and constructors are also declared a sper the need of the class. Program description: To write a program that inserts records into a file and retrieves and deletes them using extendible hashing or linear hashing techniques. Program: #include <iostream> #include <fstream> #include <cstring> #include <cctype> #include <iomanip> using namespace std; /*Function to find the Hash value for the given key*/ int locateHash(char* ky) { //Declare variables. int totSum = 0; //Find the length of the string and store it. int kyLen = strlen(ky); //Make the length to even if the length is odd. if (kyLen % 2 == 1) kyLen++; //Use loop to find the hash value of the given key. for (int aa = 0; aa < kyLen; aa += 2) totSum = (totSum + 100 * ky[aa] + ky[aa + 1]) % 19937; //Return the hash value. return totSum; } //Function to find the address of the key. int MakeAddress(char * ky, int locDepth) { //Declare variables. int retvall = 0; int maskk = 1; int hashVall = locateHash(ky); //Use loop to find the location to insert the key. for (int aa = 0; aa < locDepth; aa++) { retvall = retvall << 1; /*Find the lower address bit */ int lowerAddrBit = hashVall & maskk; retvall = retvall | lowerAddrBit; hashVall = hashVall >> 1; } /* Return the address*/ return retvall; } /*Abstract class that serves as a base class for all buffer files. */ class BaseBuffer { //Access Specifier. public: //Constructor. BaseBuffer(int capBytes = 1000); //Copy the given BaseBuffer into current BaseBuffer. BaseBuffer & operator = (const BaseBuffer &); //Remove the fields from the file buffer virtual void ClearField(); //Fix the next field value for the buffer. virtual int SetNextField(const void * fld, int size = -1) = 0; //Get the next field value of the file buffer. virtual int ExtractNextField(void * fld, int maxbytes = -1) = 0; //Display Buffer file. virtual void DisplayBuffInfo(ostream &) const; //Initialize the buffer files variables. int InitFile(int capBytes); //Sequential Read operations. virtual int SequentialRead(istream &) = 0; //Sequential Write operations. virtual int SequentialWrite(ostream &) const = 0; // Performing direct read operations. virtual int DirectReadOP(istream &, int recref); //Performing direct write operations. virtual int DirectWriteOP(ostream &, int recref) const; // Read a header from the stream. virtual int ReadStreamHeader(istream &) = 0; //write a header to the stream virtual int WriteStreamHeader(ostream &) const; //Access Specifier protected: //It is said to TRUE if buffer is assigned with value. int bufferSet; //Array to hold the field values. char * baseAry; //Overall size of the packed fields. int SizeOfBuffer; //Buffer limit. int AllowedBytes; // Index of next byte to be set/extract. int subsequentByte; //TRUE if buffer is in the packing fileOpenMode. int BufferMode; }; //Constructor that initializes the BaseBuffer to said sizes BaseBuffer::BaseBuffer(int capBytes) { //Call method to initialize the variables. InitFile(capBytes); } /*Overloaded assignment operator that copies one BaseBuffer into another. */ BaseBuffer & BaseBuffer :: operator = (const BaseBuffer & bufT) { /*Check for buffer size. If buffer size is not matching then return. */ if (AllowedBytes < bufT.SizeOfBuffer) return *this; //Otherwise copy the bufT into current buffer. //copy the bufferSet bufferSet = bufT.bufferSet; //Copy the buffer size. SizeOfBuffer = bufT.SizeOfBuffer; //Copy the field value. memcpy(baseAry, bufT.baseAry, bufT.SizeOfBuffer); //Set the next byte to process. subsequentByte = bufT.subsequentByte; //Set the packing or unpacking mode. BufferMode = BufferMode; //Return the BaseBuffer return *this; } //Function to clear the fields void BaseBuffer::ClearField() { //Clear the next byte to process subsequentByte = 0; //Set the packing mode. BufferMode = 1; } //Function to print the info of the buffer size. void BaseBuffer::DisplayBuffInfo(ostream & stream) const { /*Print the maximum allowed bytes and current size of the buffer. */ stream << "Bytes Limited " << AllowedBytes << " Present Size " << SizeOfBuffer; } //Function initializes the BaseBuffer variables. int BaseBuffer::InitFile(int capBytes) { //Set the BaseBuffer to unpack mode. bufferSet = 0; /*Check the capBytes. If capBytes is less than zero, then assign capBytes to 0.*/ if (capBytes < 0) capBytes = 0; //Set the maximum limited bytes. AllowedBytes = capBytes; //Create the allowed bytes of buffer array baseAry. baseAry = new char[AllowedBytes]; //Initialize the buffer size to 0. SizeOfBuffer = 0; //Clear BufferMode and subsequentByte to default //value. ClearField(); return 1; } /*For the given record reference, the fiunction accesses the record directly. */ int BaseBuffer::DirectReadOP(istream & inpStream, int recordReff) { //In the file move to the given position. inpStream.seekg(recordReff, ios::beg); /*Check if current position is equal to the record position. if not, then return -1. */ if (inpStream.tellg() != static_cast(recordReff)) return -1; //Otherwise, perform the sequential read operation. return SequentialRead(inpStream); } //Function that writes the record into the file directly. int BaseBuffer::DirectWriteOP(ostream & outpStream, int recordReff) const { //Get the position in the file. outpStream.seekp(recordReff, ios::beg); /*If file position and record position are same then perform write directly. */ if (outpStream.tellp() != static_cast(recordReff)) //If not, return -1 on unsuccessful write. return -1; //Otherwise, Perform the sequential write. return SequentialWrite(outpStream); } /*Declare the header */ static const char * hdrStrr = "BaseBuffer"; /*Declare Header size*/ static const int hdrSize = strlen(hdrStrr); /*Function to read the stream header*/ int BaseBuffer::ReadStreamHeader(istream & inpStream) { char strr[12]; //Move to the given position. inpStream.seekg(0, ios::beg); //Read the header field in the file. inpStream.read(strr, hdrSize); //Check inpStream is good. If not return -1. if (!inpStream.good()) return -1; /*Compare the headers. If headers are matching and identical then return the header size. */ if (strncmp(strr, hdrStrr, hdrSize) == 0) return hdrSize; //Otherwise, return -1 on failure. else return -1; } /*Function to Write the stream header*/ int BaseBuffer::WriteStreamHeader(ostream & outpStream) const { //Goto the position in the output file. outpStream.seekp(0, ios::beg); //Write the record. outpStream.write(hdrStrr, hdrSize); // Check outpStream is good. If not then return -1. if (!outpStream.good()) return -1; //Otherwise return the header size. return hdrSize; } /*Class that serves as a base class for variable length records. */ class ModifiableBuff : public BaseBuffer { //Access Specifier public: //Argumented Constructor. ModifiableBuff(int AllowedBytes = 1000); //Copy cinstructor. ModifiableBuff(const ModifiableBuff & buffer) : BaseBuffer(buffer){} //Clear the fields. void ClearField(); //Function to perform the sequential Read operations. int SequentialRead(istream &); //Function to perform the sequential Write operations. int SequentialWrite(ostream &) const; //Function to read the stream header int ReadStreamHeader(istream &); //Function to write the stream header. int WriteStreamHeader(ostream &) const; //Print the cariable length buffer. void DisplayBuffInfo(ostream &) const; //Return the buffer size. int getBufferSize() const; //Function to initialize the variables. int InitFile(); }; /* Constructor that initializes the Buffer to limited sites. */ ModifiableBuff::ModifiableBuff(int capBytes) : BaseBuffer(capBytes) { /*Call the function InitFile() to initialize the fields.*/ InitFile(); } //Function to clear the fields. void ModifiableBuff::ClearField() { //Call Base class method to clear the fields. BaseBuffer::ClearField(); } //Read the number of bytes from the input stream and write it into the buffer field. int ModifiableBuff::SequentialRead(istream & inpStream) { //Check end of file is reached. if so return -1 on //failure. if (inpStream.eof()) return -1; //Store the address. int recordAddress = inpStream.tellg(); //Clear all the fields. ClearField(); unsigned short filebuffSize; //Read the buffer length. inpStream.read((char *)&filebuffSize, sizeof(filebuffSize)); /*Check for the good condition.If file is not in the good condition then return -1 on failure.*/ if (!inpStream.good()) { //Clear the input stream. inpStream.clear(); return -1; } //Assign the buffer length. SizeOfBuffer = filebuffSize; /*Check for overflow. If SizeOfBuffer is exceeding the AllowedBytes, then it indicates the overflow.*/ if (SizeOfBuffer > AllowedBytes) return -1; //Get the buffer. inpStream.read(baseAry, SizeOfBuffer); /* Check for the good condition.If file is not in the good condition then return -1 on failure. */ if (!inpStream.good()) { //Clear the input stream. inpStream.clear(); return -1; } //Return the record address. return recordAddress; } /*Function to write the buffer length and buffer into the output stream*/ int ModifiableBuff::SequentialWrite(ostream & outpStream) const { //Get the record address. int recordAddress = outpStream.tellp(); unsigned short filebuffSize; //Store the buffer size. filebuffSize = SizeOfBuffer; //Write the buffer size to the output file. outpStream.write((char *)&filebuffSize, sizeof(filebuffSize)); //Check for error. if error occurred then return. if (!outpStream) return -1; //Otherwise write the buffer. outpStream.write(baseAry, SizeOfBuffer); //Check for suucess. if not then return -1. if (!outpStream.good()) return -1; //Otherwise return the record address. return recordAddress; } /*Declare the header and header size for the variable length files*/ const char * variableHeader = "MODIFIABLE"; const int variableHeaderSize = strlen(variableHeader); //Read the header from the input file. int ModifiableBuff::ReadStreamHeader(istream & inpStream) { //Declare the variables. char strr[12]; int reslt; // Read the BaseBuffer header reslt = BaseBuffer::ReadStreamHeader(inpStream); //Check for the consistency. if (!reslt) return 0; // read the variable length field header inpStream.read(strr, variableHeaderSize); //Check for consistency. if (!inpStream.good()) return 0; /*Compare the headers. If they are not matching then return false. */ if (strncmp(strr, variableHeader, variableHeaderSize) != 0) return 0; // Read the buffer array. return inpStream.tellg(); } /*Function to write the buffer header, variable length header, header length to the output stream. */ int ModifiableBuff::WriteStreamHeader(ostream & outpStream) const { int reslt; // write the BaseBuffer header. reslt = BaseBuffer::WriteStreamHeader(outpStream); //Check for consistency. if (!reslt) return 0; // Write the header. outpStream.write(variableHeader, variableHeaderSize); //Check for consistency. if (!outpStream.good()) return 0; // Returnt the record description. return outpStream.tellp(); } /*Function to display the variable length Allowed buffer size and current buffer size.*/ void ModifiableBuff::DisplayBuffInfo(ostream & stream) const { //Use the base class function to print the info. BaseBuffer::DisplayBuffInfo(stream); } //Function to initialize the variable length buffer. int ModifiableBuff::InitFile() { //Clear the fields. ClearField(); //Return 1 on success. return 1; } //Class creates the variable length buffer with length. class LenFldBuff : public ModifiableBuff { //Access Specifier. public: //Constructor LenFldBuff(int capBytes = 1000); // Copy constructor. LenFldBuff(const LenFldBuff & buffer) : ModifiableBuff(buffer) {} //Clear the buffer fields. void ClearField(); //Set the next field. int SetNextField(const void * fld, int size = -1); //Get the next field value. int ExtractNextField(void *fld, int capBytes = -1); //Print the length field buffer info. void DisplayBuffInfo(ostream &) const; //Initialize the length field buffer variables. int InitFile(); }; //Constructor to initialize the variables. LenFldBuff::LenFldBuff(int capBytes) : ModifiableBuff(capBytes) { //Call InitFile() to initialize the variables. InitFile(); } //Function to clear the buffer fields. void LenFldBuff::ClearField() { //Call the base class method to clear the fields. ModifiableBuff::ClearField(); } /*Function that set the next field value.*/ int LenFldBuff::SetNextField(const void* bufField, int FldSize) { //Declare variables. short strrLen; /*Check for size greater than 0. if so then assign the size to strrLen */ if (FldSize >= 0) strrLen = FldSize; //Otherwise assignt the bufField length to strrLen. else strrLen = strlen((char *)bufField); //Get the first character to pack. int start = subsequentByte; //Get the next byte. subsequentByte += (strrLen + sizeof(strrLen)); //Check for overflow. if (subsequentByte > AllowedBytes) return -1; //Pack the bytes. memcpy(&baseAry[start], &strrLen, sizeof(strrLen)); memcpy(&baseAry[start + sizeof(strrLen)], bufField, strrLen); //Assign the buffer size. SizeOfBuffer = subsequentByte; //Return the total bytes packed. return strrLen; } /* Function to extract the subsequent bytes and return the total extracted bytes*/ int LenFldBuff::ExtractNextField(void* bufField, int capBytes) { //Declare variable. short strrLen; //Check for no fields. if (subsequentByte >= SizeOfBuffer) return -1; //Get the first byte to be extracted. int start = subsequentByte; //Read the pack memcpy(&strrLen, &baseAry[start], sizeof(strrLen)); //Check field is too long. if (capBytes != -1 && strrLen > capBytes) return -1; //Set the next byte. subsequentByte += strrLen + sizeof(strrLen); //Check for no fields. if (subsequentByte > SizeOfBuffer) return -1; //Read the buffer. memcpy(bufField, &baseAry[start + sizeof(strrLen)], strrLen); //Terminate the buffer string. if (capBytes > strrLen || capBytes == -1) ((char *)bufField)[strrLen] = 0; //return the total bytes extracted. return strrLen; } /*Function that print the length field buffer info*/ void LenFldBuff::DisplayBuffInfo(ostream & outpstream) const { outpstream << "Maximum Allowed Bytes: " << AllowedBytes << " and Current size: " << SizeOfBuffer << endl; } /*Function that initialiazes the buffer field*/ int LenFldBuff::InitFile() { //Set the buffer to packing mode. bufferSet = 1; //Clear the fields. ClearField(); return 1; } //Class buffer that holds the fixed length records. class StandardLenBuff : public BaseBuffer { //Access Specifier. public: //Constructor StandardLenBuff(int rcdSize = 1000); //Copy Constructor. StandardLenBuff(const StandardLenBuff & buffer); //Function to clear the fields. void ClearField(); //Function for sequential Read int SequentialRead(istream &); //Function for sequential write. int SequentialWrite(ostream &) const; //Function to read the header. int ReadStreamHeader(istream &); //Function to write the header. int WriteStreamHeader(ostream &) const; //Function to display the buffer info. void DisplayBuffInfo(ostream &) const; //Get the size of the buffer. int getBufferSize() const; //Access Specifier. protected: //Function to initialize the file. int InitFile(int rcdSize); //Function to modify the record size. int modifyRcdSze(int rcdSize); }; //Constructor that initializes the buffer. inline StandardLenBuff::StandardLenBuff(const StandardLenBuff & buf1) : BaseBuffer(buf1) { /*Call the function InitFile() to initialize the buffer file. */ InitFile(buf1.SizeOfBuffer); } //Constructor to Initialize the file to given record size. StandardLenBuff::StandardLenBuff(int rcdSize) : BaseBuffer(rcdSize) { //Initialize the buffer to the given record size. InitFile(rcdSize); } //Clear the fields. void StandardLenBuff::ClearField() { //Clear all the fields.. BaseBuffer::ClearField(); baseAry[0] = 0; //Set the buffer to packing mode. BufferMode = 1; } //Function to read the input stream. int StandardLenBuff::SequentialRead(istream & inpStream) { //Get the record address. int recordAddress = inpStream.tellg(); //Clear the input stream. inpStream.clear(); //Clear the field. ClearField(); //Set the buffer to unpacking mode. BufferMode = 0; //Read the string from the input stream. inpStream.read(baseAry, SizeOfBuffer); /*Check for consistency. if the file is not consistent then clear the input stream and return record address.*/ if (!inpStream.good()) { //Clear the input stream. inpStream.clear(); //return the record address. return recordAddress; } //Otherwise return the record address. return recordAddress; } /*Function to read the number of bytes from the output stream and return the record location.*/ int StandardLenBuff::SequentialWrite(ostream & outpStream) const { //Get the record address. int recordAddress = outpStream.tellp(); //Read the buffer. outpStream.write(baseAry, SizeOfBuffer); /*Check for consistency. If the output stream is not good, then return -1. */ if (!outpStream.good()) return -1; //Otherwise, return the record address. return recordAddress; } /* Declare the header and header size for the fixed length buffer*/ static const char * StdHeader = "STANDARD"; static const int StdHeaderSize = strlen(StdHeader); //Function to read header from stream. int StandardLenBuff::ReadStreamHeader(istream & inpStream) { //Declare the variables. char strr[10]; int rcdSize; int reslt; // Read the base class BaseBuffer Buffer. reslt = BaseBuffer::ReadStreamHeader(inpStream); //Check for success. If not, then return -1. if (reslt < 0) return -1; // Read the string "STANDARD" inpStream.read(strr, StdHeaderSize); /*Check for consistency. If not then return -1 on failure.*/ if (!inpStream.good()) return -1; /*Compare the headers for identical. If not, then return -1. */ if (strncmp(strr, StdHeader, StdHeaderSize) != 0) return -1; //Read the record size. inpStream.read((char*)&rcdSize, sizeof(rcdSize)); //Check the header for consistency. if (bufferSet) { /*Check the buffer length and recordsize. If buffer length */ if (rcdSize != SizeOfBuffer) return -1; } // Otherwise, use the header to initialize the buffer. modifyRcdSze(rcdSize); //Return the return inpStream.tellg(); } /*Function to write the buffer header, standard length header, header length to the output stream. */ int StandardLenBuff::WriteStreamHeader(ostream & outpStream) const { int reslt; /*Check buffer for packing mode. If buffer is not set for packing mode then return -1. */ if (!bufferSet) return -1; // Write the header of the BaseBuffer. reslt = BaseBuffer::WriteStreamHeader(outpStream); //Check for consistency. If not then return -1. if (!reslt) return -1; // Write the header of the standard length buffer. outpStream.write(StdHeader, StdHeaderSize); //Check for consistency. If not then return -1. if (!outpStream.good()) return -1; // Write the buffer length. outpStream.write((char *)&SizeOfBuffer, sizeof(SizeOfBuffer)); //Check for the consistency. If not then return -1. if (!outpStream.good()) return -1; //Return the output stream position. return outpStream.tellp(); } //Function to write the standard length buffer info to the output stream. void StandardLenBuff::DisplayBuffInfo(ostream & outpStream) const { BaseBuffer::DisplayBuffInfo(outpStream); outpStream << "STANDARD "; } //Constructor to initialize the buffer to the given rcdSize int StandardLenBuff::InitFile(int rcdSize) { //Clear the fields. ClearField(); //Assign the rcdSize to SizeOfBuffer. SizeOfBuffer = rcdSize; return 1; } //Function to modify the buffer size. int StandardLenBuff::modifyRcdSze(int rcdSize) { //Change the SizeOfBuffer to rcdSize. SizeOfBuffer = rcdSize; return 1; } /* class StandardFldBuff*/ class StandardFldBuff : public StandardLenBuff { //Access Specifier. public: /*Constructors*/ StandardFldBuff(int allowedFlds, int RcdSize = 1000); StandardFldBuff(int allowedFlds, int * FldSize); StandardFldBuff(const StandardFldBuff &); /* Overloaded assignment operator*/ StandardFldBuff & operator = (const StandardFldBuff &); /*Clear all fields*/ void ClearField(); /*Describe the next Field*/ int addNxtFld(int FldSize); /* read header*/ int ReadStreamHeader(istream &); /*write header*/ int WriteStreamHeader(ostream &) const; /*set next field*/ int SetNextField(const void * fld, int size = -1); /* get next field*/ int ExtractNextField(void * fld, int capBytes = -1); /* Display Buffer info*/ void DisplayBuffInfo(ostream &) const; /* return the total defined fields*/ int NumberOfFields() const; /*function to initialize the files*/ int InitFile(int allowedFlds); int InitFile(int totFlds, int * FldSize); //Access Specifier. protected: /*Declare the variables*/ int * FldSizeAry; int AllowedFlds; int fldCnt; int subField; }; //Constructor to initialize the buffer. inline StandardFldBuff::StandardFldBuff(const StandardFldBuff & buf1) : StandardLenBuff(buf1) { //Call function to initialize the buffer. InitFile(buf1.fldCnt, buf1.FldSizeAry); } //Constructor that initializes the buffer with maximum allowed sizes. StandardFldBuff::StandardFldBuff(int allowedFlds, int capBytes) : StandardLenBuff(capBytes) { //Call function to initialize the buffer. InitFile(allowedFlds); } // Function to find the record size from field size. static int SumFieldSizes(int totFlds, int * FldSize) { int recSum = 0; //Use loop to find the record sum. for (int aa = 0; aa< totFlds; aa++) //Add the field size to the sum. recSum += FldSize[aa]; //Return the sum. return recSum; } /*Overloaded assignment operator to copy the buffer*/ StandardFldBuff & StandardFldBuff :: operator = (const StandardFldBuff & buff) { /* Check for field identity. If not matching then return. */ if (fldCnt != buff.fldCnt) //Return on failure. return *this; //Loop to check the field sizes are matching. for (int aa = 0; aa < fldCnt; aa++) /*Check each field size of buff1 and current buffer. If not, then return.*/ if (FldSizeAry[aa] != buff.FldSizeAry[aa]) //Return on failure. return *this; //Assign the subsequent field. subField = buff.subField; //call the super class function. StandardLenBuff :: operator = (buff); //Return statement. return *this; } //Constuctor to create the fields with particular size. StandardFldBuff::StandardFldBuff(int totFlds, int * FldSize) : StandardLenBuff(SumFieldSizes(totFlds, FldSize)) { //Call method to initialize the buffer. InitFile(totFlds, FldSize); } //Function to return the total count of fields. int StandardFldBuff::NumberOfFields() const { //Return the total count stored in fldCnt. return fldCnt; } //Clear the fields. void StandardFldBuff::ClearField() { //call the base class function to clear the fields. StandardLenBuff::ClearField(); //Clear all fields. subField = 0; baseAry[0] = 0; BufferMode = 1; } //Function to add the next field to the buffer. int StandardFldBuff::addNxtFld(int FldSize) { //Set the buffer to the packing mode. bufferSet = 1; /*Check the fldCnt against AllowedFlds to know the possibility to add a next field. */ if (fldCnt == AllowedFlds) //If both are same, then return 0. return 0; //Check the maximum allowed bytes to find the space. if (SizeOfBuffer + FldSize > AllowedBytes) return 0; //Add the fieldsize to the array. FldSizeAry[fldCnt] = FldSize; //Increase the field count. fldCnt++; //Increase the buffer size. SizeOfBuffer += FldSize; return 1; } /* Declare the standard field header and its length */ static const char * FieldHeader = "FIELD"; static const int FieldHeaderSize = strlen(FieldHeader); //Function to read the header. int StandardFldBuff::ReadStreamHeader(istream & inpStream) { //Declare the variables. char * strr = new char[FieldHeaderSize + 1]; int totFlds, *FldSize; int reslt; // Read the FixedLengthBufferheader reslt = StandardLenBuff::ReadStreamHeader(inpStream); //Check for error. If so, return. if (reslt < 0) return -1; // Read the header inpStream.read(strr, FieldHeaderSize); //Check for consistency. if (!inpStream.good()) return -1; //Compare the headers. If not matching then return. if (strncmp(strr, FieldHeader, FieldHeaderSize) != 0) return -1; // Read the description of the record. inpStream.read((char*)&totFlds, sizeof(totFlds)); //Check for error. If so, return. if (!inpStream) return -1; //Create field size array. FldSize = new int[totFlds]; //Loop to read the field size. for (int aa = 0; aa < totFlds; aa++) { //Read the field size from the header. inpStream.read((char*)&FldSize[aa], sizeof(FldSize[aa])); } //Check the header. if (bufferSet) { //If fields count are not matching then return. if (totFlds != fldCnt) return -1; //Loop to check the field size. for (int j = 0; j < totFlds; j++) /*Check fiedlsize is matching with fieldsize of the array. If not then return. */ if (FldSize[j] != FldSizeAry[j]) return -1; //Return the record position. return inpStream.tellg(); } //Otherwise use header to initialize the buffer. InitFile(totFlds, FldSize); //Return the record position. return inpStream.tellg(); } //Function to write the header to the stream. int StandardFldBuff::WriteStreamHeader(ostream & outpStream) const { /* Declare variables*/ int reslt; //Check for bufferSet. If it is null then, return. if (!bufferSet) return -1; // Write FixedLengthBuffer header reslt = StandardLenBuff::WriteStreamHeader(outpStream); //Check for error. If so, return. if (!reslt) return -1; // Write the header. outpStream.write(FieldHeader, FieldHeaderSize); //Check for the consistency. If not, return. if (!outpStream.good()) return -1; // Write the details of the record. outpStream.write((char*)&fldCnt, sizeof(fldCnt)); //Loop to write the record size. for (int i = 0; i < fldCnt; i++) { //Write the field sizes to the stream. outpStream.write((char*)&FldSizeAry[i], sizeof(FldSizeAry[i])); } //Check for consistency. If not then return -1. if (!outpStream) return -1; //Return the record position. return outpStream.tellp(); } //Function to set the next field int StandardFldBuff::SetNextField(const void * fld, int sze) { //Check buffer is filled or not in packing mode. If //so, return. if (subField == fldCnt || !BufferMode) return -1; //Get the first byte. int srt = subsequentByte; //Get the total bytes to be packed. int pkSize = FldSizeAry[subField]; //Check pack size is equivalent to size then return -//1. if (sze != -1 && pkSize != sze) return -1; //Otherwise move the bytes to the buffer. memcpy(&baseAry[srt], fld, pkSize); //Increase the next field size. subsequentByte += pkSize; //Increase the next field count. subField++; //Check all fields are packed. if (subField == fldCnt) { //Set buffer to unpacked mode. BufferMode = -1; //Set the counters to 0. subField = subsequentByte = 0; } //Return the packed size. return pkSize; } //Extract the next field from the buffer. int StandardFldBuff::ExtractNextField(void * fld, int capBytes) { //set Buffer mode to unpack. BufferMode = 0; //Check buffer is full. If so, return, if (subField == fldCnt) return -1; //Get the first byte to extract. int start = subsequentByte; //Get the total bytes to be unpacked. int packSize = FldSizeAry[subField]; //Otherwise move the bytes from the buffer. memcpy(fld, &baseAry[start], packSize); //Increase the next field size. subsequentByte += packSize; //Increase the next field count. subField++; /*Check all fields are unpacked. If so, clear the fields.*/ if (subField == fldCnt) ClearField(); //Return the total unpacked bytes. return packSize; } //Function to display the standard field buffer info. void StandardFldBuff::DisplayBuffInfo(ostream & outpStream) const { //Call the base class method. StandardLenBuff::DisplayBuffInfo(outpStream); outpStream << endl; //Display the info. outpStream << "\t Allowed Fields Count " << AllowedFlds << " and Current Field Count " << fldCnt << endl; //Use loop to display all fields along with its size. for (int aa = 0; aa < fldCnt; aa++) outpStream << "\t FIELD " << aa << " Size " << FldSizeAry[aa] << endl; //Initialize the buffer array to 0. baseAry[SizeOfBuffer] = 0; //Display the nest field size and buffer size. outpStream << "Subsequent Byte: " << subsequentByte << endl; outpStream << "Currnet Buffer:" << baseAry << "'" << endl; } //Function to initialize the Buffer with allowed fields count. int StandardFldBuff::InitFile(int allowedFlds) { //Clear all the fields. ClearField(); /*Check allowedFlds for positive value. If allowedFlds is negative, then assign allowedFlds to 0. */ if (allowedFlds < 0) allowedFlds = 0; //Assign the values. AllowedFlds = allowedFlds; //Create the field array to AllowedFlds FldSizeAry = new int[AllowedFlds]; //Srt buffer size to 0. SizeOfBuffer = 0; //Set the field count to 0. fldCnt = 0; return 1; } //Function to initialize the Buffer with total field count and field size. int StandardFldBuff::InitFile(int totFlds, int * FldSize) { // Set the buffer to packing mode. bufferSet = 1; //Call Function to initialize the fields. InitFile(totFlds); // Add allowed number of fields to the field array. for (int aa = 0; aa < totFlds; aa++) //Call method to add the field. addNxtFld(FldSizeAry[aa]); //Return 1 on Success. return 1; } /* class TxtInd*/ class TxtInd { //Access Specifier. public: /*Constructor*/ TxtInd(int kysLimit = 100, int cntDiff = 1); /*Destructor*/ ~TxtInd(); /* insertKy key into given record address*/ int insertKy(const char * ky, int recordAddress); /* Remove a key */ int DelKy(const char * ky); /* Search a key */ int SrchKy(const char * ky) const; /* Print the text index */ void displayTxtInd(ostream &) const; //Access Specifier. protected: //Declare variables. int AllowedKeys; int cntKeys; char * * Keys; int * RecordAddresses; /* Find a key*/ int FndKy(const char * ky) const; /* Initialize the file */ int InitFile(int kysLimit, int cntDiff); /* represent the different keys*/ int distinct; /* Friend class declaration */ friend class TxtIndBuff; }; /* Constructor */ TxtInd::TxtInd(int kysLimit, int cntDiff) : cntKeys(0), Keys(0), RecordAddresses(0) { /* Initialize the files.*/ InitFile(kysLimit, cntDiff); } /* Dextructor to delete the index*/ TxtInd :: ~TxtInd() { /* Delete the keys*/ delete Keys; /* Delete the record addresses.*/ delete RecordAddresses; } /* Insert a key into the index*/ int TxtInd::insertKy(const char * ky, int recordAddress) { int kk; /* Find the index of the ky.*/ int index = FndKy(ky); /* Check ky is already present. If so, return*/ if (distinct && index >= 0) return 0; /* Check space is available. If not then return */ if (cntKeys == AllowedKeys) return 0; /* Loop to move the keys */ for (kk = cntKeys - 1; kk >= 0; kk--) { /* If location found, then return*/ if (strcmp(ky, Keys[kk])>0) break; //Otherise, move the keys . Keys[kk + 1] = Keys[kk]; //Move the record address. RecordAddresses[kk + 1] = RecordAddresses[kk]; } /* Place the ky at the location found*/ Keys[kk + 1] = strdup(ky); /* Store the ky address.*/ RecordAddresses[kk+ 1] = recordAddress; /* Increase the keys count.*/ cntKeys++; /* Return 1 */ return 1; } /* Function to delete ky at the index*/ int TxtInd::DelKy(const char * ky) { /* Find the ky index.*/ int in1 = FndKy(ky); /* Check the key index. If index is negative then return. Because ky is not present.*/ if (in1 < 0) return 0; /* Move keys to one step upward*/ for (int aa = in1; aa < cntKeys; aa++) { /* Move the key */ Keys[aa] = Keys[aa + 1]; /* Move the address*/ RecordAddresses[aa] = RecordAddresses[aa + 1]; } /* Decrement the keys count.*/ cntKeys--; /* Return 1 on successful deletion.*/ return 1; } /* Function to search a key in the index.*/ int TxtInd::SrchKy(const char * ky) const { /* Find the index of the key*/ int in1 = FndKy(ky); /* Check the index. If the index is negative then return. Because ky is not present in the index.*/ if (in1 < 0) return in1; /* Otherwise return the record address of the ky.*/ return RecordAddresses[in1]; } /* Function to display the index content*/ void TxtInd::displayTxtInd(ostream & outpStream) const { /* Display the keys limit and keys count*/ outpStream << "MAXKEYS: " << AllowedKeys << " NUMKEYS:" << cntKeys << endl; /* Loop to display all the keys in the index.*/ for (int aa = 0; aa<="" p="" style="box-sizing: border-box;"> /* Display the key and the record address.*/ outpStream << "\t KEY[" << aa << "] " << Keys[aa] << " RECORDADDRESS " << RecordAddresses[aa] << endl; } /* Function to locate the ky in the index*/ int TxtInd::FndKy(const char * ky) const { /* Use loop to check through the keys*/ for (int aa = 0; aa < cntKeys; aa++) //If ky is found then return the index. if (strcmp(Keys[aa], ky) == 0) return aa; /*If current key is greater than ky, then return. Because ky wont be in the index.*/ else if (strcmp(Keys[aa], ky)>0) return -1; return -1; } /* Function to initialize the files.*/ int TxtInd::InitFile(int kysLimit, int cntDiff) { /* initialize the different*/ distinct = cntDiff != 0; /* Check the kysLimit. If negative, then assign default value.*/ if (kysLimit <= 0) { //Assign 0 to AllowedKeys. AllowedKeys = 0; return 0; } /* Otherwise assign AllowedKeys with kysLimit*/ AllowedKeys = kysLimit; /* Create new 2d character array */ Keys = new char *[kysLimit]; /* Create an array for record address.*/ RecordAddresses = new int[kysLimit]; return 1; } /* Class that creates a buffer for the index */ class TxtIndBuff : public StandardFldBuff { //Access Specifier. public: /* Constructor */ TxtIndBuff(int kySize, int kysLimit = 100, int xFlds = 0, int exSize = 0); /* pack the index*/ int SetNextField(const TxtInd &); /* Unpack the index.*/ int ExtractNextField(TxtInd &); /* Print the text index buffer.*/ void DisplayTxtBuff(ostream &) const; //Access Specifier. protected: /* Declare the variables.*/ int AllowedKeys; int KySze; char * dumIn; }; /* Constructor to initialize the buffer of the index */ TxtIndBuff::TxtIndBuff(int kySize, int kysLimit, int xFlds, int exSize) : StandardFldBuff(1 + 2 * kysLimit + xFlds, sizeof(int)+kysLimit*kySize + kysLimit*sizeof(int)+exSize) { /* Set the AllowedKeys and KySze */ AllowedKeys = kysLimit; KySze = kySize; /* Add new field */ addNxtFld(sizeof(int)); /* Loop to add the new field */ for (int kk = 0; kk < kysLimit; kk++) { //Add new fields. addNxtFld(KySze); addNxtFld(sizeof(int)); } /* Create character array for the dummy */ dumIn = new char[kySize + 1]; } /* Set the next field */ int TxtIndBuff::SetNextField(const TxtInd & in1) { /* Declare variables */ int rslt; /* Clear the fields */ ClearField(); /* Pack the keys count */ rslt = StandardFldBuff::SetNextField(&in1.cntKeys); /* Loop to pack the keys and the record addresses */ for (int aa = 0; aa < in1.cntKeys; aa++) { /* Pack the key */ rslt = rslt && StandardFldBuff::SetNextField(in1.Keys[aa]); /* Pack the record address */ rslt = rslt && StandardFldBuff::SetNextField(&in1.RecordAddresses[aa]); } /* pack the other fields with dummyvalue */ for (int aa = 0; aa<="" p="" style="box-sizing: border-box;"> { /* Dummy values for other fields */ rslt = rslt && StandardFldBuff::SetNextField(dumIn); rslt = rslt && StandardFldBuff::SetNextField(dumIn); } /* return the packed result */ return rslt; } /* Function to unpack the fields */ int TxtIndBuff::ExtractNextField(TxtInd & in1) { int rslt; /* Unpack the keys count */ rslt = StandardFldBuff::ExtractNextField(&in1.cntKeys); /* Unpack the keys and record addresses */ for (int aa = 0; aa < in1.cntKeys; aa++) { /* Create array to hold key */ in1.Keys[aa] = new char[KySze]; /* Unpack the key */ rslt = rslt && StandardFldBuff::ExtractNextField(in1.Keys[aa]); /* Unpack the record address */ rslt = rslt && StandardFldBuff::ExtractNextField(&in1.RecordAddresses[aa]); } /*Unpack the dummy values */ for (int aa = 0; aa<="" p="" style="box-sizing: border-box;"> { /* Unpack the dummy values for the other fields */ rslt = rslt && StandardFldBuff::ExtractNextField(dumIn); rslt = rslt && StandardFldBuff::ExtractNextField(dumIn); } /* Return result */ return rslt; } /* Function to display the index buffer */ void TxtIndBuff::DisplayTxtBuff(ostream & outpStream) const { /* Display the key size and maximum key size */ outpStream << "TxtIndBuff: KySze " << KySze << " MaxKeys " << AllowedKeys << endl; /* Display the buffer */ StandardFldBuff::DisplayBuffInfo(outpStream); } // Class to represent buffered file operations class myBuffFile { //Access Specifier. public: //Constructor myBuffFile(BaseBuffer &); //Open the existing file. int Open(char * FILENAME, ios::openmode FILEOPENMODE); /* Create a file with passed filename*/ int CreateBuffFile(char * FILENAME, ios::openmode FILEOPENMODE); /* Close the buffer*/ int CloseField(); //Function to move to the first record in the buffer int Restart(); // Function to read the record. int SequentialRead(int RecordAddress = -1); //Function to write a record int SequentialWrite(int RecordAddress = -1); //Write the buffer at the file end. int AddAtTheEnd(); // Function to access the BaseBuffer BaseBuffer & GetBuffer(); //Access Specifier. protected: /*Declare the variables*/ BaseBuffer & baseAry; fstream BufFile; int hdrSize; int ReadStreamHeader(); int WriteStreamHeader(); }; /*Constructor to create a buffer*/ myBuffFile::myBuffFile(BaseBuffer & begin) : baseAry(begin) { } /*Function that opens an existing file and checks header is correct*/ int myBuffFile::Open(char * FILENAME, ios::openmode fileOpenMode) { //Open the file in the said mode. BufFile.open(FILENAME, fileOpenMode | ios::in | ios::binary); //Check for the consistency. If not then return. if (!BufFile.good()) return 0; //Otherwise, move to the starting point in the file. BufFile.seekg(0, ios::beg); BufFile.seekp(0, ios::beg); //Get the header size. hdrSize = ReadStreamHeader(); /*Check the header length. If header length is not present, then file is opened in output mode. so return.*/ if (!hdrSize) return 0; /*Move to the desired point */ BufFile.seekp(hdrSize, ios::beg); BufFile.seekg(hdrSize, ios::beg); /* return 1 if header is correct */ return BufFile.good(); } /* Function that creates a file and write down the header on it */ int myBuffFile::CreateBuffFile(char * FILENAME, ios::openmode fileOpenMode) { /* Open the file */ BufFile.open(FILENAME, fileOpenMode | ios::trunc | ios::in | ios::out | ios::binary); /* Check for consistency. If not, then return. */ if (!BufFile.good()) { /* Close the file */ BufFile.close(); /* Return on failure */ return 0; } /* Write the header */ hdrSize = WriteStreamHeader(); /* Return 1 if write success */ return hdrSize != 0; } /* Function to close the file */ int myBuffFile::CloseField() { /* Close the file and then return */ BufFile.close(); return 1; } /* Function to rewind to the said position */ int myBuffFile::Restart() { /*Go back to the end of the header field. */ BufFile.seekg(hdrSize, ios::beg); BufFile.seekp(hdrSize, ios::beg); //Return 1. return 1; } /*Function to read a record from the given record address */ int myBuffFile::SequentialRead(int RecordAddress) { /*If record address is not there, then read the next record.*/ if (RecordAddress == -1) /*Call BaseBuffer method to read the next record from the file.*/ return baseAry.SequentialRead(BufFile); //Otherwise read the said record. else /* Call BaseBuffer method to read the record at the given address */ return baseAry.DirectReadOP(BufFile, RecordAddress); } /* Function to write the buffer into the file */ int myBuffFile::SequentialWrite(int RecordAddress) { /*If record address is not there, then write the next record.*/ if (RecordAddress == -1) /*Call BaseBuffer method to write the next record from the file.*/ return baseAry.SequentialWrite(BufFile); //Otherwise read the said record else /* Call BaseBuffer method to write the record at the given address. */ return baseAry.DirectWriteOP(BufFile, RecordAddress); } /* Function to write the buffer at the end of the file. */ int myBuffFile::AddAtTheEnd() { /* Go to the file end*/ BufFile.seekp(0, ios::end); /* Call method to write the current buffer */ return baseAry.SequentialWrite(BufFile); } // Function to get the base buffer. BaseBuffer & myBuffFile::GetBuffer() { //Return the base buffer. return baseAry; } /* Function to read the header from the file */ int myBuffFile::ReadStreamHeader() { /* Call base buffer method to read the header from the given stream file */ return baseAry.ReadStreamHeader(BufFile); } /*Function to write the header to the file. */ int myBuffFile::WriteStreamHeader() { /* Write the header to the file by calling the base buffer write method.*/ return baseAry.WriteStreamHeader(BufFile); } /* Maximum Number keys allowed in a bucket. */ const int constMaxKys = 100; /* Forward Declaration. */ class hashTableDirectory; /* Class that defines the bucket of the hash table.*/ class HashTableBucket : public TxtInd { //Access Specifier public: /* Constructor to initialize a bucket*/ HashTableBucket(hashTableDirectory & dir, int kysLimit = constMaxKys); /*Insert a key into the bucket. */ int InsertKyBucket(char * ky, int recordAddress); /*Remove a key from a bucket */ int DeleteKyBucket(char * ky); /*Split the bucket*/ HashTableBucket * splitBucket(); /* Calculate a new range for the new bucket */ int newDomain(int & newDomStart, int & newDomEnd); /* Reorganize the keys */ int reorganizeKeys(HashTableBucket & newSplitBkt); /* Find the buddy bucket */ int discoverBuddy(); /* Try to combine the bucket wit its buddy */ int CombineAttempt(); /* Combine the buckets */ int AttachBuckkets(HashTableBucket * buddyBkt, int buddyBktInd); /* Print the bucket content */ ostream & displayBkt(ostream &); //Access specifier. protected: /* Declare variables.*/ int bktDepth; hashTableDirectory & myDirectory; int bktAddr; /* Declare friend Classes.*/ friend class hashTableDirectory; friend class BktBuff; }; /* Create a buffer class for the buckets */ class BktBuff : public TxtIndBuff { //Access specifier. public: /*Constructor*/ BktBuff(int kySize, int kysLimit); /*Set the next field*/ int SetNextField(const HashTableBucket & bkt); /* Get next field */ int ExtractNextField(HashTableBucket & bkt); }; /*Declare the maximum size of key */ const int MaxKeySize = 12; /* Class that defines the directory */ class hashTableDirectory { //Access Specifier. public: /*Constructor*/ hashTableDirectory(int bktKysLimit = -1); /*Destructor*/ ~hashTableDirectory(); /*open the named directory and bucket*/ int openDirectoryAndBucket(char * NAME); /*Create a directory and bucket in the name*/ int CreateDirectory(char * NAME); /*Function closes the directory*/ int clsDirectory(); /*Function insert a key into the bucket*/ int InsertKyDirectory(char * ky, int recordAddress); /*Function removes a key from the bucket*/ int delKyDirectory(char * ky); /*Function return the record address of the key*/ int srchDirectory(char * ky); /*Function return the Bucket address of the key if it is present */ int locateKy(char * ky); /*Print the directory content*/ ostream & displayDirectory(ostream & stream); //Access Specifier. protected: /*Declare variables */ int DrtyDepth; int entriesCnt; int * bktAddr; /*Declare member function */ /* increase the directory depth */ int increaseDirectDepth(); /* Merge the directory*/ int reduceSize(); /* Insert new bucket into the directory */ int InsertNewBucket(int bucketAddr, int first, int last); /* Delete a bucket from the directory */ int DelBkt(int bucketIndex, int depth); /* Append or modify a bucket */ int AppendBkt(HashTableBucket * bkt); /* Get bucket from file */ int GetBkt(HashTableBucket * bkt, int bucketAddr); /* Set the next field */ int SetNextField() const; /* Get next field */ int ExtractNextField(); /* Declare class objects */ int bktKyLimit; myBuffFile * FileDir; LenFldBuff * buffDir; HashTableBucket * currBkt; BktBuff * buffBkt; myBuffFile * FileBkt; HashTableBucket * tempBkt; /* Friend class declaration */ friend class HashTableBucket; }; /* Constructor to initialize the directory with the bucket keys limit */ hashTableDirectory::hashTableDirectory(int bktKysLimit) { /*Initialize the directory depth */ DrtyDepth = 0; /* Initialize the total entries count to 1 */ entriesCnt = 1; /* Create bucket array */ bktAddr = new int[entriesCnt]; /* Set bucket key limit */ bktKyLimit = bktKysLimit; /* initialize the objects */ buffDir = new LenFldBuff; FileDir = new myBuffFile(*buffDir); currBkt = new HashTableBucket(*this, bktKyLimit); buffBkt = new BktBuff(MaxKeySize, bktKyLimit); FileBkt = new myBuffFile(*buffBkt); tempBkt = new HashTableBucket(*this, bktKyLimit); } //Destructor hashTableDirectory::~hashTableDirectory() { /* Clear the directory content */ clsDirectory(); } /* Function to create a directory and bucket name */ void makeNames(char * NAME, char &* newDirName, char *& newBktName) { /* create the ouputstream */ ostrstream dirName1; /* Create the directory name */ dirName1 << NAME << ".dir" << ends; newDirName = strdup(dirName1.str()); /* Create output stream for bucket */ ostrstream bktName1; /* Create bucket name */ bktName1 << NAME << ".bkt" << ends; newBktName = strdup(bktName1.str()); } /* Open the directory and bucket */ int hashTableDirectory::openDirectoryAndBucket(char * NAME) { /*Declare variables */ int reslt; char * newDirName, *newBktName; /* Make the directory and bucket in the given name */ makeNames(NAME, newDirName, newBktName); /* open the Directory */ reslt = FileDir->Open(newDirName, ios::in | ios::out); /* Check for file open. If file is not opened then return 0*/ if (!reslt) return 0; /* Otherwise the directory */ reslt = FileDir->SequentialRead(); /* if couldnt able to read the directory content then return */ if (reslt == -1) return 0; /* Else read the next record */ reslt = ExtractNextField(); /* If failed, return */ if (!reslt == -1) return 0; /* Open the bucket */ reslt = FileBkt->Open(newBktName, ios::in | ios::out); /* Return the result */ return reslt; } /* Function to create a directory and bucket */ int hashTableDirectory::CreateDirectory(char * NAME) { /* Declare variables */ int reslt; char * newDirName, *newBktName; /* Create name for the directory and bucket */ makeNames(NAME, newDirName, newBktName); /* Create a buffer for the directory */ reslt = FileDir->CreateBuffFile(newDirName, ios::in | ios::out); /* Check buffer is created. If not then return */ if (!reslt) return 0; /* Create a buffer for the bucket */ reslt = FileBkt->CreateBuffFile(newBktName, ios::in | ios::out); /* Check buffer is created. If not then return */ if (!reslt) return 0; /* Place the empty current bucket into file */ bktAddr[0] = AppendBkt(currBkt); //Return. return reslt; } /* Function to write the directory to the file and close it */ int hashTableDirectory::clsDirectory() { int rslt; /* Set the next field */ rslt = SetNextField(); /* Check next field is set. If not return */ if (rslt == -1) return 0; /* Rewind the starting posistion */ FileDir->Restart(); /* Write the Directory to the file */ rslt = FileDir->SequentialWrite(); /* Check directory is written to the file. If not then return */ if (rslt == -1) return 0; /* Close the directory and the bucket */ return FileDir->CloseField() && FileBkt->CloseField(); } /* Function to insert a key into the directory */ int hashTableDirectory::InsertKyDirectory(char * ky, int recordAddress) { /* Search the directory for duplicates, */ int found = srchDirectory(ky); /* Check key is found. If not, then insert the key.*/ if (found == -1) /* Insert the key and return */ return currBkt->InsertKyBucket(ky, recordAddress); /* No insertion. key exist */ return 0; } /* Function to delete a key entry */ int hashTableDirectory::delKyDirectory(char * ky) { /* Locate the key in the directory */ int bucketAddr = locateKy(ky); /* Load the bucket that contains the key into the current bucket */ GetBkt(currBkt, bucketAddr); /* Delete the key from the bucket and return the address */ return currBkt->DeleteKyBucket(ky); } /* Function to search a key in the directory */ int hashTableDirectory::srchDirectory(char * ky) { /* Locate the key in the directory */ int bucketAddr = locateKy(ky); /* Load the bucket that contains the key into the current bucket */ GetBkt(currBkt, bucketAddr); /* Search the key in the bucket and return the address */ return currBkt->SrchKy(ky); } /*Function to double the directory size */ int hashTableDirectory::increaseDirectDepth() { /* Create a new size that is double of current size*/ int nwSze = 2 * entriesCnt; /* Create new address array for the bucket.*/ int * nwBktAddr = new int[nwSze]; /* Loop to reorganize the buckets address.*/ for (int aa = 0; aa < entriesCnt; aa++) { /* Find the bucket and its buddy address*/ nwBktAddr[2 * aa] = bktAddr[aa]; nwBktAddr[2 * aa + 1] = bktAddr[aa]; } /* Delete current bucket address.*/ delete bktAddr; /* Assign the new address to the bucket.*/ bktAddr = nwBktAddr; /* Increase the directory depth.*/ DrtyDepth++; /* Increase the directory entries to the new increased size.*/ entriesCnt = nwSze; //Return. return 1; } /*Function to reduce the directory size on deletion of a bucket.*/ int hashTableDirectory::reduceSize() { //Check the directory depth. If depth is null,return. if (DrtyDepth == 0) return 0; /*Loop to find the different buddies. If buddies are different then return.*/ for (int aa = 0; aa < entriesCnt; aa += 2) /*Check the buddies. If the buddies are different then return. */ if (bktAddr[aa] != bktAddr[aa + 1]) return 0; /* Otherwise reduce the size to half */ int nwSze = entriesCnt / 2; /* Declare new array to store the bucket address. */ int * nwAddrs = new int[nwSze]; /* Loop to find the new address*/ for (int aa = 0; aa < nwSze; aa++) /* address of a bucket.*/ nwAddrs[aa] = bktAddr[aa * 2]; /* Delete the current bucket address entries.*/ delete bktAddr; /* Store the new bucket addresses.*/ bktAddr = nwAddrs; /* Decrease the directory depth */ DrtyDepth--; /* modify the entries count */ entriesCnt = nwSze; return 1; } /* Function to insert a new bucket into the directory.*/ int hashTableDirectory::InsertNewBucket(int bktAddr1, int beg, int lst) { /* Loop to make cells to point to the new bucket.*/ for (int aa = beg; aa <= lst; aa++) bktAddr[aa] = bktAddr1; //Return. return 1; } /* Function to delete a bucket from the directory */ int hashTableDirectory::DelBkt(int bktInd, int bktDpt) { /* Calculate the number of bits to fill */ int fillBits = DrtyDepth - bktInd; /* Flip the lower bit */ int buddyBktInd = bktDpt ^ (1 << (fillBits - 1)); //Find the new bucket address. int nwBktAddr = bktAddr[buddyBktInd];\ /* Make lower bits to 0.*/ int lwInd = bktDpt >> fillBits << fillBits; /* Set the lower bits to 1.*/ int hghInd = lwInd + (1 << fillBits) - 1; /* set all cells to point to the new bucket address.*/ for (int aa = lwInd; aa <= hghInd; aa++) /* Assign new address to the cells of the deleted bucket.*/ bktAddr[aa] = nwBktAddr; //Return statement. return 0; } /*Function that locates a key in the directory.*/ int hashTableDirectory::locateKy(char * ky) { /* It returns the bucket address of the key.*/ return bktAddr[MakeAddress(ky, DrtyDepth)]; } /* Function that packs the buffer and return the total bytes packed.*/ int hashTableDirectory::SetNextField() const { /* Declare the variables.*/ int rslt, pcksze; /* Clear the fields.*/ buffDir->ClearField(); /* Determine the pack size.*/ pcksze = buffDir->SetNextField(&DrtyDepth, sizeof(int)); /* Check pack size. If pack size is -1, then return.*/ if (pcksze == -1) /* Return -1 because we dont have any more bytes to pack.*/ return -1; /* Otherwise pack the calculated number of bytes.*/ for (int aa = 0; aa<="" p="" style="box-sizing: border-box;"> { //Pack the next field. rslt = buffDir->SetNextField(&bktAddr[aa], sizeof(int)); //Check if nect field is packed. If not then return. if (rslt == -1) return -1; //Otherwise add the packed field size. pcksze += rslt; } //Return the total packed bytes. return pcksze; } /* Function to unpack the fields.*/ int hashTableDirectory::ExtractNextField() { int rslt; /* Extract the next field.*/ rslt = buffDir->ExtractNextField(&DrtyDepth, sizeof(int)); /* Check the result. if result is -1, then return.*/ if (rslt == -1) return -1; //Change the entries count. entriesCnt = 1 << DrtyDepth; /* Check the bucket address. If bucket address is present then delete the bucket addresses.*/ if (bktAddr != 0) delete bktAddr; //Make new array for bucket addresses. bktAddr = new int[entriesCnt]; //Loop to extract all the entries in the directory. for (int aa = 0; aa<="" p="" style="box-sizing: border-box;"> { /* Extract the current bucket */ rslt = buffDir->ExtractNextField(&bktAddr[aa], sizeof(int)); /* Check result. If not extracted then return.*/ if (rslt == -1) return -1; } //Return on success. return 0; } /* Function to append a new bucket to file or update a new bucket */ int hashTableDirectory::AppendBkt(HashTableBucket * bkt) { /* Declare the variable */ int rslt; /* Set the next field */ rslt = buffBkt->SetNextField(*bkt); /* Check the result. IF not then return */ if (rslt == -1) return -1; /* Get the bucket address.*/ int adr = bkt->bktAddr; /* Check the bucket address. If the bucket address is not null, then update the bucket.*/ if (adr != 0) return FileBkt->SequentialWrite(adr); /* Append the new bucket to the end of the file.*/ adr = FileBkt->AddAtTheEnd(); /* Assign the address to the new bucke.*/ bkt->bktAddr = adr; /* Return the bucket address.*/ return adr; } /* Function to read a bucket from the file.*/ int hashTableDirectory::GetBkt(HashTableBucket * bkt, int bktAdr) { int rslt; /* Read the bucket at the given address.*/ rslt = FileBkt->SequentialRead(bktAdr); /* Check result. If bucket not exist, then return.*/ if (rslt == -1) return 0; /* Otherwise unpack the bucket.*/ rslt = buffBkt->ExtractNextField(*bkt); /* Check bucket is unpacked. If not then return .*/ if (rslt == -1) return 0; /* Otherwise assign the address to the bucket.*/ bkt->bktAddr = bktAdr; //Return statement. return 1; } /* Function that displays the directory content.*/ ostream & hashTableDirectory::displayDirectory(ostream & outpStream) { /* Write the directroy depth and its size.*/ outpStream << "Directory Depth " << DrtyDepth << " size " << entriesCnt << endl; /* Loop to process the entries in the directory.*/ for (int aa = 0; aa<="" p="" style="box-sizing: border-box;"> { /* Display the bucket address.*/ outpStream << "bucket " << bktAddr[aa] << " addr " << (void *)aa << endl; /* Get the bucket from the file.*/ GetBkt(tempBkt, bktAddr[aa]); /* Display the bucket information.*/ tempBkt->displayBkt(outpStream); } /* Display the directory end.*/ outpStream << "DIRECTORY END." << endl; /* Return the outpStream.*/ return outpStream; } /* Constructor to initialize the bucket*/ HashTableBucket::HashTableBucket(hashTableDirectory & dir, int kysLimit) :TxtInd(kysLimit), myDirectory(dir) { //Assign the bucket address to 0. bktAddr = 0; //Assign the bucket depth to 0. bktDepth = 0; } /* Function that inserts a key into the bucket.*/ int HashTableBucket::InsertKyBucket(char * ky, int recordAddress) { /* Check space is available in the bucket. If so then insert the key into the bucket.*/ if (cntKeys < AllowedKeys) { /* Call method to insert the key into the address.*/ int rslt = TxtInd::insertKy(ky, recordAddress); /* Update the bucket.*/ myDirectory.AppendBkt(this); //Return. return rslt; } /* If bucket is full, then split the bucket and insert the key.*/ else { /* Call method to split the bucket.*/ splitBucket(); // Call method to insert the key into the bucket return myDirectory.InsertKyDirectory(ky, recordAddress); } } /* Function that deletes a key from the bucket.*/ int HashTableBucket::DeleteKyBucket(char * ky) { /* Call method to delete the key.*/ int rslt = TxtInd::DelKy(ky); /* Check the result. If key is not in the bucket then return.*/ if (!rslt) return 0; /* Make an attempt to merge the bucket*/ CombineAttempt(); /* Update the directory*/ myDirectory.AppendBkt(this); return 1; } /* Function to split the bucket*/ HashTableBucket * HashTableBucket::splitBucket() { /* Declare the variables.*/ int newDomStart, newDomEnd; /* Check the directory to split the bucket. If space is not available then double the directory size.*/ if (bktDepth == myDirectory.DrtyDepth) /* Increase the directory size*/ myDirectory.increaseDirectDepth(); /* Create new bucket.*/ HashTableBucket * newSplitBkt = new HashTableBucket(myDirectory, AllowedKeys); /* Append the new bucket at the file end.*/ myDirectory.AppendBkt(newSplitBkt); /* Set the domain for the current bucket.*/ newDomain(newDomStart, newDomEnd); /* Insert the new bucket into the directory.*/ myDirectory.InsertNewBucket(newSplitBkt->bktAddr, newDomStart, newDomEnd); /* Increase the bucket depth*/ bktDepth++; /* Assign the new bucket depth*/ newSplitBkt->bktDepth = bktDepth; /* Reorganize the keys between bucket and the split bucket.*/ reorganizeKeys(*newSplitBkt); /* Update the current bucket.*/ myDirectory.AppendBkt(this); /* Append the new bucket to the end.*/ myDirectory.AppendBkt(newSplitBkt); //Return the new bucket. return newSplitBkt; } /* Function to find the buddy bucket */ int HashTableBucket::discoverBuddy() { /* Check the directory depth. If depth is 0, then directory is empty. so return.*/ if (myDirectory.DrtyDepth == 0) return -1; /* Check the depth of the bucket and the directory. If the depths are different, then no buddy bucket exist.*/ if (bktDepth < myDirectory.DrtyDepth) return -1; /* Otherwise find the address of any key */ int shdAdr = MakeAddress(Keys[0], bktDepth); //Return the buddy address. return shdAdr ^ 1; } /* Function that tries to combine the bucket with its buddy */ int HashTableBucket::CombineAttempt() { int rslt; /* Locate the buddy of the bucket. */ int buddyBktInd = discoverBuddy(); /* If buddy index is 0, then return. Because no bucket to combine.*/ if (buddyBktInd == -1) return 0; /* Find the address of the buddy in the directory.*/ int buddyAddr = myDirectory.bktAddr[buddyBktInd]; /* Create a temporay bucket.*/ HashTableBucket * buddyBucket = new HashTableBucket(myDirectory, AllowedKeys); /* Load the buddy bucket into the temporary bucket.*/ myDirectory.GetBkt(buddyBucket, buddyAddr); /* Check the buckets sizes. If the sum of buckets sizes are long then return.*/ if (cntKeys + buddyBucket->cntKeys > AllowedKeys) return 0; /* Merge the buckets.*/ AttachBuckkets(buddyBucket, buddyBktInd); /* Reduce the directory size */ rslt = myDirectory.reduceSize(); /* Recursive call to make a combine attempt if possible.*/ if (rslt) CombineAttempt(); return 1; } /* Function that merges the bucket with its buddy*/ int HashTableBucket::AttachBuckkets(HashTableBucket * buddyBkt, int buddyBktInd) { int rslt; /* Loop to copy the keys of the buddy.*/ for (int aa = 0; aa < buddyBkt->cntKeys; aa++) { // Copy the keys from buddy to the bucket. rslt = InsertKyBucket(buddyBkt->Keys[aa], buddyBkt->RecordAddresses[aa]); //Check the result. If couldn’t copy,then return. if (!rslt) return 0; } /* Decrease the bucket depth */ bktDepth--; /* Delete the buddy bucket from the directory.*/ myDirectory.DelBkt(buddyBktInd, bktDepth); //Return statement. return 1; } /* Function to find the new domain for the split bucket*/ int HashTableBucket::newDomain(int & newDomStart, int & newDomEnd) { int shrdAdr = MakeAddress(Keys[0], bktDepth); /* Calculate the bits to fill the bucket.*/ int btsFill = myDirectory.DrtyDepth - (bktDepth + 1); /* Calculate the starting and ending domain.*/ newDomStart = (shrdAdr << 1) | 1; newDomEnd = newDomStart; /* Loop that find the start and end range.*/ for (int aa = 0; aa< btsFill; aa++) { /* Calculate the start and end for the split bucket.*/ newDomStart = newDomStart << 1; newDomEnd = (newDomEnd << 1) | 1; } //Return statement. return 1; } /* Function to reorganize the keys between bucket and the split bucket.*/ int HashTableBucket::reorganizeKeys(HashTableBucket & newSplitBkt) { /* Loop to check each key in the bucket.*/ for (int aa = cntKeys - 1; aa >= 0; aa--) { /* Get the bucket address of the key.*/ int bktAdr1 = myDirectory.locateKy(Keys[aa]); /* Check the bucket address. If not then place the key into the new split bucket.*/ if (bktAdr1 != bktAddr) { /* Insert a key into the new split bucket.*/ newSplitBkt.TxtInd::insertKy(Keys[aa], RecordAddresses[aa]); /* Delete the key from the current bucket.*/ TxtInd::DelKy(Keys[aa]); } } //Return 1. return 1; } /* Function to display the bucket content to the output stream.*/ ostream & HashTableBucket::displayBkt(ostream & outpStream) { /* Display the bucket depth*/ outpStream << "BUCKET DEPTH: " << bktDepth << endl; /* Print the bucket.*/ TxtInd::displayTxtInd(outpStream); /* Return the output stream.*/ return outpStream; } /* Constructor that initializes the buffer for the bucket.*/ BktBuff::BktBuff(int kySize, int kysLimit) : TxtIndBuff(kySize, kysLimit, 1, sizeof(int)) { /* Add the next field to the buffer.*/ addNxtFld(sizeof(int)); } /* Set the next field for the buffer.*/ int BktBuff::SetNextField(const HashTableBucket & bkt) { int rslt; /* Set the bucket.*/ rslt = TxtIndBuff::SetNextField(bkt); /* If not set, then return.*/ if (rslt == -1) return -1; /* Set the bucket depth*/ return StandardFldBuff::SetNextField(&bkt.bktDepth); } /* Function to unpack a bucket from the buffer.*/ int BktBuff::ExtractNextField(HashTableBucket & bkt) { int rslt; /* Unpack the bucket.*/ rslt = TxtIndBuff::ExtractNextField(bkt); /* Check bucket is unpacked. If not, return.*/ if (rslt == -1) return -1; /* Unpack the bucket depth.*/ return StandardFldBuff::ExtractNextField(&bkt.bktDepth); } //main() method int main() { /* Declare variables */ int reslt; char deleteKey[20]; char searchKey[20]; /* Create objects */ hashTableDirectory myDirectory(4); /* Create directory */ reslt = myDirectory.CreateDirectory("tsthash"); /* Declare keys to insert into the directory */ char * kys[] = { "David","Jerry","Tom","Mike" }; const int kysCnt = 4; //Loop to insert the keys into the directory */ for (int i = 0; i<="" p="" style="box-sizing: border-box;"> { /*Call hashTableDirectory method to insert the keys into the directory.*/ reslt = myDirectory.InsertKyDirectory(kys[i], MakeAddress(kys[i], 16)); } /* Insert the keys into the directory */ reslt = myDirectory.InsertKyDirectory("uma", MakeAddress("uma", 16)); reslt = myDirectory.InsertKyDirectory("abi", MakeAddress("abi", 16)); //Display the directory content. cout << "DIRECTORY CONTENT:" << endl; myDirectory.displayDirectory(cout); cout << "ENTER KEY TO DELETE:" << endl; cin >> deleteKey; /*Delete the key. */ reslt = myDirectory.delKyDirectory(deleteKey); /* Check key is deleted and display appropriate messages. */ if (reslt == 0) cout << "Key not present" << endl; //Otherwise, display key deleted successfully */ else cout << "Key deleted Successfully" << endl; /* Get key to search in the directory. */ cout << "Enter the key to search:" << endl; cin > searchKey; /* Call method to locate the given key. */ reslt = myDirectory.locateKy(searchKey); /* Check key is present. If not then display message.*/ if (!reslt) cout << "Key not present" << endl; //Otherwise, display key is in the directory. */ else cout << "Key present in the directory" << endl; /* Display the directory after deletion. */ myDirectory.displayDirectory(cout); /* Pause the console window. */ system("pause"); return 1; } Output: DIRECTORY CONTENT: Directory Depth 1 size 2 bucket 68 addr 00000000 BUCKET DEPTH: 1 MAXKEYS: 4 NUMKEYS:3 KEY[0] Jerry RECORDADDRESS 21972 KEY[1] Mike RECORDADDRESS 29970 KEY[2] uma RECORDADDRESS 9312 bucket 140 addr 00000001 BUCKET DEPTH: 1 MAXKEYS: 4 NUMKEYS:3 KEY[0] David RECORDADDRESS 34116 KEY[1] Tom RECORDADDRESS 52178 KEY[2] abi RECORDADDRESS 38528 DIRECTORY END. ENTER KEY TO DELETE: ABI Key not present Enter the key to search: abi Key present in the directory Directory Depth 1 size 2 bucket 68 addr 00000000 BUCKET DEPTH: 1 MAXKEYS: 4 NUMKEYS:3 KEY[0] Jerry RECORDADDRESS 21972 KEY[1] Mike RECORDADDRESS 29970 KEY[2] uma RECORDADDRESS 9312 bucket 140 addr 00000001 BUCKET DEPTH: 1 MAXKEYS: 4 NUMKEYS:3 KEY[0] David RECORDADDRESS 34116 KEY[1] Tom RECORDADDRESS 52178 KEY[2] abi RECORDADDRESS 38528 DIRECTORY END. Sample output file: tsthash.bkt: tsthash.dir: Explanation: Above provided code is used to insert the records in a file and after that all the content are retrieved and delted by using the various hashing techniques as shown in the above output.

Program Plan: 1.The below mentioned variables are used: A variable totSum to store the int type of value. A variable kyLen of in ttype thst stores the length of the key. 2. The below mentioned functions are used in the program that are declared within the class. locateHash()function to find the hash value of the key. MakeAddress() function to find the address of the key. Initfile() function for initialization of the buffer. ClearField() function to clear all the fields. Various virtual functions and constructors are also declared a sper the need of the class. Program description: To write a program that inserts records into a file and retrieves and deletes them using extendible hashing or linear hashing techniques. Program: #include <iostream> #include <fstream> #include <cstring> #include <cctype> #include <iomanip> using namespace std; /Function to find the Hash value for the given key/ int locateHash(char* ky) { //Declare variables. int totSum = 0; //Find the length of the string and store it. int kyLen = strlen(ky); //Make the length to even if the length is odd. if (kyLen % 2 == 1) kyLen++; //Use loop to find the hash value of the given key. for (int aa = 0; aa < kyLen; aa += 2) totSum = (totSum + 100 * ky[aa] + ky[aa + 1]) % 19937; //Return the hash value. return totSum; } //Function to find the address of the key. int MakeAddress(char * ky, int locDepth) { //Declare variables. int retvall = 0; int maskk = 1; int hashVall = locateHash(ky); //Use loop to find the location to insert the key. for (int aa = 0; aa < locDepth; aa++) { retvall = retvall << 1; /Find the lower address bit / int lowerAddrBit = hashVall & maskk; retvall = retvall | lowerAddrBit; hashVall = hashVall >> 1; } /* Return the address/ return retvall; } /Abstract class that serves as a base class for all buffer files. / class BaseBuffer { //Access Specifier. public: //Constructor. BaseBuffer(int capBytes = 1000); //Copy the given BaseBuffer into current BaseBuffer. BaseBuffer & operator = (const BaseBuffer &); //Remove the fields from the file buffer virtual void ClearField(); //Fix the next field value for the buffer. virtual int SetNextField(const void fld, int size = -1) = 0; //Get the next field value of the file buffer. virtual int ExtractNextField(void * fld, int maxbytes = -1) = 0; //Display Buffer file. virtual void DisplayBuffInfo(ostream &) const; //Initialize the buffer files variables. int InitFile(int capBytes); //Sequential Read operations. virtual int SequentialRead(istream &) = 0; //Sequential Write operations. virtual int SequentialWrite(ostream &) const = 0; // Performing direct read operations. virtual int DirectReadOP(istream &, int recref); //Performing direct write operations. virtual int DirectWriteOP(ostream &, int recref) const; // Read a header from the stream. virtual int ReadStreamHeader(istream &) = 0; //write a header to the stream virtual int WriteStreamHeader(ostream &) const; //Access Specifier protected: //It is said to TRUE if buffer is assigned with value. int bufferSet; //Array to hold the field values. char * baseAry; //Overall size of the packed fields. int SizeOfBuffer; //Buffer limit. int AllowedBytes; // Index of next byte to be set/extract. int subsequentByte; //TRUE if buffer is in the packing fileOpenMode. int BufferMode; }; //Constructor that initializes the BaseBuffer to said sizes BaseBuffer::BaseBuffer(int capBytes) { //Call method to initialize the variables. InitFile(capBytes); } /Overloaded assignment operator that copies one BaseBuffer into another. / BaseBuffer & BaseBuffer :: operator = (const BaseBuffer & bufT) { /Check for buffer size. If buffer size is not matching then return. / if (AllowedBytes < bufT.SizeOfBuffer) return this; //Otherwise copy the bufT into current buffer. //copy the bufferSet bufferSet = bufT.bufferSet; //Copy the buffer size. SizeOfBuffer = bufT.SizeOfBuffer; //Copy the field value. memcpy(baseAry, bufT.baseAry, bufT.SizeOfBuffer); //Set the next byte to process. subsequentByte = bufT.subsequentByte; //Set the packing or unpacking mode. BufferMode = BufferMode; //Return the BaseBuffer return this; } //Function to clear the fields void BaseBuffer::ClearField() { //Clear the next byte to process subsequentByte = 0; //Set the packing mode. BufferMode = 1; } //Function to print the info of the buffer size. void BaseBuffer::DisplayBuffInfo(ostream & stream) const { /Print the maximum allowed bytes and current size of the buffer. / stream << "Bytes Limited " << AllowedBytes << " Present Size " << SizeOfBuffer; } //Function initializes the BaseBuffer variables. int BaseBuffer::InitFile(int capBytes) { //Set the BaseBuffer to unpack mode. bufferSet = 0; /Check the capBytes. If capBytes is less than zero, then assign capBytes to 0./ if (capBytes < 0) capBytes = 0; //Set the maximum limited bytes. AllowedBytes = capBytes; //Create the allowed bytes of buffer array baseAry. baseAry = new char[AllowedBytes]; //Initialize the buffer size to 0. SizeOfBuffer = 0; //Clear BufferMode and subsequentByte to default //value. ClearField(); return 1; } /For the given record reference, the fiunction accesses the record directly. / int BaseBuffer::DirectReadOP(istream & inpStream, int recordReff) { //In the file move to the given position. inpStream.seekg(recordReff, ios::beg); /Check if current position is equal to the record position. if not, then return -1. / if (inpStream.tellg() != static_cast(recordReff)) return -1; //Otherwise, perform the sequential read operation. return SequentialRead(inpStream); } //Function that writes the record into the file directly. int BaseBuffer::DirectWriteOP(ostream & outpStream, int recordReff) const { //Get the position in the file. outpStream.seekp(recordReff, ios::beg); /If file position and record position are same then perform write directly. / if (outpStream.tellp() != static_cast(recordReff)) //If not, return -1 on unsuccessful write. return -1; //Otherwise, Perform the sequential write. return SequentialWrite(outpStream); } /Declare the header / static const char * hdrStrr = "BaseBuffer"; /Declare Header size/ static const int hdrSize = strlen(hdrStrr); /Function to read the stream header/ int BaseBuffer::ReadStreamHeader(istream & inpStream) { char strr[12]; //Move to the given position. inpStream.seekg(0, ios::beg); //Read the header field in the file. inpStream.read(strr, hdrSize); //Check inpStream is good. If not return -1. if (!inpStream.good()) return -1; /Compare the headers. If headers are matching and identical then return the header size. / if (strncmp(strr, hdrStrr, hdrSize) == 0) return hdrSize; //Otherwise, return -1 on failure. else return -1; } /Function to Write the stream header/ int BaseBuffer::WriteStreamHeader(ostream & outpStream) const { //Goto the position in the output file. outpStream.seekp(0, ios::beg); //Write the record. outpStream.write(hdrStrr, hdrSize); // Check outpStream is good. If not then return -1. if (!outpStream.good()) return -1; //Otherwise return the header size. return hdrSize; } /Class that serves as a base class for variable length records. / class ModifiableBuff : public BaseBuffer { //Access Specifier public: //Argumented Constructor. ModifiableBuff(int AllowedBytes = 1000); //Copy cinstructor. ModifiableBuff(const ModifiableBuff & buffer) : BaseBuffer(buffer){} //Clear the fields. void ClearField(); //Function to perform the sequential Read operations. int SequentialRead(istream &); //Function to perform the sequential Write operations. int SequentialWrite(ostream &) const; //Function to read the stream header int ReadStreamHeader(istream &); //Function to write the stream header. int WriteStreamHeader(ostream &) const; //Print the cariable length buffer. void DisplayBuffInfo(ostream &) const; //Return the buffer size. int getBufferSize() const; //Function to initialize the variables. int InitFile(); }; /* Constructor that initializes the Buffer to limited sites. / ModifiableBuff::ModifiableBuff(int capBytes) : BaseBuffer(capBytes) { /Call the function InitFile() to initialize the fields./ InitFile(); } //Function to clear the fields. void ModifiableBuff::ClearField() { //Call Base class method to clear the fields. BaseBuffer::ClearField(); } //Read the number of bytes from the input stream and write it into the buffer field. int ModifiableBuff::SequentialRead(istream & inpStream) { //Check end of file is reached. if so return -1 on //failure. if (inpStream.eof()) return -1; //Store the address. int recordAddress = inpStream.tellg(); //Clear all the fields. ClearField(); unsigned short filebuffSize; //Read the buffer length. inpStream.read((char )&filebuffSize, sizeof(filebuffSize)); /Check for the good condition.If file is not in the good condition then return -1 on failure./ if (!inpStream.good()) { //Clear the input stream. inpStream.clear(); return -1; } //Assign the buffer length. SizeOfBuffer = filebuffSize; /Check for overflow. If SizeOfBuffer is exceeding the AllowedBytes, then it indicates the overflow./ if (SizeOfBuffer > AllowedBytes) return -1; //Get the buffer. inpStream.read(baseAry, SizeOfBuffer); /* Check for the good condition.If file is not in the good condition then return -1 on failure. / if (!inpStream.good()) { //Clear the input stream. inpStream.clear(); return -1; } //Return the record address. return recordAddress; } /Function to write the buffer length and buffer into the output stream/ int ModifiableBuff::SequentialWrite(ostream & outpStream) const { //Get the record address. int recordAddress = outpStream.tellp(); unsigned short filebuffSize; //Store the buffer size. filebuffSize = SizeOfBuffer; //Write the buffer size to the output file. outpStream.write((char )&filebuffSize, sizeof(filebuffSize)); //Check for error. if error occurred then return. if (!outpStream) return -1; //Otherwise write the buffer. outpStream.write(baseAry, SizeOfBuffer); //Check for suucess. if not then return -1. if (!outpStream.good()) return -1; //Otherwise return the record address. return recordAddress; } /Declare the header and header size for the variable length files/ const char * variableHeader = "MODIFIABLE"; const int variableHeaderSize = strlen(variableHeader); //Read the header from the input file. int ModifiableBuff::ReadStreamHeader(istream & inpStream) { //Declare the variables. char strr[12]; int reslt; // Read the BaseBuffer header reslt = BaseBuffer::ReadStreamHeader(inpStream); //Check for the consistency. if (!reslt) return 0; // read the variable length field header inpStream.read(strr, variableHeaderSize); //Check for consistency. if (!inpStream.good()) return 0; /Compare the headers. If they are not matching then return false. / if (strncmp(strr, variableHeader, variableHeaderSize) != 0) return 0; // Read the buffer array. return inpStream.tellg(); } /Function to write the buffer header, variable length header, header length to the output stream. / int ModifiableBuff::WriteStreamHeader(ostream & outpStream) const { int reslt; // write the BaseBuffer header. reslt = BaseBuffer::WriteStreamHeader(outpStream); //Check for consistency. if (!reslt) return 0; // Write the header. outpStream.write(variableHeader, variableHeaderSize); //Check for consistency. if (!outpStream.good()) return 0; // Returnt the record description. return outpStream.tellp(); } /Function to display the variable length Allowed buffer size and current buffer size./ void ModifiableBuff::DisplayBuffInfo(ostream & stream) const { //Use the base class function to print the info. BaseBuffer::DisplayBuffInfo(stream); } //Function to initialize the variable length buffer. int ModifiableBuff::InitFile() { //Clear the fields. ClearField(); //Return 1 on success. return 1; } //Class creates the variable length buffer with length. class LenFldBuff : public ModifiableBuff { //Access Specifier. public: //Constructor LenFldBuff(int capBytes = 1000); // Copy constructor. LenFldBuff(const LenFldBuff & buffer) : ModifiableBuff(buffer) {} //Clear the buffer fields. void ClearField(); //Set the next field. int SetNextField(const void * fld, int size = -1); //Get the next field value. int ExtractNextField(void fld, int capBytes = -1); //Print the length field buffer info. void DisplayBuffInfo(ostream &) const; //Initialize the length field buffer variables. int InitFile(); }; //Constructor to initialize the variables. LenFldBuff::LenFldBuff(int capBytes) : ModifiableBuff(capBytes) { //Call InitFile() to initialize the variables. InitFile(); } //Function to clear the buffer fields. void LenFldBuff::ClearField() { //Call the base class method to clear the fields. ModifiableBuff::ClearField(); } /Function that set the next field value./ int LenFldBuff::SetNextField(const void bufField, int FldSize) { //Declare variables. short strrLen; /Check for size greater than 0. if so then assign the size to strrLen / if (FldSize >= 0) strrLen = FldSize; //Otherwise assignt the bufField length to strrLen. else strrLen = strlen((char )bufField); //Get the first character to pack. int start = subsequentByte; //Get the next byte. subsequentByte += (strrLen + sizeof(strrLen)); //Check for overflow. if (subsequentByte > AllowedBytes) return -1; //Pack the bytes. memcpy(&baseAry[start], &strrLen, sizeof(strrLen)); memcpy(&baseAry[start + sizeof(strrLen)], bufField, strrLen); //Assign the buffer size. SizeOfBuffer = subsequentByte; //Return the total bytes packed. return strrLen; } / Function to extract the subsequent bytes and return the total extracted bytes/ int LenFldBuff::ExtractNextField(void bufField, int capBytes) { //Declare variable. short strrLen; //Check for no fields. if (subsequentByte >= SizeOfBuffer) return -1; //Get the first byte to be extracted. int start = subsequentByte; //Read the pack memcpy(&strrLen, &baseAry[start], sizeof(strrLen)); //Check field is too long. if (capBytes != -1 && strrLen > capBytes) return -1; //Set the next byte. subsequentByte += strrLen + sizeof(strrLen); //Check for no fields. if (subsequentByte > SizeOfBuffer) return -1; //Read the buffer. memcpy(bufField, &baseAry[start + sizeof(strrLen)], strrLen); //Terminate the buffer string. if (capBytes > strrLen || capBytes == -1) ((char )bufField)[strrLen] = 0; //return the total bytes extracted. return strrLen; } /Function that print the length field buffer info/ void LenFldBuff::DisplayBuffInfo(ostream & outpstream) const { outpstream << "Maximum Allowed Bytes: " << AllowedBytes << " and Current size: " << SizeOfBuffer << endl; } /Function that initialiazes the buffer field/ int LenFldBuff::InitFile() { //Set the buffer to packing mode. bufferSet = 1; //Clear the fields. ClearField(); return 1; } //Class buffer that holds the fixed length records. class StandardLenBuff : public BaseBuffer { //Access Specifier. public: //Constructor StandardLenBuff(int rcdSize = 1000); //Copy Constructor. StandardLenBuff(const StandardLenBuff & buffer); //Function to clear the fields. void ClearField(); //Function for sequential Read int SequentialRead(istream &); //Function for sequential write. int SequentialWrite(ostream &) const; //Function to read the header. int ReadStreamHeader(istream &); //Function to write the header. int WriteStreamHeader(ostream &) const; //Function to display the buffer info. void DisplayBuffInfo(ostream &) const; //Get the size of the buffer. int getBufferSize() const; //Access Specifier. protected: //Function to initialize the file. int InitFile(int rcdSize); //Function to modify the record size. int modifyRcdSze(int rcdSize); }; //Constructor that initializes the buffer. inline StandardLenBuff::StandardLenBuff(const StandardLenBuff & buf1) : BaseBuffer(buf1) { /Call the function InitFile() to initialize the buffer file. / InitFile(buf1.SizeOfBuffer); } //Constructor to Initialize the file to given record size. StandardLenBuff::StandardLenBuff(int rcdSize) : BaseBuffer(rcdSize) { //Initialize the buffer to the given record size. InitFile(rcdSize); } //Clear the fields. void StandardLenBuff::ClearField() { //Clear all the fields.. BaseBuffer::ClearField(); baseAry[0] = 0; //Set the buffer to packing mode. BufferMode = 1; } //Function to read the input stream. int StandardLenBuff::SequentialRead(istream & inpStream) { //Get the record address. int recordAddress = inpStream.tellg(); //Clear the input stream. inpStream.clear(); //Clear the field. ClearField(); //Set the buffer to unpacking mode. BufferMode = 0; //Read the string from the input stream. inpStream.read(baseAry, SizeOfBuffer); /Check for consistency. if the file is not consistent then clear the input stream and return record address./ if (!inpStream.good()) { //Clear the input stream. inpStream.clear(); //return the record address. return recordAddress; } //Otherwise return the record address. return recordAddress; } /Function to read the number of bytes from the output stream and return the record location./ int StandardLenBuff::SequentialWrite(ostream & outpStream) const { //Get the record address. int recordAddress = outpStream.tellp(); //Read the buffer. outpStream.write(baseAry, SizeOfBuffer); /Check for consistency. If the output stream is not good, then return -1. / if (!outpStream.good()) return -1; //Otherwise, return the record address. return recordAddress; } / Declare the header and header size for the fixed length buffer/ static const char StdHeader = "STANDARD"; static const int StdHeaderSize = strlen(StdHeader); //Function to read header from stream. int StandardLenBuff::ReadStreamHeader(istream & inpStream) { //Declare the variables. char strr[10]; int rcdSize; int reslt; // Read the base class BaseBuffer Buffer. reslt = BaseBuffer::ReadStreamHeader(inpStream); //Check for success. If not, then return -1. if (reslt < 0) return -1; // Read the string "STANDARD" inpStream.read(strr, StdHeaderSize); /Check for consistency. If not then return -1 on failure./ if (!inpStream.good()) return -1; /Compare the headers for identical. If not, then return -1. / if (strncmp(strr, StdHeader, StdHeaderSize) != 0) return -1; //Read the record size. inpStream.read((char)&rcdSize, sizeof(rcdSize)); //Check the header for consistency. if (bufferSet) { /Check the buffer length and recordsize. If buffer length / if (rcdSize != SizeOfBuffer) return -1; } // Otherwise, use the header to initialize the buffer. modifyRcdSze(rcdSize); //Return the return inpStream.tellg(); } /Function to write the buffer header, standard length header, header length to the output stream. / int StandardLenBuff::WriteStreamHeader(ostream & outpStream) const { int reslt; /Check buffer for packing mode. If buffer is not set for packing mode then return -1. / if (!bufferSet) return -1; // Write the header of the BaseBuffer. reslt = BaseBuffer::WriteStreamHeader(outpStream); //Check for consistency. If not then return -1. if (!reslt) return -1; // Write the header of the standard length buffer. outpStream.write(StdHeader, StdHeaderSize); //Check for consistency. If not then return -1. if (!outpStream.good()) return -1; // Write the buffer length. outpStream.write((char )&SizeOfBuffer, sizeof(SizeOfBuffer)); //Check for the consistency. If not then return -1. if (!outpStream.good()) return -1; //Return the output stream position. return outpStream.tellp(); } //Function to write the standard length buffer info to the output stream. void StandardLenBuff::DisplayBuffInfo(ostream & outpStream) const { BaseBuffer::DisplayBuffInfo(outpStream); outpStream << "STANDARD "; } //Constructor to initialize the buffer to the given rcdSize int StandardLenBuff::InitFile(int rcdSize) { //Clear the fields. ClearField(); //Assign the rcdSize to SizeOfBuffer. SizeOfBuffer = rcdSize; return 1; } //Function to modify the buffer size. int StandardLenBuff::modifyRcdSze(int rcdSize) { //Change the SizeOfBuffer to rcdSize. SizeOfBuffer = rcdSize; return 1; } /* class StandardFldBuff/ class StandardFldBuff : public StandardLenBuff { //Access Specifier. public: /Constructors/ StandardFldBuff(int allowedFlds, int RcdSize = 1000); StandardFldBuff(int allowedFlds, int FldSize); StandardFldBuff(const StandardFldBuff &); /* Overloaded assignment operator/ StandardFldBuff & operator = (const StandardFldBuff &); /Clear all fields/ void ClearField(); /Describe the next Field/ int addNxtFld(int FldSize); / read header/ int ReadStreamHeader(istream &); /write header/ int WriteStreamHeader(ostream &) const; /set next field/ int SetNextField(const void fld, int size = -1); /* get next field/ int ExtractNextField(void fld, int capBytes = -1); /* Display Buffer info/ void DisplayBuffInfo(ostream &) const; / return the total defined fields/ int NumberOfFields() const; /function to initialize the files/ int InitFile(int allowedFlds); int InitFile(int totFlds, int FldSize); //Access Specifier. protected: /Declare the variables/ int * FldSizeAry; int AllowedFlds; int fldCnt; int subField; }; //Constructor to initialize the buffer. inline StandardFldBuff::StandardFldBuff(const StandardFldBuff & buf1) : StandardLenBuff(buf1) { //Call function to initialize the buffer. InitFile(buf1.fldCnt, buf1.FldSizeAry); } //Constructor that initializes the buffer with maximum allowed sizes. StandardFldBuff::StandardFldBuff(int allowedFlds, int capBytes) : StandardLenBuff(capBytes) { //Call function to initialize the buffer. InitFile(allowedFlds); } // Function to find the record size from field size. static int SumFieldSizes(int totFlds, int * FldSize) { int recSum = 0; //Use loop to find the record sum. for (int aa = 0; aa< totFlds; aa++) //Add the field size to the sum. recSum += FldSize[aa]; //Return the sum. return recSum; } /Overloaded assignment operator to copy the buffer/ StandardFldBuff & StandardFldBuff :: operator = (const StandardFldBuff & buff) { /* Check for field identity. If not matching then return. / if (fldCnt != buff.fldCnt) //Return on failure. return this; //Loop to check the field sizes are matching. for (int aa = 0; aa < fldCnt; aa++) /Check each field size of buff1 and current buffer. If not, then return./ if (FldSizeAry[aa] != buff.FldSizeAry[aa]) //Return on failure. return this; //Assign the subsequent field. subField = buff.subField; //call the super class function. StandardLenBuff :: operator = (buff); //Return statement. return this; } //Constuctor to create the fields with particular size. StandardFldBuff::StandardFldBuff(int totFlds, int * FldSize) : StandardLenBuff(SumFieldSizes(totFlds, FldSize)) { //Call method to initialize the buffer. InitFile(totFlds, FldSize); } //Function to return the total count of fields. int StandardFldBuff::NumberOfFields() const { //Return the total count stored in fldCnt. return fldCnt; } //Clear the fields. void StandardFldBuff::ClearField() { //call the base class function to clear the fields. StandardLenBuff::ClearField(); //Clear all fields. subField = 0; baseAry[0] = 0; BufferMode = 1; } //Function to add the next field to the buffer. int StandardFldBuff::addNxtFld(int FldSize) { //Set the buffer to the packing mode. bufferSet = 1; /Check the fldCnt against AllowedFlds to know the possibility to add a next field. / if (fldCnt == AllowedFlds) //If both are same, then return 0. return 0; //Check the maximum allowed bytes to find the space. if (SizeOfBuffer + FldSize > AllowedBytes) return 0; //Add the fieldsize to the array. FldSizeAry[fldCnt] = FldSize; //Increase the field count. fldCnt++; //Increase the buffer size. SizeOfBuffer += FldSize; return 1; } /* Declare the standard field header and its length / static const char FieldHeader = "FIELD"; static const int FieldHeaderSize = strlen(FieldHeader); //Function to read the header. int StandardFldBuff::ReadStreamHeader(istream & inpStream) { //Declare the variables. char * strr = new char[FieldHeaderSize + 1]; int totFlds, FldSize; int reslt; // Read the FixedLengthBufferheader reslt = StandardLenBuff::ReadStreamHeader(inpStream); //Check for error. If so, return. if (reslt < 0) return -1; // Read the header inpStream.read(strr, FieldHeaderSize); //Check for consistency. if (!inpStream.good()) return -1; //Compare the headers. If not matching then return. if (strncmp(strr, FieldHeader, FieldHeaderSize) != 0) return -1; // Read the description of the record. inpStream.read((char)&totFlds, sizeof(totFlds)); //Check for error. If so, return. if (!inpStream) return -1; //Create field size array. FldSize = new int[totFlds]; //Loop to read the field size. for (int aa = 0; aa < totFlds; aa++) { //Read the field size from the header. inpStream.read((char)&FldSize[aa], sizeof(FldSize[aa])); } //Check the header. if (bufferSet) { //If fields count are not matching then return. if (totFlds != fldCnt) return -1; //Loop to check the field size. for (int j = 0; j < totFlds; j++) /Check fiedlsize is matching with fieldsize of the array. If not then return. / if (FldSize[j] != FldSizeAry[j]) return -1; //Return the record position. return inpStream.tellg(); } //Otherwise use header to initialize the buffer. InitFile(totFlds, FldSize); //Return the record position. return inpStream.tellg(); } //Function to write the header to the stream. int StandardFldBuff::WriteStreamHeader(ostream & outpStream) const { / Declare variables/ int reslt; //Check for bufferSet. If it is null then, return. if (!bufferSet) return -1; // Write FixedLengthBuffer header reslt = StandardLenBuff::WriteStreamHeader(outpStream); //Check for error. If so, return. if (!reslt) return -1; // Write the header. outpStream.write(FieldHeader, FieldHeaderSize); //Check for the consistency. If not, return. if (!outpStream.good()) return -1; // Write the details of the record. outpStream.write((char)&fldCnt, sizeof(fldCnt)); //Loop to write the record size. for (int i = 0; i < fldCnt; i++) { //Write the field sizes to the stream. outpStream.write((char)&FldSizeAry[i], sizeof(FldSizeAry[i])); } //Check for consistency. If not then return -1. if (!outpStream) return -1; //Return the record position. return outpStream.tellp(); } //Function to set the next field int StandardFldBuff::SetNextField(const void fld, int sze) { //Check buffer is filled or not in packing mode. If //so, return. if (subField == fldCnt || !BufferMode) return -1; //Get the first byte. int srt = subsequentByte; //Get the total bytes to be packed. int pkSize = FldSizeAry[subField]; //Check pack size is equivalent to size then return -//1. if (sze != -1 && pkSize != sze) return -1; //Otherwise move the bytes to the buffer. memcpy(&baseAry[srt], fld, pkSize); //Increase the next field size. subsequentByte += pkSize; //Increase the next field count. subField++; //Check all fields are packed. if (subField == fldCnt) { //Set buffer to unpacked mode. BufferMode = -1; //Set the counters to 0. subField = subsequentByte = 0; } //Return the packed size. return pkSize; } //Extract the next field from the buffer. int StandardFldBuff::ExtractNextField(void * fld, int capBytes) { //set Buffer mode to unpack. BufferMode = 0; //Check buffer is full. If so, return, if (subField == fldCnt) return -1; //Get the first byte to extract. int start = subsequentByte; //Get the total bytes to be unpacked. int packSize = FldSizeAry[subField]; //Otherwise move the bytes from the buffer. memcpy(fld, &baseAry[start], packSize); //Increase the next field size. subsequentByte += packSize; //Increase the next field count. subField++; /Check all fields are unpacked. If so, clear the fields./ if (subField == fldCnt) ClearField(); //Return the total unpacked bytes. return packSize; } //Function to display the standard field buffer info. void StandardFldBuff::DisplayBuffInfo(ostream & outpStream) const { //Call the base class method. StandardLenBuff::DisplayBuffInfo(outpStream); outpStream << endl; //Display the info. outpStream << "\t Allowed Fields Count " << AllowedFlds << " and Current Field Count " << fldCnt << endl; //Use loop to display all fields along with its size. for (int aa = 0; aa < fldCnt; aa++) outpStream << "\t FIELD " << aa << " Size " << FldSizeAry[aa] << endl; //Initialize the buffer array to 0. baseAry[SizeOfBuffer] = 0; //Display the nest field size and buffer size. outpStream << "Subsequent Byte: " << subsequentByte << endl; outpStream << "Currnet Buffer:" << baseAry << "'" << endl; } //Function to initialize the Buffer with allowed fields count. int StandardFldBuff::InitFile(int allowedFlds) { //Clear all the fields. ClearField(); /Check allowedFlds for positive value. If allowedFlds is negative, then assign allowedFlds to 0. / if (allowedFlds < 0) allowedFlds = 0; //Assign the values. AllowedFlds = allowedFlds; //Create the field array to AllowedFlds FldSizeAry = new int[AllowedFlds]; //Srt buffer size to 0. SizeOfBuffer = 0; //Set the field count to 0. fldCnt = 0; return 1; } //Function to initialize the Buffer with total field count and field size. int StandardFldBuff::InitFile(int totFlds, int * FldSize) { // Set the buffer to packing mode. bufferSet = 1; //Call Function to initialize the fields. InitFile(totFlds); // Add allowed number of fields to the field array. for (int aa = 0; aa < totFlds; aa++) //Call method to add the field. addNxtFld(FldSizeAry[aa]); //Return 1 on Success. return 1; } /* class TxtInd/ class TxtInd { //Access Specifier. public: /Constructor/ TxtInd(int kysLimit = 100, int cntDiff = 1); /Destructor/ ~TxtInd(); / insertKy key into given record address/ int insertKy(const char ky, int recordAddress); /* Remove a key / int DelKy(const char ky); /* Search a key / int SrchKy(const char ky) const; /* Print the text index / void displayTxtInd(ostream &) const; //Access Specifier. protected: //Declare variables. int AllowedKeys; int cntKeys; char * Keys; int * RecordAddresses; /* Find a key/ int FndKy(const char ky) const; /* Initialize the file / int InitFile(int kysLimit, int cntDiff); / represent the different keys/ int distinct; / Friend class declaration / friend class TxtIndBuff; }; / Constructor / TxtInd::TxtInd(int kysLimit, int cntDiff) : cntKeys(0), Keys(0), RecordAddresses(0) { / Initialize the files./ InitFile(kysLimit, cntDiff); } / Dextructor to delete the index/ TxtInd :: ~TxtInd() { / Delete the keys/ delete Keys; / Delete the record addresses./ delete RecordAddresses; } / Insert a key into the index/ int TxtInd::insertKy(const char ky, int recordAddress) { int kk; /* Find the index of the ky./ int index = FndKy(ky); / Check ky is already present. If so, return/ if (distinct && index >= 0) return 0; / Check space is available. If not then return / if (cntKeys == AllowedKeys) return 0; / Loop to move the keys / for (kk = cntKeys - 1; kk >= 0; kk--) { / If location found, then return/ if (strcmp(ky, Keys[kk])>0) break; //Otherise, move the keys . Keys[kk + 1] = Keys[kk]; //Move the record address. RecordAddresses[kk + 1] = RecordAddresses[kk]; } / Place the ky at the location found/ Keys[kk + 1] = strdup(ky); / Store the ky address./ RecordAddresses[kk+ 1] = recordAddress; / Increase the keys count./ cntKeys++; / Return 1 / return 1; } / Function to delete ky at the index/ int TxtInd::DelKy(const char ky) { /* Find the ky index./ int in1 = FndKy(ky); / Check the key index. If index is negative then return. Because ky is not present./ if (in1 < 0) return 0; / Move keys to one step upward/ for (int aa = in1; aa < cntKeys; aa++) { / Move the key / Keys[aa] = Keys[aa + 1]; / Move the address/ RecordAddresses[aa] = RecordAddresses[aa + 1]; } / Decrement the keys count./ cntKeys--; / Return 1 on successful deletion./ return 1; } / Function to search a key in the index./ int TxtInd::SrchKy(const char ky) const { /* Find the index of the key/ int in1 = FndKy(ky); / Check the index. If the index is negative then return. Because ky is not present in the index./ if (in1 < 0) return in1; / Otherwise return the record address of the ky./ return RecordAddresses[in1]; } / Function to display the index content/ void TxtInd::displayTxtInd(ostream & outpStream) const { / Display the keys limit and keys count/ outpStream << "MAXKEYS: " << AllowedKeys << " NUMKEYS:" << cntKeys << endl; / Loop to display all the keys in the index./ for (int aa = 0; aa<="" p="" style="box-sizing: border-box;"> / Display the key and the record address./ outpStream << "\t KEY[" << aa << "] " << Keys[aa] << " RECORDADDRESS " << RecordAddresses[aa] << endl; } / Function to locate the ky in the index/ int TxtInd::FndKy(const char ky) const { /* Use loop to check through the keys/ for (int aa = 0; aa < cntKeys; aa++) //If ky is found then return the index. if (strcmp(Keys[aa], ky) == 0) return aa; /If current key is greater than ky, then return. Because ky wont be in the index./ else if (strcmp(Keys[aa], ky)>0) return -1; return -1; } / Function to initialize the files./ int TxtInd::InitFile(int kysLimit, int cntDiff) { / initialize the different/ distinct = cntDiff != 0; / Check the kysLimit. If negative, then assign default value./ if (kysLimit <= 0) { //Assign 0 to AllowedKeys. AllowedKeys = 0; return 0; } / Otherwise assign AllowedKeys with kysLimit/ AllowedKeys = kysLimit; / Create new 2d character array / Keys = new char [kysLimit]; /* Create an array for record address./ RecordAddresses = new int[kysLimit]; return 1; } / Class that creates a buffer for the index / class TxtIndBuff : public StandardFldBuff { //Access Specifier. public: / Constructor / TxtIndBuff(int kySize, int kysLimit = 100, int xFlds = 0, int exSize = 0); / pack the index/ int SetNextField(const TxtInd &); / Unpack the index./ int ExtractNextField(TxtInd &); / Print the text index buffer./ void DisplayTxtBuff(ostream &) const; //Access Specifier. protected: / Declare the variables./ int AllowedKeys; int KySze; char dumIn; }; /* Constructor to initialize the buffer of the index / TxtIndBuff::TxtIndBuff(int kySize, int kysLimit, int xFlds, int exSize) : StandardFldBuff(1 + 2 kysLimit + xFlds, sizeof(int)+kysLimitkySize + kysLimitsizeof(int)+exSize) { /* Set the AllowedKeys and KySze / AllowedKeys = kysLimit; KySze = kySize; / Add new field / addNxtFld(sizeof(int)); / Loop to add the new field / for (int kk = 0; kk < kysLimit; kk++) { //Add new fields. addNxtFld(KySze); addNxtFld(sizeof(int)); } / Create character array for the dummy / dumIn = new char[kySize + 1]; } / Set the next field / int TxtIndBuff::SetNextField(const TxtInd & in1) { / Declare variables / int rslt; / Clear the fields / ClearField(); / Pack the keys count / rslt = StandardFldBuff::SetNextField(&in1.cntKeys); / Loop to pack the keys and the record addresses / for (int aa = 0; aa < in1.cntKeys; aa++) { / Pack the key / rslt = rslt && StandardFldBuff::SetNextField(in1.Keys[aa]); / Pack the record address / rslt = rslt && StandardFldBuff::SetNextField(&in1.RecordAddresses[aa]); } / pack the other fields with dummyvalue / for (int aa = 0; aa<="" p="" style="box-sizing: border-box;"> { / Dummy values for other fields / rslt = rslt && StandardFldBuff::SetNextField(dumIn); rslt = rslt && StandardFldBuff::SetNextField(dumIn); } / return the packed result / return rslt; } / Function to unpack the fields / int TxtIndBuff::ExtractNextField(TxtInd & in1) { int rslt; / Unpack the keys count / rslt = StandardFldBuff::ExtractNextField(&in1.cntKeys); / Unpack the keys and record addresses / for (int aa = 0; aa < in1.cntKeys; aa++) { / Create array to hold key / in1.Keys[aa] = new char[KySze]; / Unpack the key / rslt = rslt && StandardFldBuff::ExtractNextField(in1.Keys[aa]); / Unpack the record address / rslt = rslt && StandardFldBuff::ExtractNextField(&in1.RecordAddresses[aa]); } /Unpack the dummy values / for (int aa = 0; aa<="" p="" style="box-sizing: border-box;"> { / Unpack the dummy values for the other fields / rslt = rslt && StandardFldBuff::ExtractNextField(dumIn); rslt = rslt && StandardFldBuff::ExtractNextField(dumIn); } / Return result / return rslt; } / Function to display the index buffer / void TxtIndBuff::DisplayTxtBuff(ostream & outpStream) const { / Display the key size and maximum key size / outpStream << "TxtIndBuff: KySze " << KySze << " MaxKeys " << AllowedKeys << endl; / Display the buffer / StandardFldBuff::DisplayBuffInfo(outpStream); } // Class to represent buffered file operations class myBuffFile { //Access Specifier. public: //Constructor myBuffFile(BaseBuffer &); //Open the existing file. int Open(char FILENAME, ios::openmode FILEOPENMODE); /* Create a file with passed filename/ int CreateBuffFile(char FILENAME, ios::openmode FILEOPENMODE); /* Close the buffer/ int CloseField(); //Function to move to the first record in the buffer int Restart(); // Function to read the record. int SequentialRead(int RecordAddress = -1); //Function to write a record int SequentialWrite(int RecordAddress = -1); //Write the buffer at the file end. int AddAtTheEnd(); // Function to access the BaseBuffer BaseBuffer & GetBuffer(); //Access Specifier. protected: /Declare the variables/ BaseBuffer & baseAry; fstream BufFile; int hdrSize; int ReadStreamHeader(); int WriteStreamHeader(); }; /Constructor to create a buffer/ myBuffFile::myBuffFile(BaseBuffer & begin) : baseAry(begin) { } /Function that opens an existing file and checks header is correct/ int myBuffFile::Open(char FILENAME, ios::openmode fileOpenMode) { //Open the file in the said mode. BufFile.open(FILENAME, fileOpenMode | ios::in | ios::binary); //Check for the consistency. If not then return. if (!BufFile.good()) return 0; //Otherwise, move to the starting point in the file. BufFile.seekg(0, ios::beg); BufFile.seekp(0, ios::beg); //Get the header size. hdrSize = ReadStreamHeader(); /Check the header length. If header length is not present, then file is opened in output mode. so return./ if (!hdrSize) return 0; /Move to the desired point / BufFile.seekp(hdrSize, ios::beg); BufFile.seekg(hdrSize, ios::beg); /* return 1 if header is correct / return BufFile.good(); } / Function that creates a file and write down the header on it / int myBuffFile::CreateBuffFile(char FILENAME, ios::openmode fileOpenMode) { /* Open the file / BufFile.open(FILENAME, fileOpenMode | ios::trunc | ios::in | ios::out | ios::binary); / Check for consistency. If not, then return. / if (!BufFile.good()) { / Close the file / BufFile.close(); / Return on failure / return 0; } / Write the header / hdrSize = WriteStreamHeader(); / Return 1 if write success / return hdrSize != 0; } / Function to close the file / int myBuffFile::CloseField() { / Close the file and then return / BufFile.close(); return 1; } / Function to rewind to the said position / int myBuffFile::Restart() { /Go back to the end of the header field. / BufFile.seekg(hdrSize, ios::beg); BufFile.seekp(hdrSize, ios::beg); //Return 1. return 1; } /Function to read a record from the given record address / int myBuffFile::SequentialRead(int RecordAddress) { /If record address is not there, then read the next record./ if (RecordAddress == -1) /Call BaseBuffer method to read the next record from the file./ return baseAry.SequentialRead(BufFile); //Otherwise read the said record. else / Call BaseBuffer method to read the record at the given address / return baseAry.DirectReadOP(BufFile, RecordAddress); } / Function to write the buffer into the file / int myBuffFile::SequentialWrite(int RecordAddress) { /If record address is not there, then write the next record./ if (RecordAddress == -1) /Call BaseBuffer method to write the next record from the file./ return baseAry.SequentialWrite(BufFile); //Otherwise read the said record else / Call BaseBuffer method to write the record at the given address. / return baseAry.DirectWriteOP(BufFile, RecordAddress); } / Function to write the buffer at the end of the file. / int myBuffFile::AddAtTheEnd() { / Go to the file end/ BufFile.seekp(0, ios::end); / Call method to write the current buffer / return baseAry.SequentialWrite(BufFile); } // Function to get the base buffer. BaseBuffer & myBuffFile::GetBuffer() { //Return the base buffer. return baseAry; } / Function to read the header from the file / int myBuffFile::ReadStreamHeader() { / Call base buffer method to read the header from the given stream file / return baseAry.ReadStreamHeader(BufFile); } /Function to write the header to the file. / int myBuffFile::WriteStreamHeader() { / Write the header to the file by calling the base buffer write method./ return baseAry.WriteStreamHeader(BufFile); } / Maximum Number keys allowed in a bucket. / const int constMaxKys = 100; / Forward Declaration. / class hashTableDirectory; / Class that defines the bucket of the hash table./ class HashTableBucket : public TxtInd { //Access Specifier public: / Constructor to initialize a bucket/ HashTableBucket(hashTableDirectory & dir, int kysLimit = constMaxKys); /Insert a key into the bucket. / int InsertKyBucket(char ky, int recordAddress); /Remove a key from a bucket / int DeleteKyBucket(char * ky); /Split the bucket/ HashTableBucket * splitBucket(); /* Calculate a new range for the new bucket / int newDomain(int & newDomStart, int & newDomEnd); / Reorganize the keys / int reorganizeKeys(HashTableBucket & newSplitBkt); / Find the buddy bucket / int discoverBuddy(); / Try to combine the bucket wit its buddy / int CombineAttempt(); / Combine the buckets / int AttachBuckkets(HashTableBucket buddyBkt, int buddyBktInd); /* Print the bucket content / ostream & displayBkt(ostream &); //Access specifier. protected: / Declare variables./ int bktDepth; hashTableDirectory & myDirectory; int bktAddr; / Declare friend Classes./ friend class hashTableDirectory; friend class BktBuff; }; / Create a buffer class for the buckets / class BktBuff : public TxtIndBuff { //Access specifier. public: /Constructor/ BktBuff(int kySize, int kysLimit); /Set the next field/ int SetNextField(const HashTableBucket & bkt); / Get next field / int ExtractNextField(HashTableBucket & bkt); }; /Declare the maximum size of key / const int MaxKeySize = 12; / Class that defines the directory / class hashTableDirectory { //Access Specifier. public: /Constructor/ hashTableDirectory(int bktKysLimit = -1); /Destructor/ ~hashTableDirectory(); /open the named directory and bucket/ int openDirectoryAndBucket(char NAME); /Create a directory and bucket in the name/ int CreateDirectory(char * NAME); /Function closes the directory/ int clsDirectory(); /Function insert a key into the bucket/ int InsertKyDirectory(char * ky, int recordAddress); /Function removes a key from the bucket/ int delKyDirectory(char * ky); /Function return the record address of the key/ int srchDirectory(char * ky); /Function return the Bucket address of the key if it is present / int locateKy(char * ky); /Print the directory content/ ostream & displayDirectory(ostream & stream); //Access Specifier. protected: /Declare variables / int DrtyDepth; int entriesCnt; int * bktAddr; /Declare member function / /* increase the directory depth / int increaseDirectDepth(); / Merge the directory/ int reduceSize(); / Insert new bucket into the directory / int InsertNewBucket(int bucketAddr, int first, int last); / Delete a bucket from the directory / int DelBkt(int bucketIndex, int depth); / Append or modify a bucket / int AppendBkt(HashTableBucket bkt); /* Get bucket from file / int GetBkt(HashTableBucket bkt, int bucketAddr); /* Set the next field / int SetNextField() const; / Get next field / int ExtractNextField(); / Declare class objects / int bktKyLimit; myBuffFile FileDir; LenFldBuff * buffDir; HashTableBucket * currBkt; BktBuff * buffBkt; myBuffFile * FileBkt; HashTableBucket * tempBkt; /* Friend class declaration / friend class HashTableBucket; }; / Constructor to initialize the directory with the bucket keys limit / hashTableDirectory::hashTableDirectory(int bktKysLimit) { /Initialize the directory depth / DrtyDepth = 0; / Initialize the total entries count to 1 / entriesCnt = 1; / Create bucket array / bktAddr = new int[entriesCnt]; / Set bucket key limit / bktKyLimit = bktKysLimit; / initialize the objects / buffDir = new LenFldBuff; FileDir = new myBuffFile(buffDir); currBkt = new HashTableBucket(this, bktKyLimit); buffBkt = new BktBuff(MaxKeySize, bktKyLimit); FileBkt = new myBuffFile(buffBkt); tempBkt = new HashTableBucket(this, bktKyLimit); } //Destructor hashTableDirectory::~hashTableDirectory() { / Clear the directory content / clsDirectory(); } / Function to create a directory and bucket name / void makeNames(char NAME, char &* newDirName, char & newBktName) { / create the ouputstream / ostrstream dirName1; / Create the directory name / dirName1 << NAME << ".dir" << ends; newDirName = strdup(dirName1.str()); / Create output stream for bucket / ostrstream bktName1; / Create bucket name / bktName1 << NAME << ".bkt" << ends; newBktName = strdup(bktName1.str()); } / Open the directory and bucket / int hashTableDirectory::openDirectoryAndBucket(char NAME) { /Declare variables / int reslt; char * newDirName, newBktName; / Make the directory and bucket in the given name / makeNames(NAME, newDirName, newBktName); / open the Directory / reslt = FileDir->Open(newDirName, ios::in | ios::out); / Check for file open. If file is not opened then return 0/ if (!reslt) return 0; / Otherwise the directory / reslt = FileDir->SequentialRead(); / if couldnt able to read the directory content then return / if (reslt == -1) return 0; / Else read the next record / reslt = ExtractNextField(); / If failed, return / if (!reslt == -1) return 0; / Open the bucket / reslt = FileBkt->Open(newBktName, ios::in | ios::out); / Return the result / return reslt; } / Function to create a directory and bucket / int hashTableDirectory::CreateDirectory(char NAME) { /* Declare variables / int reslt; char newDirName, newBktName; / Create name for the directory and bucket / makeNames(NAME, newDirName, newBktName); / Create a buffer for the directory / reslt = FileDir->CreateBuffFile(newDirName, ios::in | ios::out); / Check buffer is created. If not then return / if (!reslt) return 0; / Create a buffer for the bucket / reslt = FileBkt->CreateBuffFile(newBktName, ios::in | ios::out); / Check buffer is created. If not then return / if (!reslt) return 0; / Place the empty current bucket into file / bktAddr[0] = AppendBkt(currBkt); //Return. return reslt; } / Function to write the directory to the file and close it / int hashTableDirectory::clsDirectory() { int rslt; / Set the next field / rslt = SetNextField(); / Check next field is set. If not return / if (rslt == -1) return 0; / Rewind the starting posistion / FileDir->Restart(); / Write the Directory to the file / rslt = FileDir->SequentialWrite(); / Check directory is written to the file. If not then return / if (rslt == -1) return 0; / Close the directory and the bucket / return FileDir->CloseField() && FileBkt->CloseField(); } / Function to insert a key into the directory / int hashTableDirectory::InsertKyDirectory(char ky, int recordAddress) { /* Search the directory for duplicates, / int found = srchDirectory(ky); / Check key is found. If not, then insert the key./ if (found == -1) / Insert the key and return / return currBkt->InsertKyBucket(ky, recordAddress); / No insertion. key exist / return 0; } / Function to delete a key entry / int hashTableDirectory::delKyDirectory(char ky) { /* Locate the key in the directory / int bucketAddr = locateKy(ky); / Load the bucket that contains the key into the current bucket / GetBkt(currBkt, bucketAddr); / Delete the key from the bucket and return the address / return currBkt->DeleteKyBucket(ky); } / Function to search a key in the directory / int hashTableDirectory::srchDirectory(char ky) { /* Locate the key in the directory / int bucketAddr = locateKy(ky); / Load the bucket that contains the key into the current bucket / GetBkt(currBkt, bucketAddr); / Search the key in the bucket and return the address / return currBkt->SrchKy(ky); } /Function to double the directory size / int hashTableDirectory::increaseDirectDepth() { / Create a new size that is double of current size/ int nwSze = 2 entriesCnt; /* Create new address array for the bucket./ int nwBktAddr = new int[nwSze]; /* Loop to reorganize the buckets address./ for (int aa = 0; aa < entriesCnt; aa++) { / Find the bucket and its buddy address/ nwBktAddr[2 aa] = bktAddr[aa]; nwBktAddr[2 * aa + 1] = bktAddr[aa]; } /* Delete current bucket address./ delete bktAddr; / Assign the new address to the bucket./ bktAddr = nwBktAddr; / Increase the directory depth./ DrtyDepth++; / Increase the directory entries to the new increased size./ entriesCnt = nwSze; //Return. return 1; } /Function to reduce the directory size on deletion of a bucket./ int hashTableDirectory::reduceSize() { //Check the directory depth. If depth is null,return. if (DrtyDepth == 0) return 0; /Loop to find the different buddies. If buddies are different then return./ for (int aa = 0; aa < entriesCnt; aa += 2) /Check the buddies. If the buddies are different then return. / if (bktAddr[aa] != bktAddr[aa + 1]) return 0; / Otherwise reduce the size to half / int nwSze = entriesCnt / 2; / Declare new array to store the bucket address. / int nwAddrs = new int[nwSze]; /* Loop to find the new address/ for (int aa = 0; aa < nwSze; aa++) / address of a bucket./ nwAddrs[aa] = bktAddr[aa 2]; /* Delete the current bucket address entries./ delete bktAddr; / Store the new bucket addresses./ bktAddr = nwAddrs; / Decrease the directory depth / DrtyDepth--; / modify the entries count / entriesCnt = nwSze; return 1; } / Function to insert a new bucket into the directory./ int hashTableDirectory::InsertNewBucket(int bktAddr1, int beg, int lst) { / Loop to make cells to point to the new bucket./ for (int aa = beg; aa <= lst; aa++) bktAddr[aa] = bktAddr1; //Return. return 1; } / Function to delete a bucket from the directory / int hashTableDirectory::DelBkt(int bktInd, int bktDpt) { / Calculate the number of bits to fill / int fillBits = DrtyDepth - bktInd; / Flip the lower bit / int buddyBktInd = bktDpt ^ (1 << (fillBits - 1)); //Find the new bucket address. int nwBktAddr = bktAddr[buddyBktInd];\ / Make lower bits to 0./ int lwInd = bktDpt >> fillBits << fillBits; / Set the lower bits to 1./ int hghInd = lwInd + (1 << fillBits) - 1; / set all cells to point to the new bucket address./ for (int aa = lwInd; aa <= hghInd; aa++) / Assign new address to the cells of the deleted bucket./ bktAddr[aa] = nwBktAddr; //Return statement. return 0; } /Function that locates a key in the directory./ int hashTableDirectory::locateKy(char ky) { /* It returns the bucket address of the key./ return bktAddr[MakeAddress(ky, DrtyDepth)]; } / Function that packs the buffer and return the total bytes packed./ int hashTableDirectory::SetNextField() const { / Declare the variables./ int rslt, pcksze; / Clear the fields./ buffDir->ClearField(); / Determine the pack size./ pcksze = buffDir->SetNextField(&DrtyDepth, sizeof(int)); / Check pack size. If pack size is -1, then return./ if (pcksze == -1) / Return -1 because we dont have any more bytes to pack./ return -1; / Otherwise pack the calculated number of bytes./ for (int aa = 0; aa<="" p="" style="box-sizing: border-box;"> { //Pack the next field. rslt = buffDir->SetNextField(&bktAddr[aa], sizeof(int)); //Check if nect field is packed. If not then return. if (rslt == -1) return -1; //Otherwise add the packed field size. pcksze += rslt; } //Return the total packed bytes. return pcksze; } / Function to unpack the fields./ int hashTableDirectory::ExtractNextField() { int rslt; / Extract the next field./ rslt = buffDir->ExtractNextField(&DrtyDepth, sizeof(int)); / Check the result. if result is -1, then return./ if (rslt == -1) return -1; //Change the entries count. entriesCnt = 1 << DrtyDepth; / Check the bucket address. If bucket address is present then delete the bucket addresses./ if (bktAddr != 0) delete bktAddr; //Make new array for bucket addresses. bktAddr = new int[entriesCnt]; //Loop to extract all the entries in the directory. for (int aa = 0; aa<="" p="" style="box-sizing: border-box;"> { / Extract the current bucket / rslt = buffDir->ExtractNextField(&bktAddr[aa], sizeof(int)); / Check result. If not extracted then return./ if (rslt == -1) return -1; } //Return on success. return 0; } / Function to append a new bucket to file or update a new bucket / int hashTableDirectory::AppendBkt(HashTableBucket bkt) { /* Declare the variable / int rslt; / Set the next field / rslt = buffBkt->SetNextField(bkt); /* Check the result. IF not then return / if (rslt == -1) return -1; / Get the bucket address./ int adr = bkt->bktAddr; / Check the bucket address. If the bucket address is not null, then update the bucket./ if (adr != 0) return FileBkt->SequentialWrite(adr); / Append the new bucket to the end of the file./ adr = FileBkt->AddAtTheEnd(); / Assign the address to the new bucke./ bkt->bktAddr = adr; / Return the bucket address./ return adr; } / Function to read a bucket from the file./ int hashTableDirectory::GetBkt(HashTableBucket bkt, int bktAdr) { int rslt; /* Read the bucket at the given address./ rslt = FileBkt->SequentialRead(bktAdr); / Check result. If bucket not exist, then return./ if (rslt == -1) return 0; / Otherwise unpack the bucket./ rslt = buffBkt->ExtractNextField(bkt); /* Check bucket is unpacked. If not then return ./ if (rslt == -1) return 0; / Otherwise assign the address to the bucket./ bkt->bktAddr = bktAdr; //Return statement. return 1; } / Function that displays the directory content./ ostream & hashTableDirectory::displayDirectory(ostream & outpStream) { / Write the directroy depth and its size./ outpStream << "Directory Depth " << DrtyDepth << " size " << entriesCnt << endl; / Loop to process the entries in the directory./ for (int aa = 0; aa<="" p="" style="box-sizing: border-box;"> { / Display the bucket address./ outpStream << "bucket " << bktAddr[aa] << " addr " << (void )aa << endl; /* Get the bucket from the file./ GetBkt(tempBkt, bktAddr[aa]); / Display the bucket information./ tempBkt->displayBkt(outpStream); } / Display the directory end./ outpStream << "DIRECTORY END." << endl; / Return the outpStream./ return outpStream; } / Constructor to initialize the bucket/ HashTableBucket::HashTableBucket(hashTableDirectory & dir, int kysLimit) :TxtInd(kysLimit), myDirectory(dir) { //Assign the bucket address to 0. bktAddr = 0; //Assign the bucket depth to 0. bktDepth = 0; } / Function that inserts a key into the bucket./ int HashTableBucket::InsertKyBucket(char ky, int recordAddress) { /* Check space is available in the bucket. If so then insert the key into the bucket./ if (cntKeys < AllowedKeys) { / Call method to insert the key into the address./ int rslt = TxtInd::insertKy(ky, recordAddress); / Update the bucket./ myDirectory.AppendBkt(this); //Return. return rslt; } / If bucket is full, then split the bucket and insert the key./ else { / Call method to split the bucket./ splitBucket(); // Call method to insert the key into the bucket return myDirectory.InsertKyDirectory(ky, recordAddress); } } / Function that deletes a key from the bucket./ int HashTableBucket::DeleteKyBucket(char ky) { /* Call method to delete the key./ int rslt = TxtInd::DelKy(ky); / Check the result. If key is not in the bucket then return./ if (!rslt) return 0; / Make an attempt to merge the bucket/ CombineAttempt(); / Update the directory/ myDirectory.AppendBkt(this); return 1; } / Function to split the bucket/ HashTableBucket HashTableBucket::splitBucket() { /* Declare the variables./ int newDomStart, newDomEnd; / Check the directory to split the bucket. If space is not available then double the directory size./ if (bktDepth == myDirectory.DrtyDepth) / Increase the directory size/ myDirectory.increaseDirectDepth(); / Create new bucket./ HashTableBucket newSplitBkt = new HashTableBucket(myDirectory, AllowedKeys); /* Append the new bucket at the file end./ myDirectory.AppendBkt(newSplitBkt); / Set the domain for the current bucket./ newDomain(newDomStart, newDomEnd); / Insert the new bucket into the directory./ myDirectory.InsertNewBucket(newSplitBkt->bktAddr, newDomStart, newDomEnd); / Increase the bucket depth/ bktDepth++; / Assign the new bucket depth/ newSplitBkt->bktDepth = bktDepth; / Reorganize the keys between bucket and the split bucket./ reorganizeKeys(newSplitBkt); /* Update the current bucket./ myDirectory.AppendBkt(this); / Append the new bucket to the end./ myDirectory.AppendBkt(newSplitBkt); //Return the new bucket. return newSplitBkt; } / Function to find the buddy bucket / int HashTableBucket::discoverBuddy() { / Check the directory depth. If depth is 0, then directory is empty. so return./ if (myDirectory.DrtyDepth == 0) return -1; / Check the depth of the bucket and the directory. If the depths are different, then no buddy bucket exist./ if (bktDepth < myDirectory.DrtyDepth) return -1; / Otherwise find the address of any key / int shdAdr = MakeAddress(Keys[0], bktDepth); //Return the buddy address. return shdAdr ^ 1; } / Function that tries to combine the bucket with its buddy / int HashTableBucket::CombineAttempt() { int rslt; / Locate the buddy of the bucket. / int buddyBktInd = discoverBuddy(); / If buddy index is 0, then return. Because no bucket to combine./ if (buddyBktInd == -1) return 0; / Find the address of the buddy in the directory./ int buddyAddr = myDirectory.bktAddr[buddyBktInd]; / Create a temporay bucket./ HashTableBucket buddyBucket = new HashTableBucket(myDirectory, AllowedKeys); /* Load the buddy bucket into the temporary bucket./ myDirectory.GetBkt(buddyBucket, buddyAddr); / Check the buckets sizes. If the sum of buckets sizes are long then return./ if (cntKeys + buddyBucket->cntKeys > AllowedKeys) return 0; / Merge the buckets./ AttachBuckkets(buddyBucket, buddyBktInd); / Reduce the directory size / rslt = myDirectory.reduceSize(); / Recursive call to make a combine attempt if possible./ if (rslt) CombineAttempt(); return 1; } / Function that merges the bucket with its buddy/ int HashTableBucket::AttachBuckkets(HashTableBucket buddyBkt, int buddyBktInd) { int rslt; /* Loop to copy the keys of the buddy./ for (int aa = 0; aa < buddyBkt->cntKeys; aa++) { // Copy the keys from buddy to the bucket. rslt = InsertKyBucket(buddyBkt->Keys[aa], buddyBkt->RecordAddresses[aa]); //Check the result. If couldn’t copy,then return. if (!rslt) return 0; } / Decrease the bucket depth / bktDepth--; / Delete the buddy bucket from the directory./ myDirectory.DelBkt(buddyBktInd, bktDepth); //Return statement. return 1; } / Function to find the new domain for the split bucket/ int HashTableBucket::newDomain(int & newDomStart, int & newDomEnd) { int shrdAdr = MakeAddress(Keys[0], bktDepth); / Calculate the bits to fill the bucket./ int btsFill = myDirectory.DrtyDepth - (bktDepth + 1); / Calculate the starting and ending domain./ newDomStart = (shrdAdr << 1) | 1; newDomEnd = newDomStart; / Loop that find the start and end range./ for (int aa = 0; aa< btsFill; aa++) { / Calculate the start and end for the split bucket./ newDomStart = newDomStart << 1; newDomEnd = (newDomEnd << 1) | 1; } //Return statement. return 1; } / Function to reorganize the keys between bucket and the split bucket./ int HashTableBucket::reorganizeKeys(HashTableBucket & newSplitBkt) { / Loop to check each key in the bucket./ for (int aa = cntKeys - 1; aa >= 0; aa--) { / Get the bucket address of the key./ int bktAdr1 = myDirectory.locateKy(Keys[aa]); / Check the bucket address. If not then place the key into the new split bucket./ if (bktAdr1 != bktAddr) { / Insert a key into the new split bucket./ newSplitBkt.TxtInd::insertKy(Keys[aa], RecordAddresses[aa]); / Delete the key from the current bucket./ TxtInd::DelKy(Keys[aa]); } } //Return 1. return 1; } / Function to display the bucket content to the output stream./ ostream & HashTableBucket::displayBkt(ostream & outpStream) { / Display the bucket depth/ outpStream << "BUCKET DEPTH: " << bktDepth << endl; / Print the bucket./ TxtInd::displayTxtInd(outpStream); / Return the output stream./ return outpStream; } / Constructor that initializes the buffer for the bucket./ BktBuff::BktBuff(int kySize, int kysLimit) : TxtIndBuff(kySize, kysLimit, 1, sizeof(int)) { / Add the next field to the buffer./ addNxtFld(sizeof(int)); } / Set the next field for the buffer./ int BktBuff::SetNextField(const HashTableBucket & bkt) { int rslt; / Set the bucket./ rslt = TxtIndBuff::SetNextField(bkt); / If not set, then return./ if (rslt == -1) return -1; / Set the bucket depth/ return StandardFldBuff::SetNextField(&bkt.bktDepth); } / Function to unpack a bucket from the buffer./ int BktBuff::ExtractNextField(HashTableBucket & bkt) { int rslt; / Unpack the bucket./ rslt = TxtIndBuff::ExtractNextField(bkt); / Check bucket is unpacked. If not, return./ if (rslt == -1) return -1; / Unpack the bucket depth./ return StandardFldBuff::ExtractNextField(&bkt.bktDepth); } //main() method int main() { / Declare variables / int reslt; char deleteKey[20]; char searchKey[20]; / Create objects / hashTableDirectory myDirectory(4); / Create directory / reslt = myDirectory.CreateDirectory("tsthash"); / Declare keys to insert into the directory / char kys[] = { "David","Jerry","Tom","Mike" }; const int kysCnt = 4; //Loop to insert the keys into the directory / for (int i = 0; i<="" p="" style="box-sizing: border-box;"> { /Call hashTableDirectory method to insert the keys into the directory./ reslt = myDirectory.InsertKyDirectory(kys[i], MakeAddress(kys[i], 16)); } / Insert the keys into the directory / reslt = myDirectory.InsertKyDirectory("uma", MakeAddress("uma", 16)); reslt = myDirectory.InsertKyDirectory("abi", MakeAddress("abi", 16)); //Display the directory content. cout << "DIRECTORY CONTENT:" << endl; myDirectory.displayDirectory(cout); cout << "ENTER KEY TO DELETE:" << endl; cin >> deleteKey; /Delete the key. / reslt = myDirectory.delKyDirectory(deleteKey); / Check key is deleted and display appropriate messages. / if (reslt == 0) cout << "Key not present" << endl; //Otherwise, display key deleted successfully / else cout << "Key deleted Successfully" << endl; /* Get key to search in the directory. / cout << "Enter the key to search:" << endl; cin > searchKey; / Call method to locate the given key. / reslt = myDirectory.locateKy(searchKey); / Check key is present. If not then display message./ if (!reslt) cout << "Key not present" << endl; //Otherwise, display key is in the directory. / else cout << "Key present in the directory" << endl; /* Display the directory after deletion. / myDirectory.displayDirectory(cout); / Pause the console window. */ system("pause"); return 1; } Output: DIRECTORY CONTENT: Directory Depth 1 size 2 bucket 68 addr 00000000 BUCKET DEPTH: 1 MAXKEYS: 4 NUMKEYS:3 KEY[0] Jerry RECORDADDRESS 21972 KEY[1] Mike RECORDADDRESS 29970 KEY[2] uma RECORDADDRESS 9312 bucket 140 addr 00000001 BUCKET DEPTH: 1 MAXKEYS: 4 NUMKEYS:3 KEY[0] David RECORDADDRESS 34116 KEY[1] Tom RECORDADDRESS 52178 KEY[2] abi RECORDADDRESS 38528 DIRECTORY END. ENTER KEY TO DELETE: ABI Key not present Enter the key to search: abi Key present in the directory Directory Depth 1 size 2 bucket 68 addr 00000000 BUCKET DEPTH: 1 MAXKEYS: 4 NUMKEYS:3 KEY[0] Jerry RECORDADDRESS 21972 KEY[1] Mike RECORDADDRESS 29970 KEY[2] uma RECORDADDRESS 9312 bucket 140 addr 00000001 BUCKET DEPTH: 1 MAXKEYS: 4 NUMKEYS:3 KEY[0] David RECORDADDRESS 34116 KEY[1] Tom RECORDADDRESS 52178 KEY[2] abi RECORDADDRESS 38528 DIRECTORY END. Sample output file: tsthash.bkt: tsthash.dir: Explanation: Above provided code is used to insert the records in a file and after that all the content are retrieved and delted by using the various hashing techniques as shown in the above output.

EBK DATA STRUCTURES AND ALGORITHMS IN C

4th Edition

ISBN: 9781285415017

Author: DROZDEK

Publisher: YUZU

See similar textbooks

Concept explainers

Fundamentals of blockchaining

In a business network, the tracking assets and the process of recording transactions are facilitated by the shared immutable ledger called a blockchain. Assets are of two types they are tangible and intangible. The tangible assets are land, house, cash, …

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 10, Problem 2PA

Chapter 10, Problem 4PA

Students have asked these similar questions

Dijkstra's Algorithm (part 1). Consider the network shown below, and Dijkstra’s link-state algorithm. Here, we are interested in computing the least cost path from node E (note: the start node here is E) to all other nodes using Dijkstra's algorithm. Using the algorithm statement used in the textbook and its visual representation, complete the "Step 0" row in the table below showing the link state algorithm’s execution by matching the table entries (i), (ii), (iii), and (iv) with their values. Write down your final [correct] answer, as you‘ll need it for the next question.

4. |z + 5 - 5i| = 7

14. dz, C: |z❘ C: |z❘ = 0.6 ze² - 2iz H

Chapter 10 Solutions

EBK DATA STRUCTURES AND ALGORITHMS IN C

Ch. 10 - Prob. 7E Ch. 10 - Prob. 10E Ch. 10 - Prob. 2PA Ch. 10 - Prob. 3PA Ch. 10 - Prob. 4PA

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.