#ifndef librock_ILOCATE_H #define librock_ILOCATE_H #include #ifdef librock_EXPERIMENTAL_LOCATE_x001 #define librock_CHashLocatebySZ librock_CHashLocatebySZ_x001 #define librock_IHash32Locate librock_IHash32Locate_x001 #define librock_CFHash32Locate librock_CFHash32Locate_x001 #define librock_CHashLocatebyUI32 librock_CHashLocatebyUI32_x001 #define librock_CHashLocatebyUI32_B librock_CHashLocatebyUI32_B_x001 #define librock_CHashWeightedLocatebySZ librock_CHashWeightedLocatebySZ_x001 #include /* License text in librock_LIDESC_HC=12440211096131f5976d36be0cddca4cd9152e45 */ /* $Log: locate.h,v $ Revision 1.6 2002/04/09 03:54:23 forrest@mibsoftware.com rights=#1 Misc fixes. Revision 1.5 2002/03/18 19:32:09 forrest@mibsoftware.com rights=#1 API and implementation changes for librock Revision 1.4 2002/02/10 03:16:48 forrest@mibsoftware.com rights=#1 EXPERIMENTAL bracketing. Standardized chg log. Revision 1.3 2002/01/30 15:00:37 forrest@mibsoftware.com rights=#1 Fix for librock_CHashLocatebySz constructor Revision 1.2 2002/01/29 04:40:02 forrest@mibsoftware.com rights=#1 Prep for publish. API clean up, TAB, space at eol removal Revision 1.1 2001/01/06 19:36:17 forrest@mibsoftware.com rights=#1 Initial import to CVS rights#1 Copyright (c) Forrest J Cavalier III d-b-a Mib Software rights#1 License text in librock_LIDESC_HC=12440211096131f5976d36be0cddca4cd9152e45 */ #include #include /**************************************************************/ class librock_PTR librock_ILocate { /* 12/4/98 Interface class */ public: virtual void DeleteAll() = 0; virtual int Delete(const void librock_PTR *pIndex) = 0; virtual int Insert(const void librock_PTR *lpvIndex,const void librock_PTR *lpvData) = 0; virtual int InsertOrReplace(const void librock_PTR *pIndex,const void librock_PTR *lpvData) = 0; virtual int FindM(const void librock_PTR *lpvIndex,void *pData,int iBase,int N) = 0; virtual void librock_PTR *ITERbegin() = 0; virtual void librock_PTR *ITERnext(void librock_PTR *pIterInfo,const void librock_PTR * librock_PTR *ppIndex) = 0; virtual void ITERend(void librock_PTR *pIterInfo) = 0; }; /* ILocate */ #if 0 /**************************************************************/ class librock_PTR librock_IHash32Locate : public librock_ILocate { /* 10-1-96 */ /* 11-20-96 works on blank terminated words by default, override the following virtual functions to get other functionality: entrycmp() hashfn() Insert(); Example overrides: CHashSZDict */ /* DEBUG: document */ /* DEBUG: move all implementation out of here */ protected: struct Entry_s { librock_uint32_t hashcode; char data[1]; /* Data stored here by _Store */ }; struct Entry_s librock_PTR * librock_PTR *m_entries; /* Head entries of expanding hash table */ int m_cEntries; /* count of items in m_entries. NOT the number of items inserted so far! */ librock_CPRCL_x001 m_prclEntries; virtual librock_uint32_t hashfn(const void librock_PTR *lpvIndex) = 0; virtual int indexcmp(const void librock_PTR *lpvIndex,struct CDictEntry_t librock_PTR *cmp) =0; protected: struct CDictEntry_t *_Store(const void librock_PTR *lpvData,int cbData,librock_uint32_t hc, const void librock_PTR *location); struct CDictEntry_t librock_PTR *_Lookup(const void librock_PTR *lpvIndex,int cnt) { librock_uint32_t hashcode = hashfn(lpvIndex); int ind = (int) (hashcode % m_cEntries); struct Entry_s librock_PTR *p; p = m_entries[ind]; while(p) { while(p && (p->hashcode != hashcode)) { p = p->next; } if (!p) { break; } /* Here with a match for hashcode */ if (!indexcmp(lpvIndex,p)) { cnt--; if (cnt < 0) { return p; } } p = p->next; } return 0; /* Not found */ }; public: IHashLocate(int cEntries); virtual int Insert(const void librock_PTR *lpvIndex,const void librock_PTR *pointer) = 0; /* moved from protected 7/2/99 */ virtual int InsertX(const void librock_PTR *lpvIndex,int cbIndex,const void librock_PTR *pointer,int cbPointer); virtual void DeleteAll(); virtual void *PRCLperm(int c) { return m_prclEntries.PRCLperm(c); } /* 2/9/2000 */ virtual int Delete(const void *) { assert(0&&"Delete() Unsupported"); return -1; }; virtual int InsertOrReplace(const void librock_PTR *lpszNameType,const void librock_PTR *location); virtual void librock_PTR *Lookup(const void librock_PTR *lpsbName) { void *location; if (LookupX(lpsbName,&location,0,0,1)) { return location; } else { return 0; } } virtual int LookupX(const void librock_PTR *lpvIndex,void librock_PTR * librock_PTR*ppLocation,void librock_PTR * librock_PTR *ppData,int iBase,int N) { /* 9/14/2000 API change */ /*N Parameter and name changed 7/2/99 */ librock_uint32_t hashcode = hashfn(lpvIndex); int ind = (int) (hashcode % m_cEntries); struct Entry_s librock_PTR *p; p = m_entries[ind]; int iRet = 0; while(p) { while(p && (p->hashcode != hashcode)) { p = p->next; } if (!p) { return iRet; } /* Here with a match for hashcode */ if (!indexcmp(lpvIndex,p)) { iBase--; if (iBase < 0) { if (ppData) { ppData[iRet] = p->data; } if (ppLocation) { ppLocation[iRet] = p->location; } iRet++; if (iRet >= N) { return iRet; } } } p = p->next; } return iRet; }; struct IterInfo_s { librock_uint32_t hashcode; int iCnt; }; virtual void librock_PTR *ITERbegin() { /* DEBUG: should take argument to allow iter of multiple matching items */ struct IterInfo_s librock_PTR *p = (struct IterInfo_s librock_PTR *) malloc(sizeof(IterInfo_s)); if (p) { p->hashcode = 0; p->iCnt = 0; } return p; }; virtual void ITERend(void librock_PTR *pIterInfo) { free(pIterInfo); }; virtual void librock_PTR *ITERnext(void librock_PTR *pIterInfo,const void librock_PTR * librock_PTR *ppData) { /* see wri2htm/topic.cpp for example of iterating start with *iCnt = 0, *phashcode = 0 */ /* 3/5/97 */ struct IterInfo_s librock_PTR *pIter = (struct IterInfo_s librock_PTR *) pIterInfo; int ind; struct Entry_s librock_PTR *p; ind = (int) (pIter->hashcode % m_cEntries); do { p = m_entries[ind]; int iCnt = pIter->iCnt; while(p) { /* Walk out to iCnt */ /* Here with a match for hashcode */ if (iCnt <= 0) { /* Stop here */ if (ppData) { *ppData = p->data; } /* Set up next entry */ pIter->iCnt += 1; if (p->next) { } else if (ind < m_cEntries-1) { pIter->iCnt = 0; pIter->hashcode += 1; } /* else leave it: it is the last entry...*/ return p->location; } p = p->next; iCnt--; } /* Advance to next bin */ ind++; if (ind < m_cEntries) { pIter->iCnt = 0; pIter->hashcode += 1; } } while(ind < m_cEntries); /* All bins are empty */ return 0; } #if 0 void librock_PTR *ITEREntries(long librock_PTR *phashcode,int *piCnt,const char librock_PTR * librock_PTR *ppname=0) { /* see wri2htm/topic.cpp for example of iterating start with *iCnt = 0, *phashcode = 0 */ /* 3/5/97 */ int ind; struct CDictEntry_t librock_PTR *p; ind = (int) (*phashcode % m_cEntries); do { p = m_entries[ind]; int iCnt = *piCnt; while(p) { /* Walk out to iCnt */ /* Here with a match for hashcode */ if (iCnt <= 0) { if (ppname) { *ppname = p->name; } /* Set up next entry */ *piCnt += 1; if (p->next) { } else if (ind < m_cEntries-1) { *piCnt = 0; *phashcode += 1; } /* else leave it: it is the last entry...*/ return p->pointer; } p = p->next; iCnt--; } /* Advance to next bin */ ind++; if (ind < m_cEntries) { *piCnt = 0; *phashcode += 1; } } while(ind < m_cEntries); /* All bins are empty */ return 0; }; #endif }; /* IHashLocate */ #endif #ifdef librock_EXPERIMENTAL_PRCL_x001 /**************************************************************/ #include class librock_CBoundedLinLocate : public librock_ILocate { /* 12/4/98 */ /* DEBUG: document */ /* DEBUG: move all implementation out of here */ /* Searches are linear. Growth is limited to a fixed number of entries */ protected: struct CDictEntry_t { const void librock_PTR *pIndex; void librock_PTR *p; }; struct CDictEntry_t *m_Entries; int m_cEntries; /* count of items in m_entries */ librock_CPRCL_x001 m_prclEntries; /* For storing indexes */ protected: public: librock_CBoundedLinLocate(int cEntries); virtual ~librock_CBoundedLinLocate(); virtual void DeleteAll() { assert(0&&"CBoundedLinLocate::DeleteAll() Unsupported");}; virtual int Delete(const void *) { assert(0&&"Delete() Unsupported"); return -1; }; virtual int Insert(const void librock_PTR *lpszNameType,const void librock_PTR *pointer); virtual int InsertOrReplace(const void librock_PTR *lpszNameType,const void librock_PTR *pointer); virtual void librock_PTR *Lookup(const void librock_PTR *lpsbName) { return Lookup(lpsbName,0); } int indexcmp(const void librock_PTR *pvIndex1,const void librock_PTR *pvIndex2) { return strcmp((const char librock_PTR *)pvIndex1,(const char librock_PTR *)pvIndex2); } virtual void librock_PTR *Lookup(const void librock_PTR *lpvIndex,const char librock_PTR * librock_PTR *ppname) { int ind = 0; while(ind < m_cEntries) { if (m_Entries[ind].pIndex && !indexcmp(lpvIndex,m_Entries[ind].pIndex)) { if (ppname) { *ppname = (const char librock_PTR *) (m_Entries[ind].pIndex); } return m_Entries[ind].p; } ind++; } return 0; }; struct IterInfo_s { int i; }; virtual void librock_PTR *ITERbegin() { struct IterInfo_s librock_PTR *p = (struct IterInfo_s librock_PTR *) malloc(sizeof(IterInfo_s)); if (p) { p->i = 0; } return p; }; virtual void ITERend(void librock_PTR *pIterInfo) { free(pIterInfo); }; virtual void librock_PTR *ITERnext(void librock_PTR *pIterInfo,const void librock_PTR * librock_PTR *ppIndex) { struct IterInfo_s librock_PTR *pIter = (struct IterInfo_s librock_PTR *) pIterInfo; while(pIter->i < m_cEntries) { pIter->i += 1; /* Set for next */ if (m_Entries[pIter->i - 1].pIndex) { return m_Entries[pIter->i -1].p; } } return 0; } }; /* librock_CBoundedLinLocate */ #endif /**************************************************************/ class librock_PTR librock_IHash32Locate /* : librock_ILocate */ { /* Table0 is an in-memory array with fixed row, column and entry size Table1 is a larger array with fixed column and entry size. Could be on disk only. Table2 is an expansion table, holding only overflow from Table1. It is more expensive to access this table, because the offset must be obtained from the entry in Table1, instead of calculated from the row. Sizing the tables is a tradeoff between empty space in the table, and access times. 50% larger than the expected number of entries is a good approximation, although this will store any number of items, by overflowing into table2. */ protected: struct HashTableEntry_s { librock_uint32_t hashcode; char data[1]; /* Data stored here by _Store. Fixed length. Generally this a location, but it could be any fixed length data, extra hash bits, etc. The length of data stored is determined by an argument to the constructor. */ }; struct expansion_s { /* prefix of Table1 row. Offsets into .2 expansion table */ short int iPastUsed; librock_uint32_t offsetOverflow; librock_uint32_t cAllocOverflow; librock_uint32_t iPastUsedOverflow; }; virtual void CalcGeometry(int nRows,int nCols, int cbEntryData); int m_nRows; /* Rows in Table0 and Table1. Determined by the argument given to the constructor */ int m_nCols; /* Columns in Table0. Determined by the argument given to the constructor */ int m_nColsTable1ExpansionRow; /* Number of columns in table 1. Calculated in the constructor */ int m_nColsTable1SubRow; /* Number of columns in table 1 subrows. Calculated in the constructor */ int m_nTable1SubRow; /* Number of table 1 subrows. Calculated in the constructor */ int m_sizeofTable1SubRow; /* Number of bytes in a table1 subrow. nColsTable1 * sizeofHashEntry + sizeof(struct expansion_s) */ int m_sizeofTable1Block; /* Calculated in the constructor. Size of table1 block Read and written */ int m_sizeofHashTableEntry; int m_Table1Bias; /* Statistics */ int m_cToTable1; int m_cLookup0notfound; int m_bDumpStats; int *m_iTable1InsertNext; /* If known */ int *m_iTable0InsertNext; /* (NOTE: If Table0 ever gets shared by processes, m_iTable0InsertNext[] must be part of what is shared.) */ struct HashTableEntry_s *m_pEmptyEntry; struct HashTableEntry_s librock_PTR *m_pTable0; /* Head entries of expanding hash table */ #if 0 virtual int indexcmp(const void librock_PTR *lpName,const struct HashTableEntry_s librock_PTR *cmp) { assert(0&&"indexcmp not supported in base class"); return 1;}; #endif librock_CAllocOffset32 *paifTable2; int m_bTable2InMem; #if 0 #define librock_IHash32Locate_nRowGroupBuffers 10 int m_nRowGroupBuffers; struct expansion_s *m_pRowGroupBuffers[librock_IHash32Locate_nRowGroupBuffers]; int m_iRowGroupBuffers[librock_IHash32Locate_nRowGroupBuffers]; int m_rRowGroupBuffers[librock_IHash32Locate_nRowGroupBuffers]; #endif public: inline struct HashTableEntry_s *Advance(const void *p,int amt) { return (struct HashTableEntry_s *) ((char *) p + amt * m_sizeofHashTableEntry); }; virtual int indexcmp(const void librock_PTR *lpvIndex,const void *pHTE) =0; protected: struct HashTableEntry_s librock_PTR *_Store(librock_uint32_t hc, const void librock_PTR *lpvData); struct SearchRow_s { /* Used internally, to pass arguments back and forth to _SearchRow */ librock_uint32_t hc; const void *pIndex; void *pRet; /* HashTableEntries, but derived class may have different sizes. */ long *piHTE; int iBase; int cToFill; }; virtual void _SearchRow( const struct HashTableEntry_s librock_PTR *pRow, int nCols, struct SearchRow_s *s, int iBaseHTE ); /* virtual void _SearchRow( const struct HashTableEntry_s librock_PTR *pRow, int nCols, librock_uint32_t hc, struct HashTableEntry_s librock_PTR *pRet, long *piHTE,long iBaseHTE, int *piBase, int *pcToFill); */ int _RowPack(struct HashTableEntry_s *pdest,struct HashTableEntry_s *psrc,int nSrc); virtual char *LoadTable2Row(long o,long cRow,long cAdd) = 0; virtual int ToTable2(struct expansion_s *pTable1Image,int cnt) = 0; virtual void FreeTable2Row(char *pImage) = 0; virtual void FreeTable1Block(int bChanged,unsigned iSubRow,struct HashTableEntry_s *pBlock,struct expansion_s *pSubRow) = 0; virtual void LoadTable1Block(unsigned iSubRow,struct HashTableEntry_s **ppErow,struct expansion_s **ppSubRow) = 0; virtual void ToTable1(struct HashTableEntry_s *pToPurge,int cPurge); virtual void WriteRange(unsigned iSubRow, long iHTE,struct HashTableEntry_s *pToWrite,int cWrite) = 0; virtual void AllToTable1(); public: /* Insert() and InsertOrReplace() store a copy of a fixed-size block of memory at lpvData, for later retrieval by FindM(). hashfn() is called to determine a hash code. The size of the block is set in the constructor. Except as an argument to hashfn(), this class does not use or store pIndex. FindM() calls hashfn() on pIndex, and then copies blocks with matching hashcodes. If further comparison of the indexes is required, the caller must store an index in each block, and compare. Because derivative classes are already provided, it will be be rare that you need to derive from this class directly. Use one of the derivative classes instead. */ librock_IHash32Locate(int nRows,int nCols, int cbEntryData); virtual ~librock_IHash32Locate(); #if 0 virtual struct HashTableEntry_s librock_PTR *LookupX(struct HashTableEntry_s librock_PTR *pCopy,const void *pIndex,int cnt); virtual void Dump0(librock_IStream *f); #endif virtual void Check(); #if 0 void DumpStatsTable1Block(librock_uint32_t hc,struct HashTableEntry_s *pTable1ExpansionRow,FILE *f); virtual void DumpStats(FILE *f); #endif virtual librock_uint32_t hashfn(const void librock_PTR *lpvIndex) = 0; public: /* librock_ILocate interface */ virtual int Insert(const void librock_PTR *lpvIndex,const void librock_PTR *lpvData); virtual int InsertOrReplace(const void librock_PTR *lpvIndex,const void librock_PTR *lpvData) { assert(0&&"InsertOrReplace() Not written"); return 0;}; virtual int FindMHC(const void librock_PTR *pIndex, unsigned iSubRow, void *pRet, /* Copies of HashTableEntries */ long *piHTE, /* Indices of the entry */ int iBase, int N); virtual int FindM(const void librock_PTR *pIndex, void *pRet, /* Copies of HashTableEntries */ long *piHTE, /* Indices of the entry */ int iBase, int N); int IterM(int iSubRow, void *pRet, long *piHTE, int iBase, int N); virtual void DeleteAll() { assert(0&&"DeleteAll Method not written"); }; virtual int Delete(const void librock_PTR *) { assert(0&&"Delete() not written"); return -1; }; #if 0 /* Removed 2002-04-04. Use IterM instead */ virtual void librock_PTR *ITERbegin(); virtual void ITERend(void librock_PTR *pIterInfo); virtual void librock_PTR *ITERnext(void librock_PTR *pIterInfo,const void librock_PTR * librock_PTR *ppData); #endif }; /* librock_IHash32Locate */ /**************************************************************/ class librock_PTR librock_CFHash32Locate : public librock_IHash32Locate { /* Table0 is an in-memory array with fixed row, column and entry size Table1 is a larger array with fixed column and entry size. Could be on disk only. Table2 is an expansion table, holding only overflow from Table1. It is more expensive to access this table, because the offset must be obtained from the entry in Table1, instead of calculated from the row. Sizing the tables is a tradeoff between empty space in the table, and access times. 50% larger than the expected number of entries is a good approximation, although this will store any number of items, by overflowing into table2. */ protected: #if 0 virtual int indexcmp(const void librock_PTR *lpName,const struct HashTableEntry_s librock_PTR *cmp) { assert(0&&"indexcmp not supported in base class"); return 1;}; #endif #if 0 #define librock_IHash32Locate_nRowGroupBuffers 10 int m_nRowGroupBuffers; struct expansion_s *m_pRowGroupBuffers[librock_IHash32Locate_nRowGroupBuffers]; int m_iRowGroupBuffers[librock_IHash32Locate_nRowGroupBuffers]; int m_rRowGroupBuffers[librock_IHash32Locate_nRowGroupBuffers]; #endif public: protected: struct HashTableEntry_s librock_PTR *_Store(librock_uint32_t hc, const void librock_PTR *lpvData); virtual char *LoadTable2Row(long o,long cRow,long cAdd); virtual int ToTable2(struct expansion_s *pTable1Image,int cnt); virtual void FreeTable2Row(char *pImage); virtual void FreeTable1Block(int bChanged,unsigned iSubRow,struct HashTableEntry_s *pBlock,struct expansion_s *pSubRow); virtual void LoadTable1Block(unsigned iSubRow,struct HashTableEntry_s **ppErow,struct expansion_s **ppSubRow); virtual void WriteRange(unsigned iSubRow, long iHTE,struct HashTableEntry_s *pToWrite,int cWrite); librock_FILE *m_f; /* Image of Table0,1,2, if in a file */ char *m_pTable1; /* Image of Table1, if m_f is 0 */ public: librock_CFHash32Locate(int nRows,int nCols, int cbEntryData); virtual ~librock_CFHash32Locate(); void Open(const char *asz); #if 0 virtual struct HashTableEntry_s librock_PTR *LookupX(struct HashTableEntry_s librock_PTR *pCopy,const void *pIndex,int cnt); #endif virtual void Dump0(librock_FILE *f); void Load0(librock_FILE *f); virtual void Check() {}; /* Checking and stats */ void DumpStatsTable1Block(librock_uint32_t hc,struct HashTableEntry_s *pTable1ExpansionRow,librock_FILE *f); virtual void DumpStats(librock_FILE *f); virtual librock_uint32_t hashfn(const void librock_PTR *ptr) = 0; }; /* librock_CFHash32Locate */ /**************************************************************/ /**************************************************************/ class librock_CFHash32LocateFposByBTS : public librock_CFHash32Locate { public: struct HashTableEntry_s { librock_uint32_t hashcode; long pos; }; inline struct HashTableEntry_s *Advance(const void *p,int amt) { return (struct HashTableEntry_s *) ((char *) p + amt * m_sizeofHashTableEntry); }; librock_CFHash32LocateFposByBTS(int row,int col); virtual librock_uint32_t hashfn(const void librock_PTR *pIndex) { librock_uint32_t ret = 0; const char *ptr = (char *) pIndex; while(*ptr > ' ') { ret = (ret << 5) + ret + (((*ptr >= 'A')&& (*ptr <= 'Z')) ? (*ptr + ('a' - 'A')) : *ptr); ptr++; } return ret; }; protected: librock_FILE *m_fData; int m_bCI; /* case insensitive */ protected: const char *aGetItem(char **ppaszLine,struct HashTableEntry_s *p); int _aPutItem(const char *pszLine,struct HashTableEntry_s *p); public: void IgnoreCase() { m_bCI = 1; }; const char * Open(const char *pszDataFile); virtual ~librock_CFHash32LocateFposByBTS(); const char * Rebuild(const char *pszDataFile); void Replace(const char *pszLine); /* 2/8/2001 */ void Append(const char *pszLine); #if 0 void AppendBin(const void *pszLine,librock_uint32_t cbLine) { /* 2/8/2001 */ fseek(m_fData,0,SEEK_END); long pos = ftell(m_fData); fwrite(&cbLine,1,sizeof(cbLine),m_fData); fwrite(pszLine,1,cbLine,m_fData); fflush(m_fData); /* DEBUG: performance killer */ Insert(pszLine,&pos); } int FindLastBin(void **ppasz,const char *asz,int iBase); /* 2/8/2001 */ #endif virtual int indexcmp(const void librock_PTR *lpName,const void *pHTE); int FindM(char **ppasz,const char *asz,int iBase,int cMax); }; inline librock_CFHash32LocateFposByBTS::librock_CFHash32LocateFposByBTS(int row,int col) : librock_CFHash32Locate(row,col,sizeof(struct HashTableEntry_s)) { m_fData = 0; m_bCI = 0; } /**************************************************************/ class librock_CHashLocatebySZ : public librock_CFHash32Locate { /* CDictEntry_t->data holds the null terminated string index value Non-case sensitive string comparisons and hashes. This used to be called CHashSZDict */ public: librock_CHashLocatebySZ(int n,const char *); virtual ~librock_CHashLocatebySZ(); private: virtual int Insert(const void librock_PTR *lpvIndex,const void librock_PTR *pointer) {/* */return 0;}; protected: struct HashTableEntry_s { librock_uint32_t hashcode; char *pszIndex; const void *pointer; }; class librock_CPRCL_x001 *store; virtual librock_uint32_t hashfn(const void librock_PTR *ptr); /* Default is name! */ virtual int indexcmp(const void librock_PTR *lpvIndex,const void *pHTE); public: #if 0 virtual int Insert(const void librock_PTR *lpvIndex,const void librock_PTR *pointer); #endif virtual int Insert_B(const void librock_PTR *lpvIndex,int cbIndex,const void librock_PTR *pointer,int cbPointer); int FindM(const char *asz,void **pRet,int iBase,int cMax); }; inline librock_CHashLocatebySZ::librock_CHashLocatebySZ(int n,const char *fname) : librock_CFHash32Locate(n,4,sizeof(struct HashTableEntry_s)) { store = 0; Open(fname); }; /**************************************************************/ class librock_CHashLocatebyLine : public librock_IHash32Locate { /* CDictEntry_t->data holds the null terminated string index value Non-case sensitive string comparisons and hashes. This used to be called CHashSZDict */ struct HashTableEntry_s { librock_uint32_t hashcode; char *pszLine; }; public: librock_CHashLocatebyLine(int n); protected: virtual librock_uint32_t hashfn(const void librock_PTR *ptr); virtual int indexcmp(const void librock_PTR *lpName,struct HashTableEntry_s librock_PTR *cmp); public: virtual int Insert(const void librock_PTR *lpvIndex,const void librock_PTR *pointer); virtual int Insert_B(const void librock_PTR *lpvIndex,int cbIndex,const void librock_PTR *pointer,int cbPointer); }; inline librock_CHashLocatebyLine::librock_CHashLocatebyLine(int n) : librock_IHash32Locate(n,4,sizeof(struct HashTableEntry_s)) {}; /**************************************************************/ class librock_CHashLocatebyBTS : public librock_IHash32Locate { /* CDictEntry_t->data holds the null terminated string index value. Non-case sensitive comparisons and hashes are up to first blank or whitespace. */ public: struct HashTableEntry_s { librock_uint32_t hashcode; char *pszIndex; }; librock_CHashLocatebyBTS(int n); protected: virtual librock_uint32_t hashfn(const void librock_PTR *ptr); /* Default is name! */ virtual int indexcmp(const void librock_PTR *lpName,const void *pHTE); public: virtual int Insert(const void librock_PTR *lpvIndex,const void librock_PTR *pointer); }; inline librock_CHashLocatebyBTS::librock_CHashLocatebyBTS(int n) : librock_IHash32Locate(n,4,sizeof(struct HashTableEntry_s)) {}; /**************************************************************/ #ifdef librock_EXPERIMENTAL_CHashLocatebyUI32_x001 class librock_CHashLocatebyUI32 : public librock_CFHash32Locate { public: librock_CHashLocatebyUI32(int n); struct HashTableEntry_s { librock_uint32_t hashcode; const void *location; }; protected: virtual librock_uint32_t hashfn(const void librock_PTR *ptr); virtual int indexcmp(const void librock_PTR *lpvIndex,const void *pHTE) { return 0; #if 0 librock_uint32_t l = *((librock_uint32_t *) lpvIndex); return (l - *((librock_uint32_t *) cmp->data)); #endif } private: virtual int FindM(const void librock_PTR *pIndex, void *pRet, /* Copies of HashTableEntries */ long *piHTE, /* Indices of the entry */ int iBase, int N) { assert(!("Can't call this, because indexcmp doesn't work!")); return 0; } public: int Insert(const void librock_PTR *lpvIndex,const void librock_PTR *pointer) { struct HashTableEntry_s entry; entry.location = pointer; librock_CFHash32Locate::Insert(lpvIndex,&entry.location); return 0; }; }; /**************************************************************/ #endif #ifdef librock_EXPERIMENTAL_CHashLocatebyUI32_B_x001 class librock_CHashLocatebyUI32_B : public librock_CFHash32Locate { /* CDictEntry_t->data holds the librock_uint32_t index value */ public: librock_CHashLocatebyUI32_B(int n); struct HashTableEntry_s { librock_uint32_t hashcode; const void *location; librock_uint32_t index; }; protected: virtual librock_uint32_t hashfn(const void librock_PTR *ptr); virtual int indexcmp(const void librock_PTR *lpvIndex,const void *pHTEarg) { struct HashTableEntry_s *pHTE = ((struct HashTableEntry_s *) pHTEarg); librock_uint32_t l = *((librock_uint32_t *) lpvIndex); return (l - pHTE->index); } public: int Insert(const void librock_PTR *lpvIndex,const void librock_PTR *pointer) { struct HashTableEntry_s entry; entry.location = pointer; entry.index = *((librock_uint32_t *) lpvIndex); librock_CFHash32Locate::Insert(lpvIndex,&entry.location); return 0; }; virtual void WriteRange(unsigned iSubRow, long iHTE,struct HashTableEntry_s *pToWrite,int cWrite) { librock_CFHash32Locate::WriteRange(iSubRow,iHTE,(librock_IHash32Locate::HashTableEntry_s *)pToWrite,cWrite); } }; /**************************************************************/ #endif #ifdef librock_EXPERIMENTAL_PRCL_x001 class librock_CHashWeightedLocatebySZ : protected librock_CFHash32Locate { /* Each reference has a weight. */ struct HashTableEntry_s { librock_uint32_t hashcode; const char *psz; const void *location; int weight; }; public: librock_CHashWeightedLocatebySZ(int n); // int bOptimizeLookup; /* Set to 1 if all weights inserted will be grouped by location first */ /* bOptimizeLookup used to work when CFHash32Locate always did FindM in the most recently inserted order. It does not guarantee that as of 3-12-2002 */ protected: librock_CPRCL_x001 m_prclStrings; virtual librock_uint32_t hashfn(const void librock_PTR *ptr); /* Default is name! */ virtual int indexcmp(const void librock_PTR *lpName,const void librock_PTR *pHTE); public: virtual int Insert(const void librock_PTR *lpvIndex,const void librock_PTR *pointer) { assert(0&&"Call InsertWeight() instead"); return -1; }; virtual int InsertWeight(const void librock_PTR *lpvIndex,const void librock_PTR *location,long weight); }; inline librock_CHashWeightedLocatebySZ::librock_CHashWeightedLocatebySZ(int n) : librock_CFHash32Locate(n,4,sizeof(struct HashTableEntry_s)) { }; #endif /**************************************************************/ #endif /* EXPERIMENTAL */ #ifdef librock_EXPERIMENTAL_LOCATE_x001 #undef librock_CHashLocatebySZ #undef librock_IHash32Locate #undef librock_CFHash32Locate #undef librock_CHashLocatebyUI32 #undef librock_CHashLocatebyUI32_B #undef librock_CHashWeightedLocatebySZ #endif #include #endif