hash 링크
7560 단어 알고리즘 과 데이터 구조
hash 체인 시 계 는 hash 시계 와 체인 시계의 결합 으로 사용 하기에 비교적 편리 하 다.
hash 링크 구현
본 논문 의 hash 링크 실현: hash 머리 는 단일 체인 표, 다른 hash 노드 는 양 방향 링크 를 사용 합 니 다.주로 리 눅 스 커 널 에서 이 루어 진 것 을 실현 하고 본 고 는 이식 을 했다.본문 코드http://download.csdn.net/detail/it_pcode / 6632905 다운로드.
hash 실현
#ifndef HLIST_H_
#define HLIST_H_
#include
#include
#include
#include
#include
/* type member ptr, ptr type */
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
/* RAM, */
#define prefetch(x) (x)
/*
* Double linked lists with a single pointer list head.
* Mostly useful for hash tables where the two pointer list head is
* too wasteful.
* You lose the ability to access the tail in O(1).
*/
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
static inline void INIT_HLIST_NODE(struct hlist_node *h) {
h->next = NULL;
h->pprev = NULL;
}
static inline int hlist_unhashed(const struct hlist_node *h) {
return !h->pprev;
}
static inline int hlist_empty(const struct hlist_head *h) {
return !h->first;
}
static inline void __hlist_del(struct hlist_node *n) {
struct hlist_node *next = n->next;
struct hlist_node **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
}
static inline void hlist_del(struct hlist_node *n) {
__hlist_del(n);
n->next = NULL;
n->pprev = NULL;
}
static inline void hlist_del_init(struct hlist_node *n) {
if (!hlist_unhashed(n)) {
__hlist_del(n);
INIT_HLIST_NODE(n);
}
}
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) {
struct hlist_node *first = h->first;
n->next = first;
if (first)
first->pprev = &n->next;
h->first = n;
n->pprev = &h->first;
}
/* next must be != NULL */
static inline void hlist_add_before(struct hlist_node *n,
struct hlist_node *next) {
n->pprev = next->pprev;
n->next = next;
next->pprev = &n->next;
*(n->pprev) = n;
}
static inline void hlist_add_after(struct hlist_node *n,
struct hlist_node *next) {
next->next = n->next;
n->next = next;
next->pprev = &n->next;
if (next->next)
next->next->pprev = &next->next;
}
/*
* Move a list from one list head to another. Fixup the pprev
* reference of the first entry if it exists.
*/
static inline void hlist_move_list(struct hlist_head *old,
struct hlist_head *new) {
new->first = old->first;
if (new->first)
new->first->pprev = &new->first;
old->first = NULL;
}
#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
#define hlist_for_each(pos, head) \
for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
pos = pos->next)
#define hlist_for_each_safe(pos, n, head) \
for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
pos = n)
/**
* hlist_for_each_entry - iterate over list of given type
* @tpos: the type * to use as a loop cursor.
* @pos: the &struct hlist_node to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the hlist_node within the struct.
*/
#define hlist_for_each_entry(tpos, pos, head, member) \
for (pos = (head)->first; \
pos && ({ prefetch(pos->next); 1;}) && \
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
pos = pos->next)
/**
* hlist_for_each_entry_continue - iterate over a hlist continuing after current point
* @tpos: the type * to use as a loop cursor.
* @pos: the &struct hlist_node to use as a loop cursor.
* @member: the name of the hlist_node within the struct.
*/
#define hlist_for_each_entry_continue(tpos, pos, member) \
for (pos = (pos)->next; \
pos && ({ prefetch(pos->next); 1;}) && \
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
pos = pos->next)
/**
* hlist_for_each_entry_from - iterate over a hlist continuing from current point
* @tpos: the type * to use as a loop cursor.
* @pos: the &struct hlist_node to use as a loop cursor.
* @member: the name of the hlist_node within the struct.
*/
#define hlist_for_each_entry_from(tpos, pos, member) \
for (; pos && ({ prefetch(pos->next); 1;}) && \
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
pos = pos->next)
/**
* hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
* @tpos: the type * to use as a loop cursor.
* @pos: the &struct hlist_node to use as a loop cursor.
* @n: another &struct hlist_node to use as temporary storage
* @head: the head for your list.
* @member: the name of the hlist_node within the struct.
*/
#define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
for (pos = (head)->first; \
pos && ({ n = pos->next; 1; }) && \
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
pos = n)
#endif /* HLIST_H_ */
hash 링크 인 스 턴 스
우선 자신의 hash list 초기 화, 키 존재 여부 판정, key 값 찾기 등 함 수 를 실현 합 니 다.그리고 메 인 테스트 프로그램.
#define MAX_LEN 20
struct hash_node {
struct hlist_node hnode;
int age;
};
struct hlist_head hashead[MAX_LEN];
void init_hlist() {
int i = 0;
for (i = 0; i < MAX_LEN; i++) {
INIT_HLIST_HEAD(&hashead[i]);
}
}
int key_exists(struct hlist_head *head, int key) {
struct hash_node * node;
struct hlist_node *hlistnode;
hlist_for_each_entry(node, hlistnode, head,hnode) {
if (node->age == key) {
return 1;
}
}
return 0;
}
struct hash_node * hlist_search(int age) {
struct hash_node *node, *data;
int i = 0;
struct hlist_node *hlistnode;
for (i = 0; i < MAX_LEN; i++) {
hlist_for_each_entry(node, hlistnode, &hashead[i],hnode) {
data = container_of(&node->hnode, struct hash_node, hnode);
if (data->age == age) {
return data;
}
}
}
return NULL;
}
void testhlist() {
init_hlist();
int i = 0;
struct hash_node * node;
struct hlist_node *hlistnode;
srand(time(NULL));
for (i = 0; i < 4 * MAX_LEN; i++) {
node = malloc(sizeof(struct hash_node));
INIT_HLIST_NODE(&node->hnode);
node->age = rand() % (4 * MAX_LEN);
if (key_exists(&hashead[node->age % MAX_LEN], node->age) == 0) {
hlist_add_head(&node->hnode, &hashead[node->age % MAX_LEN]);
}
}
for (i = 0; i < MAX_LEN; i++) {
printf("head %d has member :", i);
hlist_for_each_entry(node, hlistnode, &hashead[i],hnode) {
printf("%d ", node->age);
}
printf("
");
}
for (i = 0; i < MAX_LEN; i++) {
node = hlist_search(i);
if (NULL != node) {
printf("found %d
", i);
hlist_del(&node->hnode);
}
}
printf("after clear
");
for (i = 0; i < MAX_LEN; i++) {
printf("head %d has member :", i);
hlist_for_each_entry(node, hlistnode, &hashead[i],hnode) {
printf("%d ", node->age);
}
printf("
");
}
}
main 함수 에서 주 테스트 프로그램 을 호출 하면 됩 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
데이터 구조의 링크 의 실현글 목록 소개 실현 1. 프로필 동적 배열, 스 택 과 대열 의 바 텀 은 모두 정적 배열 에 의존 하고 resize 로 고정 용량 문 제 를 해결한다.그리고 링크 는 진정한 동적 데이터 구조 이다 2. 실현...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.