0
作爲實現編譯器的類項目的一部分，我還實現了用作編譯器符號表的哈希表。對象的C++ memcpy副本出現損壞
散列表的實現目的是非常低級的，手動打包的原始內存塊，它僅用於存儲令牌對象。因此，爲了優化哈希表的可序列化性，我決定簡單地將表中的令牌內聯，也就是說，當第一次插入令牌時，只需將令牌對象memcpy複製到表的內存中即可。
我知道一個不應該memcpy a class that has virtual functions or pointers，並在general using memcpy on objects of a class is bad practice。然而，從下面的聲明可以看出，Token類沒有虛函數或指針，如果這不是低級編程的練習，我不會使用memcpy。
class Token {
public:
Token() : tag(BAD) {}
Token(Tag t) : tag(t) {}
Tag tag;
size_t getSize(){ return sizeof(Token); }
};
，我遇到的問題是，哈希表正確插入記號，並尋找相同的密鑰時，發現相同的內存位置，但是，當我嘗試訪問返回的成員令牌指針，看起來數據已損壞。
我寫了一個程序來測試簡單輸入上的符號表。該程序執行以下操作：
- 將輸入文件讀入緩衝區。
- 通過將所有內置令牌插入Lexer符號表中來初始化Lexer。
- 在輸入中調用Lexer的getToken方法並打印令牌標籤，直到讀取EOF令牌。
儘管符號表返回內存中插入令牌的相同位置，但令牌的標記屬性不再匹配插入的原始屬性。下面是日誌輸出當程序插入關鍵字程序到符號表中：
[debug] Entering SymbolTable.insert(const char* key)
[debug] bin: 48 Searching for the last element in this bin's linked list.
[debug] Last entry found... writing to entry's next location field.
[debug] Writing the new entry's identifier to the table.
[debug] The identifier: program has been written to the table.
[debug] The memory blocks are not equal prior to assignment.
[debug] The memory blocks are equal.
[debug] nextLoc: 571 tag: 46
[debug] Location of Token: 14287688
並且在下面的日誌輸出當程序隨後查找該標識符在符號表程序。
[debug] Entering Lexer.getToken()
[debug] Entering SymbolTable.contains(const char* key)
[debug] Entering SymbolTable.find(const char* key) key: program
[debug] bin: 48
[debug] Search location: 541
[debug] Comparing key char: p to table char: p
[debug] Comparing key char: r to table char: a
[debug] Tag of entry: 1684368227
[debug] Location of Token: 14287653
[debug] Search location: 557
[debug] Comparing key char: p to table char: p
[debug] Comparing key char: r to table char: r
[debug] Comparing key char: o to table char: o
[debug] Comparing key char: g to table char: c
[debug] Tag of entry: 1920296037
[debug] Location of Token: 14287668
[debug] Search location: 0
[debug] Comparing key char: p to table char: p
[debug] Comparing key char: r to table char: r
[debug] Comparing key char: o to table char: o
[debug] Comparing key char: g to table char: g
[debug] Comparing key char: r to table char: r
[debug] Comparing key char: a to table char: a
[debug] Comparing key char: m to table char: m
[debug] Tag of entry: 1207959598
[debug] Location of Token: 14287688
The 1th token: 60
所以這可以從令牌消息的位置可以看出，符號表被發現在內存中同一位置的地方寫的令牌，但是令牌的標籤是不同的。我很難理解爲什麼會這樣。
爲了完整起見，這裏是SymbolTable類的定義。
template<class sizeType>
class SymbolTable{
public:
SymbolTable();
~SymbolTable();
Token* operator[](const char* key);
bool contains(const char* key);
Token* insert(const char* key, Token value);
private:
void* find(const char* key);
static const size_t nbins = 64;
sizeType nextLoc;
void* table;
size_t hash(const char* key){
return (size_t)key[0] % nbins;
}
};
這裏是符號表插入，查找和運算符[]函數的源代碼。
template<class sizeType> Token* SymbolTable<sizeType>::insert(const char* key, Token value){
BOOST_LOG_TRIVIAL(debug) << "Entering SymbolTable.insert(const char* key)";
size_t bin = hash(key);
void *sizeType_ptr,
*tbl_char_ptr,
*idSize_ptr;
unsigned char idSize = 0;
const char *key_ptr = key;
Token *token_ptr = NULL;
// Find the last entry in this bin's linked list.
BOOST_LOG_TRIVIAL(debug) << "bin: " << bin
<< " Searching for the last element in this bin's linked list.";
sizeType_ptr = table + sizeof(sizeType)*bin;
while(*((sizeType*)sizeType_ptr) != 0){
sizeType_ptr = table + *((sizeType*)sizeType_ptr);
}
BOOST_LOG_TRIVIAL(debug) << "Last entry found... writing to entry's next location field.";
// Write the location of the new entry to this entry's next field.
*((sizeType*)sizeType_ptr) = nextLoc;
// Move to new entry's location.
sizeType_ptr = table + nextLoc;
// Write identifier
BOOST_LOG_TRIVIAL(debug) << "Writing the new entry's identifier to the table.";
tbl_char_ptr = sizeType_ptr + sizeof(sizeType) + sizeof(unsigned char);
while(*key_ptr != '\0'){
*((char*)tbl_char_ptr) = *key_ptr;
tbl_char_ptr = tbl_char_ptr + sizeof(char);
++key_ptr;
++idSize;
}
BOOST_LOG_TRIVIAL(debug) << "The identifier: " << key << " has been written to the table.";
// Write length of identifier.
idSize_ptr = sizeType_ptr + sizeof(sizeType);
*((unsigned char*)idSize_ptr) = idSize;
token_ptr = (Token*)(tbl_char_ptr + sizeof(char));
void *tk = &value,
*tb = token_ptr;
for(int i = 0; i < value.getSize(); ++i){
if(*((char*)tk) != *((char*)tb)){
BOOST_LOG_TRIVIAL(debug) << "The memory blocks are not equal prior to assignment.";
break;
}
}
memcpy((void*)token_ptr, &value, value.getSize());
bool areEqual = true;
for(int i = 0; i < value.getSize(); ++i){
if(*((char*)tk) != *((char*)tb)){
areEqual = false;
BOOST_LOG_TRIVIAL(debug) << "The memory blocks are not after assignment.";
break;
}
}
if(areEqual){
BOOST_LOG_TRIVIAL(debug) << "The memory blocks are equal.";
}
nextLoc = nextLoc + sizeof(sizeType) + sizeof(unsigned char)
+ idSize*sizeof(char) + value.getSize();
BOOST_LOG_TRIVIAL(debug) << "nextLoc: " << nextLoc
<< " tag: " << token_ptr->tag;
BOOST_LOG_TRIVIAL(debug) << "Location of Token: " << (size_t)token_ptr;
return token_ptr;
}
template<class sizeType>
void* SymbolTable<sizeType>::find(const char* key){
BOOST_LOG_TRIVIAL(debug) << "Entering SymbolTable.find(const char* key) "
<< "key: " << key;
bool found = false;
size_t bin = hash(key);
void *idSize,
*sizeType_ptr,
*tbl_char_ptr,
*result_ptr = NULL;
const char* key_ptr = key;
BOOST_LOG_TRIVIAL(debug) << "bin: " << bin;
sizeType_ptr = table + sizeof(sizeType)*bin;
while(!found){
found = true;
// Is this the last element in this bin?
if(*((sizeType*)sizeType_ptr) == 0){
result_ptr = NULL;
return result_ptr;
}
// Advance to the next element in this bin's linked list.
sizeType_ptr = table + *((sizeType*)sizeType_ptr);
idSize = sizeType_ptr + sizeof(sizeType);
tbl_char_ptr = idSize + sizeof(unsigned char);
BOOST_LOG_TRIVIAL(debug) << "Search location: " << *((sizeType*)sizeType_ptr);
// Check if the passed key matches the current key in the table.
for(int i = 0; i < *((unsigned char*)idSize); ++i){
BOOST_LOG_TRIVIAL(debug) << "Comparing key char: " << *key_ptr
<< "to table char: " << *((const char*)tbl_char_ptr);
// Check if the key is too short or if the chars do not match.
if(*key_ptr != *((const char*)tbl_char_ptr)){
found = false;
break;
}
++key_ptr;
tbl_char_ptr = tbl_char_ptr + sizeof(char);
BOOST_LOG_TRIVIAL(debug) << "*(const char*)tbl_char_ptr: "
<< *((const char*)tbl_char_ptr);
}
result_ptr = tbl_char_ptr + sizeof(char);
BOOST_LOG_TRIVIAL(debug) << "Tag of entry: " << ((Token*)result_ptr)->tag;
BOOST_LOG_TRIVIAL(debug) << "Location of Token: " << (size_t)result_ptr;
key_ptr = key;
}
return result_ptr;
}
template<class sizeType>
Token* SymbolTable<sizeType>::operator[](const char* key){
BOOST_LOG_TRIVIAL(debug) << "Entering SymbolTable.operator[](const char* key)";
void* void_ptr = find(key);
Token* token_ptr = (Token*)void_ptr;
return token_ptr;
}
這裏是測試程序的源代碼。
int main(){
cout << "Executing testLexer.cpp" << endl;
ifstream file("./pascalPrograms/helloworld.pas");
string program((istreambuf_iterator<char>(file)), istreambuf_iterator<char>());
cout << "program:\n\n" << program << endl;
int fileSize = program.length();
const char* buffer = program.c_str();
const char* scanp = buffer;
cout << "Instantiating Lexer" << endl << endl;
Lexer lexer = Lexer(scanp);
Token* tok;
int i = 0;
cout << "Entering while loop to fetch tags." << endl << endl;
do{
i++;
tok = lexer.getToken();
cout << "The " << i << "th token: " << tok->tag << endl;
} while(tok->tag != END_OF_FILE);
return 0;
}
非常感謝您的幫助！：d
編輯：
這裏是輸入的Pascal程序：
program Hello;
begin
writeln ('Hello, world.');
readln
end.
，並澄清了一個問題：
爲什麼令牌的標籤從符號檢索當符號表中的令牌是原始的精確副本時，是否與放入符號表中的令牌的標記不同？
tl; dr＆沒有問題 – user463035818
@ tobi303問題是，當程序令牌放入符號表中時，它的正確標記爲46，但稍後檢索時，其標記爲1207959598即使包含該標記的符號表中的內存塊與原始標記本身相同。我想在這篇文章中更清楚地說明這個問題，用什麼語言來說明這個問題呢？ –
添加適當的標籤將有助於避免從像我這樣的noobs獲得批評者）（也許'編譯器構造？） – user463035818