Generic Hash 타입 설계

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

h->first 가 포인터이기때문에 이것을 가리키기 위해서 이중 포인터를 사용함.

first 는 기존 노드를 가리킴. 그래서 새로운 노드가 들어왔을떄.

n->next = first; 했을 때 같은 곳을 가리킴

first->pprev . first가 기존 노드를 가리키는 포인터이므로 first->pprev 는 &n->next를 가리킴

노드가 오든 포인터이든 둘 다 가리킬 수 있음. 

 

sturct hlist_node *first = h->first; next, pprev 를 따로 쓰지 않고, 가리키는 위치는 next임.

 

#include <stdio.h>
#include <stdlib.h>

struct hlist_head {
	struct hlist_node* first;
};

struct hlist_node {
	struct hlist_node* next, ** pprev;
};

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;
}
/*
#define offsetof(TYPE, MEMBER)	((size_t)&((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) ({                      \
	const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
	(type *)( (char *)__mptr - offsetof(type,member) );})
//-------------------------------------------------
*/

#define  container_of(ptr, type, member) (type*)((char*)ptr-(unsigned long)&((type*)0)->member)
#define  HASH_MAX   8

typedef struct
{
	int sno;
	struct hlist_node hash;
} SAWON;

int hash_sno(int sno)
{
	return sno % HASH_MAX;
}

void display(struct hlist_head* heads)
{
	int i;
	struct hlist_node* temp;
	SAWON* s;
	system("clear");
	for (i = 0; i < HASH_MAX; i++)
	{
		printf("[%d]", i);
		for (temp = heads[i].first; temp; temp = temp->next)
		{
			s = container_of(temp, SAWON, hash);
			printf("<->[%d]", s->sno);
		}
		printf("\n");
	}
	getchar();
}

int main()
{
	struct hlist_head heads[HASH_MAX] = { 0, };
	SAWON s[30] = { 0, };
	int i;
	int sno;

	display(heads);
	for (i = 0; i < 30; i++)
	{
		sno = 1000 + i;
		s[i].sno = sno;
		hlist_add_head(&s[i].hash, &heads[hash_sno(sno)]);
		display(heads);
	}
	return 0;
}