C 利用 uthash 快速做一些题目

18322

发布于未知归属地

uthash hash 表快速操作

add/replace
find
delete
count
iterate
sort

uthash 已经集成到最新的GCC

https://github.com/troydhanson/uthash
http://troydhanson.github.io/uthash/
http://troydhanson.github.io/uthash/userguide.html

csdn:
https://blog.csdn.net/houjixin/article/details/15809825
https://blog.csdn.net/houjixin/article/details/15810153

构建 hash

struct hash_entry {
    int id;            /* we'll use this field as the key */
    char name[10];
    UT_hash_handle hh; /* makes this structure hashable */
};
struct hash_entry *head = NULL;

key为int

对应的查找宏：

struct hash_entry * tmp; 
HASH_FIND_INT(head,&key,tmp)

没有找到tmp为NULL，找到就指向对应hash点

添加宏

HASH_ADD_INT(head,id,tmp);

在hash中KEY值唯一，在添加时需要先查找，没找到就构建一个新的，如果存在就需要创建新的值

HASH_REPLACE宏等价于HASH_ADD宏，只是它们首先尝试查找和删除项。如果它发现并删除一个项，它还将返回该项指针作为输出参数。

删除宏从head hash表中删除user结点

HASH_DEL(head,user);

利用hash中的迭代器进行删除所有和打印

void delete_all(struct hash_entry * head)
{
  struct hash_entry *current_user, *tmp;

  HASH_ITER(hh, head, current_user, tmp)
  {
        printf("id:%d,name:%s\n",tmp->id,tmp->name);
        HASH_DEL(users,current_user);  /* delete; users advances to next */
        free(current_user);            /* optional- if you want to free  */
  }
}

或者通过hh.next指针遍历hash表中的所有items。

void print_all(struct hash_entry * head)
{
  struct hash_entry  *tmp;

  for(tmp=head;tmp!=NULL;tmp=(struct hash_entry *)tmp->hh.next)
  {
    printf("id:%d,name:%s\n",tmp->id,tmp->name);
  }
}

排序
排序函数与快排qsort 比较函数差不多

int sort_function(void *a,void *b)
{
  /* compare a to b (cast a and b appropriately)
   * return (int) -1 if (a < b)  或者 return (int) a-b 升序
   * return (int)  0 if (a == b)
   * return (int)  1 if (a > b)        return（int)b-a 降序
   */
}


int name_sort(struct hash_entry * a,struct hash_entry * b)
{
    return strcmp(a->name,b->name);
}


int name_id(struct hash_entry * a,struct hash_entry * b)
{
    return strcmp(a->id - b->id);
}



void sort_by_name()
{
    HASH_SORT(head,name_sort);
}

key为char *

当你的结构体使用的是指针方式，那么你应当使用 HASH_ADD_KEYPTR 方法；当你使用的数组方式，则需要使用 HASH_ADD_STR 方法。

字符数组为key


struct hash_entry {
    char name[10];             /* key (string is WITHIN the structure) */
    int id;
    UT_hash_handle hh;         /* makes this structure hashable */
};


int test() {
    const char *names[] = { "joe", "bob", "betty", NULL };
    struct hash_entry *s, *tmp, *users = NULL;

    for (int i = 0; names[i]; ++i) {
        s = (struct hash_entry *)malloc(sizeof *s);
        strcpy(s->name, names[i]);
        s->id = i;
        HASH_ADD_STR( users, name, s );
    }

    HASH_FIND_STR( users, "betty", s);
    if (s) printf("betty's id is %d\n", s->id);

    /* free the hash table contents */
    HASH_ITER(hh, users, s, tmp) {
      HASH_DEL(users, s);
      free(s);
    }
    return 0;
}

字符指针为key

struct hash_entry {
    char * name;             /* key (string is WITHIN the structure) */
    int id;
    UT_hash_handle hh;         /* makes this structure hashable */
};


int test() {
    const char *names[] = { "joe", "bob", "betty", NULL };
    struct hash_entry *s, *tmp, *users = NULL;

    for (int i = 0; names[i]; ++i) {
        s = (struct hash_entry *)malloc(sizeof *s);
        s->name = names[i];
        s->id = i;
        HASH_ADD_KEYPTR(hh, users, s->name,strlen(s->name), s );
    }

    HASH_FIND_STR( users, "betty", s);
    if (s) printf("betty's id is %d\n", s->id);

    /* free the hash table contents */
    HASH_ITER(hh, users, s, tmp) {
      HASH_DEL(users, s);
      free(s);
    }
    return 0;
}

指针为key


struct hash_entry {
    void * key;             /* key (string is WITHIN the structure) */
    int i;
    UT_hash_handle hh;         /* makes this structure hashable */
};

struct hash_entry * head =NULL;
char *someaddr =NULL;

int test() {
    struct hash_entry *s;
    struct hash_entry *tmp=(struct hash_entry*)malloc（sizeof(struct hash_entry);
    if(!tmp) return -1;
    tmp->key =(void*)someaddr;
    tmp->i =1;


    HASH_ADD_PTR(hash,key,tmp);
    HASH_FIND_STR( hash, &someaddr, s);
    if (s) printf("found\n");

    /* free the hash table contents */
 
    HASH_DEL(head, tmp);
    free(tmp);

    return 0;
}

暂无评论