Binary search 이용한 file indexing

file indexing이라기보단 file 내 offset indexing이라고 해야되나..

#include <iostream>

#include<string.h>

#include<fstream>

#include<vector>

using namespace std;

#define DEFAULT_RECORD_SIZE 128

#define DEFAULT_RECORD_CNT 32

#define INVALID_BLOCK_NUMBER -1

#define KEY_SIZE 10

struct DATA{

char dump[128];

};

class Block{

private:

class Header{

public:

typedef struct key_rrn{

int rrn;

char key[KEY_SIZE]; //name field

}KR;

private:

///File format fields

unsigned block_num; //현재 블럭 넘버

int record_sz; //한 레코드 사이즈

int record_cnt; //현재 저장된 레코드 개수

int max_record_cnt; //최대 저장 레코드 수

KR *KRs; //key-rrn array

int *avRRNs; //available RRN정보. stack 형태

int avRRNs_cnt; //가용 RRN배열에 들어있는 데이터 갯수

public:

//공간 할당 없이 초기화

Header(){

block_num = INVALID_BLOCK_NUMBER;

record_sz = 0;

record_cnt = 0;

max_record_cnt = 0;

KRs = NULL;

avRRNs = NULL;

avRRNs_cnt = 0;

}

//헤더에 공간을 할당하며 초기화함

Header(unsigned blockNumber, int maxRecordCount, int recordSize=DEFAULT_RECORD_SIZE){

block_num = blockNumber;

record_sz = recordSize;

record_cnt = 0;

max_record_cnt = maxRecordCount;

KRs = new KR[max_record_cnt];

memset((void*)(KRs), 0x00, sizeof(KRs));

avRRNs = new int[max_record_cnt];

for(int i=0; i<max_record_cnt; i++)

avRRNs[i] = i;

avRRNs_cnt = max_record_cnt;

}

unsigned getBlockNumber(){ return block_num; }

int getRecordSize(){ return record_sz; }

int getRecordCount(){ return record_cnt; }

int getMaxRecordCount(){ return max_record_cnt; }

bool hasData(){

if(KRs == NULL && avRRNs == NULL)

return false;

return true;

}

int getHeaderSize(){

return sizeof(block_num)+sizeof(record_sz)+sizeof(record_cnt)+sizeof(max_record_cnt)

+sizeof(KR)*max_record_cnt+sizeof(int)*max_record_cnt+sizeof(avRRNs_cnt);

}

//operation

private:

int popAvailableRRN(){ 

if(avRRNs_cnt == 0)

return -1;

avRRNs_cnt--;

return avRRNs[avRRNs_cnt];

}

void pushAvailableRRN(int returned){

if(avRRNs_cnt == max_record_cnt)

return;

avRRNs[avRRNs_cnt] = returned;

avRRNs_cnt++;

}

//swapping

inline void swap(KR& a, KR& b){

KR t;

memcpy(&t, &a, sizeof(KR));

memcpy(&a, &b, sizeof(KR));

memcpy(&b, &t, sizeof(KR));

}

//inplace insertion sort for sorting h.KRs array (I think insertion sort is better than quick sort..)

void krSort(){

if(KRs==NULL)

return;

int i, j;

KR tmp;

for(i=1; i<record_cnt; i++){

memcpy(&tmp, &KRs[i], sizeof(KR));

for(j=i-1; j>=0; j--){

if(strcmp(KRs[j].key,tmp.key) >0)

memcpy(&KRs[j+1], &KRs[j], sizeof(KR));

else

break;

}

memcpy(&KRs[j+1], &tmp, sizeof(KR));

}

}

//binary search and return the matched KR's index

int searchIdx(const char* key){

if(KRs==NULL)

return -1;

int fidx=0, lidx=record_cnt-1;

int mid=0;

bool isFound = false;

while(!isFound){

if(fidx > lidx)

break;

mid = static_cast<int>((fidx+lidx)/2);

if( strncmp(KRs[mid].key, key, KEY_SIZE)==0){

isFound = true;

}

else if(strncmp(KRs[mid].key, key, KEY_SIZE) > 0){

lidx = mid-1;

}

else{

fidx = mid+1;

}

}//end while

if(isFound)

return mid;

else

return -1;

}

public:

//return RRN. return -1 when failed

int Search(const char*key){

int idx = searchIdx(key);

if(idx==-1)

return -1;

return KRs[idx].rrn;

}

//insert a Key and return the matched rrn, and sorting. Data is not inserted, just increse offset info

int Insert(const char* key){

if(KRs==NULL  ||  record_cnt >= max_record_cnt)

return -1;

int avrrn = popAvailableRRN();

KRs[record_cnt].rrn = avrrn;

strncpy(KRs[record_cnt].key, key, KEY_SIZE);

record_cnt++;

krSort();

return avrrn;

}

//delete index info by key. return deleted RRN matched inupt key

int Delete(const char* key){

if(KRs==NULL  ||  record_cnt <= 0)

return -1;

int idx = searchIdx(key);

if(idx == -1)

return -1;

int rrn = KRs[idx].rrn;

record_cnt--;

swap(KRs[idx], KRs[record_cnt]);//마지막 KR정보를 지워진 공간으로 이동

memset((void*)(&KRs[record_cnt+1]), 0x00, sizeof(KR));

krSort();

//사용 가능해진 rrn(방금지운) avRRNs에 삽입

pushAvailableRRN(rrn);

return rrn;

}

//file operations

//성공:헤더가 쓰여진 마지막 위치. 실패시 -1리턴

bool  writeHeader(fstream& fs){

if(KRs==NULL  ||  avRRNs==NULL  ||  fs.is_open() == false)

return false;

fs.write((const char*)(&block_num), sizeof(unsigned));

fs.write((const char*)(&record_sz), sizeof(int));

fs.write((const char*)(&record_cnt), sizeof(int));

fs.write((const char*)(&max_record_cnt), sizeof(int));

fs.write((const char*)(KRs), sizeof(KR)*max_record_cnt );

fs.write((const char*)(avRRNs), sizeof(int)*max_record_cnt);

fs.write((const char*)(&avRRNs_cnt), sizeof(int));

return true;

}

bool readHeader(fstream& fs){

if(fs.is_open() == false)

return false;

fs.read((char*)(&block_num), sizeof(unsigned));

fs.read((char*)(&record_sz), sizeof(int));

fs.read((char*)(&record_cnt), sizeof(int));

fs.read((char*)(&max_record_cnt), sizeof(int));

if(KRs != NULL)

delete [] KRs;

KRs = new KR[max_record_cnt];

fs.read((char*)(KRs), sizeof(KR)*max_record_cnt);

if(avRRNs !=NULL)

delete [] avRRNs;

avRRNs = new int[max_record_cnt];

fs.read((char*)(avRRNs), sizeof(int)*max_record_cnt);

fs.read((char*)(&avRRNs_cnt), sizeof(int));

return true;

}

};

class Record{

private:

///File format fields

int RRN;

char Key[KEY_SIZE];

DATA data;

public:

Record(int rrn = -1){

RRN = rrn;

memset(Key, 0x00, sizeof(Key));

memset(&data, 0x00, sizeof(data));

}

Record(int rrn, const char* key, DATA& _data){

RRN = rrn;

strncpy(Key, key, sizeof(Key));

memcpy(&data, &_data, sizeof(DATA));

}

//get sets..

int getRRN(){ return RRN; }

const char* getKey(){ return Key; }

DATA getData(){ return data; }

//insert data operations...

//file operations..

bool writeRecord(fstream& fs){

if(fs.is_open()==false)

return false;

fs.write((const char*)(&RRN), sizeof(RRN));

fs.write((const char*)(Key), sizeof(Key));

fs.write((const char*)(&data), sizeof(DATA));

return true;

}

bool readRecord(fstream& fs){

if(fs.is_open()==false)

return false;

fs.read((char*)(&RRN), sizeof(RRN));

fs.read((char*)(Key), sizeof(Key));

fs.read((char*)(&data), sizeof(DATA));

return true;

}

};

protected:

///File format fields

Header head;

///Block class member fields

int record_cnt;

int record_offset; //record data start offset

fstream fs;

public:

Block()

: head(), fs()

{

record_cnt = 0;

record_offset = 0;

}

Block(unsigned blockNumber, int recordCount = DEFAULT_RECORD_CNT)

: head(blockNumber, recordCount, sizeof(Record)), fs()

{

record_cnt = recordCount;

record_offset = head.getHeaderSize();

}

//get sets..

//get header info

unsigned getBlockNumber(){ return head.getBlockNumber(); }

int getCurrentRecordCount(){ return head.getRecordCount(); }

int getRecordSize(){ return head.getRecordSize(); }

int getMaxRecordcount(){ return head.getMaxRecordCount(); }

//block operations..

private:

bool readHeader(){

if(fs.is_open()==false)

return false;

fs.seekg(0, ios::beg);

return head.readHeader(fs);

}

bool writeHeader(){

if(fs.is_open() == false)

return false;

fs.seekp(0, ios::beg);

return head.writeHeader(fs);

}

public:

//open filestream.

bool openFileStream(const char* FileName, bool newFile=false){

if(newFile){

fs.open(FileName, ios::in|ios::out|ios::trunc);

if(fs.is_open()==false)

return false;

}

else{

fs.open(FileName, ios::in|ios::out|ios::_Nocreate);

if(fs.is_open()==false)

return false;

if( this->readHeader() == false)

return false;

record_offset = head.getHeaderSize();

}

return true;

}

//close filestream. 

bool closeFileStream(){

if(writeHeader() == false)

return false;

fs.close();

return true;

}

//search record

bool searchRecord(const char* key, DATA& data_buf, int& rrn_buf){

if(fs.is_open() == false)

return false;

int rrn=head.Search(key);

if(rrn == -1)

return false;

Record tmp;

fs.seekg(0,ios::cur); //여기서 이렇게 seekg를 호출하지 않으면 아래 seekg가 제대로 되지 않습니다.

//이유는 모르겠습니다..

fs.seekg(record_offset+(rrn*head.getRecordSize()), ios::beg);

if( tmp.readRecord(fs) == false)

return false;

data_buf = tmp.getData();

rrn_buf = tmp.getRRN();

return true;

}

bool insertRecord(const char* key, DATA& data){

if(fs.is_open()==false)

return false;

int rrn = head.Insert(key);

if(rrn == -1)

return false;

Record rtmp(rrn, key, data);

fs.seekp(record_offset+(rrn*head.getRecordSize()),ios::beg);

return rtmp.writeRecord(fs);

}

bool updateRecord(const char* originKey, const char* newKey, DATA& data){

if(fs.is_open()==false)

return false;

int rrn = head.Search(originKey);

if(rrn == -1)

return false;

fs.seekp(record_offset+(rrn*head.getRecordSize()), ios::beg);

Record rtmp(rrn, newKey, data);

return rtmp.writeRecord(fs);

}

bool deleteRecord(const char* key){

if(fs.is_open()==false)

return false;

int rrn = head.Delete(key);

if(rrn == -1)

return false;

fs.seekp(record_offset+(rrn*head.getRecordSize()), ios::beg);

Record rtmp;

return rtmp.writeRecord(fs);

}

~Block(){

writeHeader();

}

};