C 数据库中的通用查找函数

Question

所以我正在尝试使用哈希表在 C 中创建一个数据库（其中我的哈希表只是一个带有空指针的链表数组）。我也在尝试使用 void 指针使其 "generic" 但我不知道如何使用 void 指针进行查找和删除。例如，我有一个名为 CSG（Course StudentID Grade）的元组，定义为

typedef struct CSG {
  char Course[6];
  int StudentId;
  char Grade[2];
  int (*hash)(int StudentId);
}CSG;

函数指针只是指向我写的一个简单的散列函数。

目前 CSG 的查找函数是

LinkedList*  lookup_CSG(hashtable* db,int StudentId, char* Grade, char* Course){
    LinkedList* ret=new_LinkedList();
    if(StudentId!=0){
        ListNode* curr=db->table[int_hash(StudentId)]->head;
        while(curr!=NULL){
            CSG* currentCSG=(CSG*)curr->data;
            if(currentCSG->StudentId==StudentId){
                append(ret, currentCSG);
                return ret;
            }
            else{
                curr=curr->next;
            }
        }
    }
    else if(Grade[0]!='*'&&Course[0]!='*'){
        for(int i=0;i<1009;i++){
            ListNode* curr=db->table[i]->head;
            if(curr==NULL){
                continue;
            }
            while(curr!=NULL){
                if(curr==NULL){
                    break;
                }
                CSG* currentCSG=(CSG*)curr->data;
                if(currentCSG==NULL){
                    break;
                }
                if(strcmp(Grade, currentCSG->Grade)==0&&strcmp(Course, currentCSG->Course)==0){
                    append(ret, currentCSG);
                }
                curr=curr->next;
            }
        }
    }
    else if(Grade[0]!='*'){
        for(int i=0;i<1009;i++){
            ListNode* curr=db->table[i]->head;
            if(curr==NULL){
                continue;
            }
            while(curr!=NULL){
                if(curr==NULL){
                    break;
                }
                CSG* currentCSG=(CSG*)curr->data;
                if(currentCSG==NULL){
                    break;
                }
                if(strcmp(Grade, currentCSG->Grade)==0){
                    append(ret, currentCSG);
                }
                curr=curr->next;
            }
        }
    }
    else if(Course[0]!='*'){
        for(int i=0;i<1009;i++){
            ListNode* curr=db->table[i]->head;
            if(curr==NULL){
                continue;
            }
            while(curr!=NULL){
                if(curr==NULL){
                    break;
                }
                CSG* currentCSG=(CSG*)curr->data;
                if(currentCSG==NULL){
                    break;
                }
                if(strcmp(Course, currentCSG->Course)==0){
                    append(ret, currentCSG);
                }
                curr=curr->next;
            }
        }
    }
    return ret;
}

其中 " * " 或 0 char if 省略某个参数，即如果您调用 lookup_CSG(db,0 "A-","*") 将 return 一个所有元组的链接列表，其中成绩是A-.

效果很好，但是对于这个模型，我将不得不为每个元组编写一个特定的查找和删除函数。有谁知道我是否可以创建 "generic" 查找函数。当我尝试这个时，我运行遇到了麻烦，因为每个元组都有不同的属性，所以比较和转换都会不同。查找函数也会根据元组采用不同的参数。谢谢！

Answer 1

有两种方法可以解决这个问题：

对所有值类型和参数使用void*，或
编写一组宏，为所有输入类型生成强类型散列table（就像在klib中所做的那样）。

对于第一种方法，您将需要两个接受 void* 的函数指针，它们可以使用以下类型定义：

// returns a 32-bit hash value for the specified key
typedef int32_t (*HashGetterFn)(const void*);

// return 'true' if two parameters are equal
typedef bool (*EqualityFn)(const void*, const void*);

// you can also place these in a struct
typedef struct 
{
    HashGetterFn getHash;
    EqualityFn equals;
}
HashFuncs;

这允许您对任何您喜欢的键使用相同的函数签名，尽管您必须在您的函数中通过引用传递它。

因此，如果您的密钥是 int，您将编写这两个函数：

// a hash implementation for int keys
static int32_t int_hash(const void * input)
{
     // cast the void pointer to the actual key pointer
     const int * value = (const int *)input;

     // dereference it and calculate the hash
     return (int32_t)*value;
}

static bool int_equals(const void * a, const void * b)
{
     // cast the void pointers to actual key pointers
     const int * aval = (const int *)a;
     const int * bcal = (const int *)b;

     // dereference and compare
     return *aval == *bval;
}

// and then you use it somewhere
void some_function(int *item)
{
    // wrap these two functions
    HashFuncs hashfn = { .getHash = int_hash, .equals = int_equals };

    // create a hashtable which will use them 
    HashTable hashtable = hashtable_create(hashfn);

    // add a key/value pair
    hashtable_add(&hashtable, (void*)item);
}

您可能已经注意到两个问题：

您的值需要具有静态持续时间或在堆上分配，因为它们是通过引用传递的。或者，您还需要将结构的大小传递给散列 table 并将其所有函数 memcpy 每个结构实例的 value 到内部 table .
没有什么能阻止您将完全错误的值传递给散列 table 函数，因为它们接受 void 指针以允许它们使用任何类型。这意味着当您的哈希函数之一取消引用错误的指针类型时，编译没有问题的函数可能会在运行时失败。

为了缓解这种情况，klib is to use the preprocessor to generate a list of strongly typed functions and structs for each specific key/value pair you want to use. This approach is also not perfect; it's a pain to write and test there numerous multi-line macros 采取了这种方法，但由于该库已经编写完毕，您不妨重用它。

这基本上是泛型编程在许多现代语言（C++ 中的模板、C# 中的泛型或 Java）中优雅修复的问题之一。

C 数据库中的通用查找函数

Generic Lookup Function in C database

c

database

generic-programming

void-pointers