template<typename RECORD_TYPE, const uint_fast8_t MAX_LOOKAHEAD = 4, const unsigned char SMALLEST_CHAR = 'A', const unsigned char LARGEST_CHAR = 'Z', typename LT_KEY_COMPARE = FastLookupUtils::ltBinaryBlock>
class FastLookupTable< RECORD_TYPE, MAX_LOOKAHEAD, SMALLEST_CHAR, LARGEST_CHAR, LT_KEY_COMPARE >
Fast map lookup table.
- Parameters
-
RECORD_TYPE | identifies the type of the records to be referenced by the map. |
MAX_LOOKAHEAD | specifies how many characters are to be used for fixed fanout tables. |
SMALLEST_CHAR | identifies the smallest expected character value to be seen in a key. |
LARGEST_CHAR | identifies the largest expected character value to be seen in a key. |
LT_KEY_COMPARE | is the comparison routine for the key. The default routine does a binary comparison and would rarely need to be replaced; however, this can be useful to handle special modifiers embedded within a key. |
- Note
If a character appears outside the range of [SMALLEST_CHAR,LARGEST_CHAR], the key will still be accepted. It will be added to the local out-of-bounds list, which incurs O(ln N) additional overhead where N is the number of exceptional elements recorded at that level.
If a key is longer than the MAX_LOOKAHEAD limit, it will still be accepted. It is added to the out-of-bounds list at the leaf element of the fixed fanout tables. The default comparison routine honors the key length.
The MAX_LOOKAHEAD parameter has the greatest effect on trading space for time: the amount of space required is proportional to (LARGEST_CHAR - SMALLEST_CHAR) raised to the MAX_LOOKAHEAD power. Simply put: the amount of space required increases exponentially as MAX_LOOKAHEAD increases and it becomes increasingly infeasible to fit all of the data into a CPU's cache. If the keys are not uniformly distributed, many of the fixed fanout tables will be sparse, which lowers the effectiveness of the CPU's cache with respect to whatever data was retrieved.
Arbitrary binary keys can be handled using SMALLEST_CHAR set to 0 and LARGEST_CHAR set to 255; however, cache efficiency goes down and storage requirements go up as the range is widened. With MAX_LOOKAHEAD=2
, about 1 megabyte will be required for the data structures. Increasing MAX_LOOKAHEAD to 3 raises the storage requirements to about 256 megabytes.
template<typename RECORD_TYPE , const uint_fast8_t MAX_LOOKAHEAD = 4, const unsigned char SMALLEST_CHAR = 'A', const unsigned char LARGEST_CHAR = 'Z', typename LT_KEY_COMPARE = FastLookupUtils::ltBinaryBlock>
int FastLookupTable< RECORD_TYPE, MAX_LOOKAHEAD, SMALLEST_CHAR, LARGEST_CHAR, LT_KEY_COMPARE >::addRecord |
( |
const char * |
key, |
|
|
RECORD_TYPE * |
rec |
|
) |
| |
|
inline |
template<typename RECORD_TYPE , const uint_fast8_t MAX_LOOKAHEAD = 4, const unsigned char SMALLEST_CHAR = 'A', const unsigned char LARGEST_CHAR = 'Z', typename LT_KEY_COMPARE = FastLookupUtils::ltBinaryBlock>
int FastLookupTable< RECORD_TYPE, MAX_LOOKAHEAD, SMALLEST_CHAR, LARGEST_CHAR, LT_KEY_COMPARE >::addRecord |
( |
const std::string & |
key, |
|
|
RECORD_TYPE * |
rec |
|
) |
| |
|
inline |
template<typename RECORD_TYPE , const uint_fast8_t MAX_LOOKAHEAD = 4, const unsigned char SMALLEST_CHAR = 'A', const unsigned char LARGEST_CHAR = 'Z', typename LT_KEY_COMPARE = FastLookupUtils::ltBinaryBlock>
int FastLookupTable< RECORD_TYPE, MAX_LOOKAHEAD, SMALLEST_CHAR, LARGEST_CHAR, LT_KEY_COMPARE >::addRecord |
( |
const unsigned char * |
key, |
|
|
const uint_fast32_t |
keyLen, |
|
|
RECORD_TYPE * |
rec |
|
) |
| |
|
inline |
Add a record to mapping table.
- Parameters
-
key | points to the start of the key |
keyLen | indicates the length of the key; it must be greater than 0. |
rec | is a pointer to the record which is to be stored |
- Return values
-
1 | indicates it was added within the MAX_LOOKAHEAD tables. |
2 | indicates it had characters outside the range |
3 | indicates it was longer than MAX_LOOKAHEAD . |
- Warning
- The contents of the key are not copied and must be maintained at the specified location for the lifetime of the record. An ideal solution is for the key to be located within the record itself and thus share its fate.
References FastLookupTable< RECORD_TYPE, MAX_LOOKAHEAD, SMALLEST_CHAR, LARGEST_CHAR, LT_KEY_COMPARE >::addRecordToSpillover(), app(), AS_TEXT_BUFFER, FastLookupTable< RECORD_TYPE, MAX_LOOKAHEAD, SMALLEST_CHAR, LARGEST_CHAR, LT_KEY_COMPARE >::ELEMENT_RANGE, LOG_COMPONENT_CERR, LOG_ENDLINE, FastLookupTable< RECORD_TYPE, MAX_LOOKAHEAD, SMALLEST_CHAR, LARGEST_CHAR, LT_KEY_COMPARE >::nextLevel, OME_EXPECT_FALSE, OME_EXPECT_TRUE, OME_PREFETCH, and FastLookupTable< RECORD_TYPE, MAX_LOOKAHEAD, SMALLEST_CHAR, LARGEST_CHAR, LT_KEY_COMPARE >::record.
Referenced by FastLookupTable< RECORD_TYPE, MAX_LOOKAHEAD, SMALLEST_CHAR, LARGEST_CHAR, LT_KEY_COMPARE >::addRecord().
template<typename RECORD_TYPE , const uint_fast8_t MAX_LOOKAHEAD = 4, const unsigned char SMALLEST_CHAR = 'A', const unsigned char LARGEST_CHAR = 'Z', typename LT_KEY_COMPARE = FastLookupUtils::ltBinaryBlock>
RECORD_TYPE* FastLookupTable< RECORD_TYPE, MAX_LOOKAHEAD, SMALLEST_CHAR, LARGEST_CHAR, LT_KEY_COMPARE >::findRecord |
( |
const unsigned char * |
key, |
|
|
const uint_fast32_t |
keyLen |
|
) |
| const |
|
inline |
Find record in mapping table.
- Parameters
-
key | points to the start of the key |
keyLen | indicates the length of the key; it must be greater than 0. |
- Return values
-
0 | indicates the record was not found |
References app(), AS_TEXT_BUFFER, FastLookupTable< RECORD_TYPE, MAX_LOOKAHEAD, SMALLEST_CHAR, LARGEST_CHAR, LT_KEY_COMPARE >::ELEMENT_RANGE, FastLookupTable< RECORD_TYPE, MAX_LOOKAHEAD, SMALLEST_CHAR, LARGEST_CHAR, LT_KEY_COMPARE >::findRecordInSpillover(), LOG_COMPONENT_CERR, LOG_ENDLINE, FastLookupTable< RECORD_TYPE, MAX_LOOKAHEAD, SMALLEST_CHAR, LARGEST_CHAR, LT_KEY_COMPARE >::nextLevel, OME_EXPECT_FALSE, OME_EXPECT_TRUE, OME_PREFETCH, and FastLookupTable< RECORD_TYPE, MAX_LOOKAHEAD, SMALLEST_CHAR, LARGEST_CHAR, LT_KEY_COMPARE >::record.
Referenced by FastLookupTable< RECORD_TYPE, MAX_LOOKAHEAD, SMALLEST_CHAR, LARGEST_CHAR, LT_KEY_COMPARE >::findRecord().