Generic Hash 2

1000, 1096 % 8 은

2진수로 하였을 때 뒷자리 3개로 결정하게 됨.

pid를 8개의 버킷으로 분리하겠다는 의미임.

 

그럼 항상 저 GOLDEN_RATIO_PRIME_32 를 사용해서 hash 값을 구하면 좋은 것인가?

언제 사용 할 수 있는지.

#include <stdio.h>

#define GOLDEN_RATIO_PRIME_32 0x9e370001UL


int main()
{
	unsigned long long hash = 3 * GOLDEN_RATIO_PRIME_32;
	printf("%llu\n%lu", hash, GOLDEN_RATIO_PRIME_32);

	long long var = 0x1234567812345678;
	printf("\n%llu", var);
	return 0;
}

 

#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 long)&((type*)0)->member)

#define  HASH_MAX   8

#define GOLDEN_RATIO_PRIME_32 0x9e370001UL

unsigned int hash_32(unsigned int val, unsigned int bits)
{
	unsigned int hash = val * GOLDEN_RATIO_PRIME_32;
	return hash >> (32 - bits);
}

#define pid_hashfn(pid)  \
	    hash_32( pid, 3 )    

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

int hash_sno(int sno)
{
	return hash_32(sno, 3);
}

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