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

Question

所以我尝试使用哈希表在 C 中创建一个数据库(其中我的哈希表只是一个带有 void 指针的 LinkedList 数组)。我还尝试使用 void 指针使其成为“通用”，但我不知道如何使用 void 指针进行查找和删除。例如，我有一个名为 CSG(类(class) 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 字符用于省略某个参数，即如果您调用 lookup_CSG(db,0 "A-","* ") 将返回所有等级为 A- 的元组的链表。

这工作得很好，但是对于这个模型，我必须为每个元组编写一个特定的查找和删除函数。有谁知道是否有一种方法可以创建“通用”查找函数。当我尝试这样做时，我遇到了麻烦，因为每个元组都有不同的属性，因此比较会有所不同，铸件也会有所不同。查找函数还将根据元组采用不同的参数。谢谢!

Answer 1

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

1. 对所有值类型和参数使用 void*，或者
2. 编写一堆宏，为所有输入类型生成强类型哈希表(就像 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;

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

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

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

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

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

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

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