aboutsummaryrefslogtreecommitdiff
path: root/Src/nde/Index.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'Src/nde/Index.cpp')
-rw-r--r--Src/nde/Index.cpp787
1 files changed, 787 insertions, 0 deletions
diff --git a/Src/nde/Index.cpp b/Src/nde/Index.cpp
new file mode 100644
index 00000000..83fe9097
--- /dev/null
+++ b/Src/nde/Index.cpp
@@ -0,0 +1,787 @@
+/* ---------------------------------------------------------------------------
+Nullsoft Database Engine
+--------------------
+codename: Near Death Experience
+--------------------------------------------------------------------------- */
+
+/* ---------------------------------------------------------------------------
+
+Raw Index Class
+
+--------------------------------------------------------------------------- */
+
+#include "nde.h"
+#include <stdio.h>
+
+
+const char *iSign="NDEINDEX";
+
+//---------------------------------------------------------------------------
+Index::Index(VFILE *H, unsigned char id, int pos, int type, bool newindex, int nentries, Table *parentTable)
+{
+ Handle = H;
+ IndexTable = NULL;
+ MaxSize=0;
+ locateUpToDate = false;
+ Id = id;
+ Position = pos;
+// DataType = type;
+ SecIndex = NULL;
+ InChain=false;
+ InInsert=false;
+ InChainIdx = -1;
+ pTable = parentTable;
+ TableHandle = pTable->Handle;
+ SetGlobalLocateUpToDate(false);
+
+ if (!newindex)
+ {
+ Vfseek(Handle, (int)strlen(__INDEX_SIGNATURE__), SEEK_SET);
+ Vfread(&NEntries, sizeof(NEntries), Handle);
+ }
+ else
+ NEntries = nentries;
+ LoadIndex(newindex);
+}
+
+//---------------------------------------------------------------------------
+Index::~Index()
+{
+ if (IndexTable)
+ free(IndexTable);
+}
+
+//---------------------------------------------------------------------------
+int Index::Insert(int N)
+{
+ return Insert(NULL, N, false);
+}
+
+//---------------------------------------------------------------------------
+int Index::Insert(Index *parindex, int N, bool localonly)
+{
+ if (InChain) return -1;
+ Index *p = parindex;
+ IndexField *f = 0;
+ locateUpToDate = false;
+ SetGlobalLocateUpToDate(false);
+ InInsert=true;
+ if (N > NEntries) N = NEntries;
+ if ((NEntries+1) > (int)MaxSize)
+ {
+ MaxSize *=2;//+= BLOCK_SIZE;
+ int *newBlock = (int *)calloc(MaxSize, sizeof(int)*2);
+ memcpy(newBlock, IndexTable, NEntries*sizeof(int)*2);
+ free(IndexTable);
+ IndexTable = newBlock;
+ }
+
+ if (N < NEntries && Id == PRIMARY_INDEX)
+ {
+ memmove(IndexTable+(N+1)*2, IndexTable+(N*2), (NEntries-N)*sizeof(int)*2);
+ NEntries++;
+ }
+ else
+ {
+ N=NEntries;
+ NEntries++;
+ }
+
+ Update(N, 0, NULL, localonly);
+
+ // Should be always safe to cat the new record since if we are primary index,
+ // then secondary is sorted, so value will be moved at update
+ // if we are a secondary index, then an insertion will insert at the end of the primary index anyway
+ if (!localonly && SecIndex)
+ {
+ InChain=true;
+ int pp = SecIndex->index->Insert(this, N, false);
+ InChain=false;
+ IndexTable[N*2+1] = pp == -1 ? N : pp;
+ if (N < NEntries-1 && Id == PRIMARY_INDEX)
+ {
+ int pidx = -1;
+ if (!parindex)
+ {
+ int v = pp;
+ f = SecIndex;
+ if (f)
+ {
+ while (f->index->SecIndex->index != this)
+ {
+ v = f->index->GetCooperative(v);
+ f = f->index->SecIndex;
+ }
+ p = f->index;
+ pidx = v;
+ }
+ }
+ if (p && pidx != -1)
+ {
+ p->SetCooperative(pidx, N);
+ UpdateMe(p, N, NEntries);
+ }
+ }
+ }
+
+ InInsert=false;
+ return N;
+}
+
+//---------------------------------------------------------------------------
+void Index::LoadIndex(bool newindex)
+{
+ if (IndexTable)
+ free(IndexTable);
+ MaxSize = ((NEntries) / BLOCK_SIZE + 1) * BLOCK_SIZE;
+ IndexTable = (int *)calloc(MaxSize, sizeof(int)*2);
+ if (!newindex)
+ {
+ Vfseek(Handle, (int)strlen(__INDEX_SIGNATURE__)+4+((NEntries*4*2)+4)*(Position+1), SEEK_SET);
+ int v = 0;
+ Vfread(&v, sizeof(v), Handle);
+ Id = (unsigned char)v;
+ Vfread(IndexTable, NEntries*2*sizeof(int), Handle);
+ }
+}
+
+//---------------------------------------------------------------------------
+int Index::Update(int Idx, int Pos, RecordBase *record, bool localonly)
+{
+ return Update(NULL, -1, Idx, Pos, record, false, localonly);
+}
+
+//---------------------------------------------------------------------------
+int Index::Update(Index *parindex, int paridx, int Idx, int Pos, RecordBase *record, bool forceLast, bool localonly)
+{
+ if (InChain) return InChainIdx;
+ int NewIdx=Idx;
+ int oldSecPtr = IndexTable[Idx*2+1];
+ if (!forceLast && Id == PRIMARY_INDEX || record == NULL || Idx < NUM_SPECIAL_RECORDS)
+ {
+ if (Idx < NEntries && Idx >= 0)
+ {
+ IndexTable[Idx*2] = Pos;
+ if (!localonly && SecIndex && SecIndex->index != this && !InInsert)
+ {
+ InChain=true;
+ InChainIdx = Idx;
+ SecIndex->index->Update(this, Idx, IndexTable[Idx*2+1], Pos, record, forceLast, false);
+ InChainIdx = -1;
+ InChain=false;
+ }
+ }
+ else
+ {
+#ifdef WIN32
+ MessageBox(NULL, L"Updating outside range", L"Oops", 16);
+#else
+ printf("NDE Error: updating outside range!\n");
+#endif
+ }
+ }
+ else
+ {
+ if (forceLast)
+ NewIdx = NEntries;
+ else
+ {
+ if (Pos != Get(Idx) || Id != PRIMARY_INDEX)
+ {
+ int state = 0;
+ NewIdx = FindSortedPlace(record->GetField(Id), Idx, &state, QFIND_ENTIRE_SCOPE);
+ }
+ }
+
+ if (NewIdx <= NEntries && NewIdx >= NUM_SPECIAL_RECORDS)
+ {
+ if (NewIdx != Idx)
+ {
+ Index *p = parindex;
+ IndexField *f = 0;
+ int pidx = paridx;
+ NewIdx = MoveIndex(Idx, NewIdx);
+ if (SecIndex->index != this)
+ {
+ if (!parindex)
+ {
+ int v = GetCooperative(NewIdx);
+ f = SecIndex;
+ if (f)
+ {
+ while (f->index->SecIndex->index != this)
+ {
+ v = f->index->GetCooperative(v);
+ f = f->index->SecIndex;
+ }
+ p = f->index;
+ pidx = v;
+ }
+ }
+ if (p)
+ {
+ p->SetCooperative(pidx, NewIdx);
+ UpdateMe(p, NewIdx, Idx);
+ }
+ }
+ }
+ IndexTable[NewIdx*2] = Pos;
+ if (!localonly && SecIndex && SecIndex->index != this && !InInsert) // Actually, we should never be InInsert and here, but lets cover our ass
+ {
+ InChain=true;
+ InChainIdx = oldSecPtr;
+ SecIndex->index->Update(this, NewIdx, oldSecPtr, Pos, record, forceLast, false);
+ InChainIdx = -1;
+ InChain=false;
+ }
+ }
+ else
+ {
+#ifdef WIN32
+ MessageBox(NULL, L"QSort failed and tried to update index outside range", L"Oops", 16);
+#else
+ printf("NDE Error: qsort failed and tried to update index outside range!\n");
+#endif
+ }
+ }
+ locateUpToDate = false;
+ SetGlobalLocateUpToDate(false);
+ pTable->IndexModified();
+ return NewIdx;
+}
+
+//---------------------------------------------------------------------------
+int Index::Get(int Idx)
+{
+ if (Idx < NEntries)
+ return IndexTable[Idx*2];
+ else
+ {
+#ifdef WIN32
+ MessageBox(NULL, L"Requested index outside range", L"Oops", 16);
+#else
+ printf("NDE Error: requested index outside range!\n");
+#endif
+ return -1;
+ }
+}
+
+//---------------------------------------------------------------------------
+void Index::Set(int Idx, int P)
+{
+ if (Idx < NEntries)
+ IndexTable[Idx*2]=P;
+ else
+ {
+#ifdef WIN32
+ MessageBox(NULL, L"Updating index outside range", L"Oops", 16);
+#else
+ printf("NDE Error: updating index outside range!\n");
+#endif
+ }
+}
+
+//---------------------------------------------------------------------------
+void Index::WriteIndex(void)
+{
+ if (Id == PRIMARY_INDEX)
+ {
+ Vfseek(Handle, (int)strlen(__INDEX_SIGNATURE__), SEEK_SET);
+ Vfwrite(&NEntries, sizeof(NEntries), Handle);
+ }
+ Vfseek(Handle, (int)strlen(__INDEX_SIGNATURE__)+4+((NEntries*4*2)+4)*(Position+1), SEEK_SET);
+ int v=(int)Id;
+ Vfwrite(&v, sizeof(v), Handle);
+ Vfwrite(IndexTable, NEntries*2*sizeof(int), Handle);
+}
+
+//---------------------------------------------------------------------------
+int Index::MoveIndex(int idx, int newidx)
+{
+ if (idx == newidx)
+ return newidx;
+ int oldPos=IndexTable[idx*2], oldPtr=IndexTable[idx*2+1];
+
+ if (NEntries > idx+1)
+ memmove(IndexTable+idx*2, IndexTable+(idx+1)*2, (NEntries-idx)*sizeof(int)*2);
+ if (newidx > idx)
+ newidx--;
+ if (NEntries > newidx)
+ memmove(IndexTable+(newidx+1)*2, IndexTable+newidx*2, (NEntries-newidx-1)*sizeof(int)*2);
+ IndexTable[newidx*2] = oldPos;
+ IndexTable[newidx*2+1] = oldPtr;
+ return newidx;
+}
+
+//---------------------------------------------------------------------------
+void Index::Colaborate(IndexField *secindex)
+{
+ SecIndex = secindex;
+ for (int i=0;i<NUM_SPECIAL_RECORDS;i++)
+ /*secindex->index->*/SetCooperative(i, i);
+
+}
+
+//---------------------------------------------------------------------------
+void Index::Propagate(void)
+{
+ int i;
+
+ if (!SecIndex || SecIndex->ID == PRIMARY_INDEX) return;
+ SecIndex->index->NEntries=NUM_SPECIAL_RECORDS;
+ for (i=0;i<NUM_SPECIAL_RECORDS;i++)
+ {
+ SecIndex->index->Set(i, Get(i));
+ SecIndex->index->SetCooperative(i, GetCooperative(i));
+ }
+
+ Scanner *s = pTable->NewScanner();
+ if (!s)
+ {
+#ifdef WIN32
+ MessageBox(NULL, L"Failed to create a scanner in reindex", L"Oops", 16);
+#else
+ printf("NDE Error: failed to create a scanner in reindex!\n");
+#endif
+ return;
+ }
+
+ int *coopSave = (int *)calloc(NEntries, sizeof(int));
+ if (!coopSave)
+ {
+#ifdef WIN32
+ MessageBox(NULL, L"Alloc failed in reindex", L"Oops", 16);
+#else
+ printf("NDE Error: alloc failed in reindex!\n");
+#endif
+ return;
+ }
+
+ for (i=0;i<NEntries;i++)
+ {
+ coopSave[i] = GetCooperative(i);
+ SetCooperative(i, i);
+ }
+
+ if (SecIndex->index->SecIndex->index->Id != PRIMARY_INDEX)
+ {
+#ifdef WIN32
+ MessageBox(NULL, L"Propagating existing index", L"Oops", 16);
+#else
+ printf("NDE Error: propagating existing index!\n");
+#endif
+ free(coopSave);
+ return;
+ }
+
+ s->SetWorkingIndexById(-1);
+
+ for (i=NUM_SPECIAL_RECORDS;i<NEntries;i++)
+ {
+ Record *rec = s->GetRecord(coopSave[i]);
+ if (rec)
+ {
+ SecIndex->index->NEntries++;
+ // SecIndex->index->Insert(NULL, i, true);
+ SecIndex->index->SetCooperative(i, coopSave[i]);
+ SecIndex->index->Set(i, Get(i));
+ SecIndex->index->Update(i, SecIndex->index->Get(i), rec, true);
+ /* SecIndex->index->SetCooperative(i, q);*/
+ rec->Release();
+ }
+ else
+ {
+#ifdef WIN32
+ MessageBox(NULL, L"Unable to read record in reindex", L"Oops", 16);
+#else
+ printf("NDE Error: unable to read record in reindex!\n");
+#endif
+ }
+ }
+
+ free(coopSave);
+
+ if (NEntries != SecIndex->index->NEntries) {
+#ifdef WIN32
+ MessageBox(NULL, L"Secindex->NEntries desynchronized in reindex", L"Oops", 16);
+#else
+ printf("NDE Error: Secindex->NEntries desynchronized in reindex!\n");
+#endif
+ }
+
+ pTable->DeleteScanner(s);
+}
+
+//---------------------------------------------------------------------------
+void Index::SetCooperative(int Idx, int secpos)
+{
+ if (Idx < NEntries && Idx >= 0)
+ IndexTable[Idx*2+1] = secpos;
+ else
+ {
+#ifdef WIN32
+ MessageBox(NULL, L"Cooperative update outside range", L"Oops", 16);
+#else
+ printf("NDE Error: cooperative update outside range!\n");
+#endif
+ }
+}
+
+//---------------------------------------------------------------------------
+int Index::GetCooperative(int Idx)
+{
+ if (Idx < NEntries && Idx >= 0)
+ return IndexTable[Idx*2+1];
+ else
+ {
+#ifdef WIN32
+ MessageBox(NULL, L"Cooperative request outside range", L"Oops", 16);
+#else
+ printf("NDE Error: cooperative request outside range!\n");
+#endif
+ }
+ return -1;
+}
+
+//---------------------------------------------------------------------------
+int Index::NeedFix() {
+ for (int i=NUM_SPECIAL_RECORDS;i<NEntries;i++) {
+ if (IndexTable[i*2+1] <= 0) return 1;
+ }
+ return 0;
+}
+
+//---------------------------------------------------------------------------
+void Index::UpdateMe(Index *Me, int NewIdx, int OldIdx)
+{
+ int j=NewIdx > OldIdx ? -1 : 1;
+ for (int i=min(NewIdx, OldIdx);i<=max(NewIdx, OldIdx)&&i<NEntries;i++)
+ {
+ if (i == NewIdx) continue;
+ int v = GetCooperative(i);
+ IndexField *f = SecIndex;
+ while (f->index->SecIndex->index != this)
+ {
+ v = f->index->GetCooperative(v);
+ f = f->index->SecIndex;
+ }
+ Me->SetCooperative(v, Me->GetCooperative(v)+j);
+ }
+}
+
+//---------------------------------------------------------------------------
+Field *Index::QuickFindField(unsigned char Idx, int Pos)
+{
+ int ThisPos = Pos;
+
+ while (ThisPos)
+ {
+ Vfseek(TableHandle, ThisPos, SEEK_SET);
+ Field entry(ThisPos);
+ uint32_t next_pos;
+ entry.ReadField(pTable, ThisPos, true, &next_pos);
+ if (entry.GetFieldId() == Idx)
+ {
+ return entry.ReadField(pTable, ThisPos);
+ }
+ ThisPos = next_pos;
+ }
+ return NULL;
+}
+
+//---------------------------------------------------------------------------
+// Dynamic qsort (i definitly rule)
+int Index::FindSortedPlace(Field *thisField, int curIdx, int *laststate, int start)
+{
+ return FindSortedPlaceEx(thisField, curIdx, laststate, start, COMPARE_MODE_EXACT);
+}
+
+//---------------------------------------------------------------------------
+// and here again ugly switch
+int Index::FindSortedPlaceEx(Field *thisField, int curIdx, int *laststate, int start, int comp_mode)
+{
+ int top=start != QFIND_ENTIRE_SCOPE ? start : NUM_SPECIAL_RECORDS;
+ int bottom=NEntries-1;
+ int compEntry = 0;
+ int cePos = 0;
+ Field *compField=NULL;
+ int i = 0;
+ Field *cfV=NULL;
+
+ if (NEntries <= NUM_SPECIAL_RECORDS) return NUM_SPECIAL_RECORDS;
+ switch(comp_mode)
+ {
+ case COMPARE_MODE_EXACT:
+ while (bottom-top >= 1)
+ {
+ compEntry=(bottom-top)/2+top;
+ if (compEntry == curIdx) compEntry++;
+ if (compEntry == bottom) break;
+ cePos = Get(compEntry);
+ if (!cePos) bottom = compEntry;
+ else
+ {
+ compField = QuickFindField(Id, Get(compEntry));
+ cfV = compField;
+ if (!thisField)
+ {
+ if (!compField) i = 0;
+ else i = 1;
+ }
+ else i = thisField->Compare(cfV);
+ switch (i)
+ {
+ case 1:
+ top = compEntry+1;
+ break;
+ case -1:
+ bottom = compEntry-1;
+ break;
+ case 0:
+ *laststate=0;
+ delete compField;
+ return compEntry+1;
+ }
+ delete compField;
+ }
+ }
+ compEntry=(bottom-top)/2+top;
+ if (compEntry == curIdx) return curIdx;
+ compField = QuickFindField(Id, Get(compEntry));
+ cfV = compField;
+ if (thisField) *laststate = thisField->Compare(cfV);
+ else
+ {
+ if (!compField) *laststate = 0;
+ else *laststate = 1;
+ }
+ break;
+
+ case COMPARE_MODE_CONTAINS:
+ while (bottom-top >= 1)
+ {
+ compEntry=(bottom-top)/2+top;
+ if (compEntry == curIdx) compEntry++;
+ if (compEntry == bottom) break;
+ cePos = Get(compEntry);
+ if (!cePos) bottom = compEntry;
+ else
+ {
+ compField = QuickFindField(Id, Get(compEntry));
+ cfV = compField;
+ if (!thisField)
+ {
+ if (!compField) i = 0;
+ else i = 1;
+ }
+ else i = thisField->Contains(cfV);
+ switch (i)
+ {
+ case 1:
+ top = compEntry+1;
+ break;
+ case -1:
+ bottom = compEntry-1;
+ break;
+ case 0:
+ *laststate=0;
+ delete compField;
+ return compEntry+1;
+ }
+ if (compField)
+ {
+ delete compField;
+ }
+ }
+ }
+ compEntry=(bottom-top)/2+top;
+ if (compEntry == curIdx) return curIdx;
+ compField = QuickFindField(Id, Get(compEntry));
+ cfV = compField;
+ if (thisField) *laststate = thisField->Contains(cfV);
+ else
+ {
+ if (!compField) *laststate = 0;
+ else *laststate = 1;
+ }
+ break;
+
+ case COMPARE_MODE_STARTS:
+ while (bottom-top >= 1)
+ {
+ compEntry=(bottom-top)/2+top;
+ if (compEntry == curIdx) compEntry++;
+ if (compEntry == bottom) break;
+ cePos = Get(compEntry);
+ if (!cePos) bottom = compEntry;
+ else
+ {
+ compField = QuickFindField(Id, Get(compEntry));
+ cfV = compField;
+ if (!thisField)
+ {
+ if (!compField) i = 0;
+ else i = 1;
+ }
+ else i = thisField->Starts(cfV);
+ switch (i)
+ {
+ case 1:
+ top = compEntry+1;
+ break;
+ case -1:
+ bottom = compEntry-1;
+ break;
+ case 0:
+ *laststate=0;
+ delete compField;
+ return compEntry+1;
+ }
+ if (compField)
+ {
+ delete compField;
+ }
+ }
+ }
+ compEntry=(bottom-top)/2+top;
+ if (compEntry == curIdx) return curIdx;
+ compField = QuickFindField(Id, Get(compEntry));
+ cfV = compField;
+ if (thisField) *laststate = thisField->Starts(cfV);
+ else
+ {
+ if (!compField) *laststate = 0;
+ else *laststate = 1;
+ }
+ break;
+ }
+
+ switch (*laststate)
+ {
+ case -1:
+ delete compField;
+ return compEntry;
+ case 1:
+ case 0:
+ delete compField;
+ return /*compEntry==NEntries-1 ? compEntry : */compEntry+1;
+ }
+ return NUM_SPECIAL_RECORDS; // we're not supposed to be here :/
+}
+
+int Index::QuickFind(int Id, Field *field, int start)
+{
+ return QuickFindEx(Id, field, start, COMPARE_MODE_EXACT);
+}
+
+//---------------------------------------------------------------------------
+int Index::QuickFindEx(int Id, Field *field, int start, int comp_mode)
+{
+ int laststate = 0;
+ Field *compField=NULL, *cfV=NULL;
+ int i = FindSortedPlaceEx(field, Id, &laststate, start, comp_mode)-1; // -1 because we don't insert but just search
+ if (laststate != 0)
+ return FIELD_NOT_FOUND;
+ if (i < start)
+ return FIELD_NOT_FOUND;
+
+ switch(comp_mode)
+ {
+ case COMPARE_MODE_CONTAINS:
+ while (--i>=NUM_SPECIAL_RECORDS)
+ {
+ compField = QuickFindField(Id, Get(i));
+ cfV = compField;
+ if (field->Contains(cfV) != 0)
+ {
+ if (compField)
+ {
+ delete compField;
+ }
+ return i+1;
+ }
+ if (compField)
+ {
+ delete compField;
+ }
+ }
+ break;
+ case COMPARE_MODE_EXACT:
+ while (--i>=NUM_SPECIAL_RECORDS)
+ {
+ compField = QuickFindField(Id, Get(i));
+ cfV = compField;
+ if (field->Compare(cfV) != 0)
+ {
+ if (compField)
+ {
+ delete compField;
+ }
+ return i+1;
+ }
+ if (compField)
+ {
+ delete compField;
+ }
+ }
+ break;
+ case COMPARE_MODE_STARTS:
+ while (--i>=NUM_SPECIAL_RECORDS)
+ {
+ compField = QuickFindField(Id, Get(i));
+ cfV = compField;
+ if (field->Starts(cfV) != 0)
+ {
+ delete compField;
+ return i+1;
+ }
+ delete compField;
+ }
+ break;
+ }
+
+ return i+1;
+}
+
+//---------------------------------------------------------------------------
+int Index::TranslateIndex(int Pos, Index *index)
+{
+ int v = GetCooperative(Pos);
+ IndexField *f = SecIndex;
+ while (f->index != this && f->index != index)
+ {
+ v = f->index->GetCooperative(v);
+ f = f->index->SecIndex;
+ }
+ return v;
+}
+
+//---------------------------------------------------------------------------
+void Index::Delete(int Idx, int Pos, Record *record)
+{
+ Update(NULL, -1, Idx, Pos, record, true, false);
+ Shrink();
+}
+
+//---------------------------------------------------------------------------
+void Index::Shrink(void)
+{
+ if (InChain) return;
+ if (SecIndex && SecIndex->index != this) // Actually, we should never be InInsert and here, but lets cover our ass
+ {
+ InChain=true;
+ SecIndex->index->Shrink();
+ InChain=false;
+ }
+ NEntries--;
+}
+
+//---------------------------------------------------------------------------
+void Index::SetGlobalLocateUpToDate(bool isUptodate) {
+ if (!pTable) return;
+ pTable->SetGlobalLocateUpToDate(isUptodate);
+}
+
+unsigned char Index::GetId() {
+ return Id;
+} \ No newline at end of file
generated by cgit (git 2.34.1) at 2025-05-01 22:22:04 -0400