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