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

Question

所以我试图在 C 中使用哈希表创建一个数据库(其中我的 hastable 只是一个带有空指针的 LinkedLists 数组)。我也在尝试使用 void 指针使其“通用”，但我不知道如何使用 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 如果省略某个参数，即如果您调用 lookup_CSG(db,0 "A-","*")将返回等级为 A- 的所有元组的链表。

哪个工作正常，但使用此模型，我必须为每个元组编写特定的查找和删除函数。有谁知道是否有一种方法可以创建“通用”查找功能。当我尝试这个时我遇到了麻烦，因为每个元组都有不同的属性，所以比较会和类型转换不同。查找函数还将根据元组采用不同的参数。谢谢!

Answer 1

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

使用 void*对于所有值类型和参数，或

编写一堆宏，这些宏将为所有输入类型生成强类型哈希表(就像在 klib 中所做的那样)。

对于第一种方法，您需要两个接受 void* 的函数指针。 , 可以使用以下方式进行 typedef:

// 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;

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

因此，如果您的 key 是 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);
}

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

您的值需要具有静态持续时间或在堆上分配，因为它们是通过引用传递的。或者，您还需要将 struct 的大小传递给哈希表，并将其所有函数 memcpy 将每个 struct 实例的值放入内部表中。

没有什么可以阻止您将完全错误的值传递给哈希表函数，因为它们接受 void指针以允许它们使用任何类型。这意味着编译没有问题的函数可能会在运行时失败，当您的哈希函数之一取消引用错误的指针类型时。

为了缓解这种情况， klib 采取的方法是使用预处理器为您要使用的每个特定键/值对生成强类型函数和结构的列表。这种方法也不是完美的；在那里编写和测试很痛苦 multi-line macros ，但既然这个库已经写好了，你不妨重用它。

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