nginx hash 구조
ngx_int_t
ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts)
{
u_char *elts;
size_t len;
u_short *test;
ngx_uint_t i, n, key, size, start, bucket_size;
ngx_hash_elt_t *elt, **buckets;
/* nginx hash :
hash N , N ( <k,v>), ,
N , ngx_hash_elt_t
ngx_hash_elt_t .
:
: hash , , .
hash , , hash .
nginx hash :
ngx_hash_init_t.bucket_size ;
.
, ( hash % )
, , , ,
, ngx_hash_init_t.hash.buckets .
= + void
, .
ngx_hash_init_t.hash.buckets .
.
" " NULL
void : , ngx_hash_find() etl->value NULL .
" " void* ngx_hash_elt_t ?
, void* ngx_hash_elt_t ngx_hash_elt_t.value ,
ngx_hash_elt_t.value void .
: , .
*/
/* + void ,
*/
for (n = 0; n < nelts; n++) {
if (hinit->bucket_size < NGX_HASH_ELT_SIZE(&names[n]) + sizeof(void *))
{
ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
"could not build the %s, you should "
"increase %s_bucket_size: %i",
hinit->name, hinit->name, hinit->bucket_size);
return NGX_ERROR;
}
}
/* */
test = ngx_alloc(hinit->max_size * sizeof(u_short), hinit->pool->log);
if (test == NULL) {
return NGX_ERROR;
}
bucket_size = hinit->bucket_size - sizeof(void *);
/*
NGX_HASH_ELT_SIZE(&name[n]) > (2*sizeof(void*))
bucket_size bucket_size/(2*sizeof(void*))
nelts start 。
*/
start = nelts / (bucket_size / (2 * sizeof(void *)));
start = start ? start : 1;
if (hinit->max_size > 10000 && hinit->max_size / nelts < 99) {
start = hinit->max_size - 1000;
}
/* , nelts */
for (size = start; size < hinit->max_size; size++) {
ngx_memzero(test, size * sizeof(u_short));
for (n = 0; n < nelts; n++) {
if (names[n].key.data == NULL) {
continue;
}
key = names[n].key_hash % size;
test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
#if 0
ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
"%ui: %ui %ui \"%V\"",
size, key, test[key], &names[n].key);
#endif
if (test[key] > (u_short) bucket_size) { /* size , nelts */
goto next;
}
}
goto found;
next:
continue;
}
ngx_log_error(NGX_LOG_EMERG, hinit->pool->log, 0,
"could not build the %s, you should increase "
"either %s_max_size: %i or %s_bucket_size: %i",
hinit->name, hinit->name, hinit->max_size,
hinit->name, hinit->bucket_size);
ngx_free(test);
return NGX_ERROR;
found:
/* nelts size */
for (i = 0; i < size; i++) {
test[i] = sizeof(void *); /* */
}
for (n = 0; n < nelts; n++) {
if (names[n].key.data == NULL) {
continue;
}
key = names[n].key_hash % size; /* N */
test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n])); /* n */
}
len = 0;
/* cacheline */
for (i = 0; i < size; i++) {
if (test[i] == sizeof(void *)) { /* */
continue;
}
test[i] = (u_short) (ngx_align(test[i], ngx_cacheline_size));
len += test[i];
}
/* hash NULL, ngx_hash_wildcard_t ,
ngx_hash_init_t ngx_hash_t.
ngx_hash_wildcard_t .
*/
if (hinit->hash == NULL) {
hinit->hash = ngx_pcalloc(hinit->pool, sizeof(ngx_hash_wildcard_t)
+ size * sizeof(ngx_hash_elt_t *));
if (hinit->hash == NULL) {
ngx_free(test);
return NGX_ERROR;
}
/* */
buckets = (ngx_hash_elt_t **)
((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t));
} else {
/* */
buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *));
if (buckets == NULL) {
ngx_free(test);
return NGX_ERROR;
}
}
elts = ngx_palloc(hinit->pool, len + ngx_cacheline_size);
if (elts == NULL) {
ngx_free(test);
return NGX_ERROR;
}
elts = ngx_align_ptr(elts, ngx_cacheline_size);
for (i = 0; i < size; i++) {
if (test[i] == sizeof(void *)) {
continue;
}
/* */
buckets[i] = (ngx_hash_elt_t *) elts;
elts += test[i];
}
for (i = 0; i < size; i++) {
test[i] = 0;
}
for (n = 0; n < nelts; n++) {
if (names[n].key.data == NULL) {
continue;
}
/* names ngx_hash_elt_t ,
names ngx_hash_elt_t .
*/
key = names[n].key_hash % size;
elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]);
elt->value = names[n].value;
elt->len = (u_short) names[n].key.len;
ngx_strlow(elt->name, names[n].key.data, names[n].key.len);
test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));
}
/* NULL */
for (i = 0; i < size; i++) {
if (buckets[i] == NULL) {
continue;
}
elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]);
elt->value = NULL;
}
ngx_free(test);
hinit->hash->buckets = buckets;
hinit->hash->size = size;
#if 0
for (i = 0; i < size; i++) {
ngx_str_t val;
ngx_uint_t key;
elt = buckets[i];
if (elt == NULL) {
ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
"%ui: NULL", i);
continue;
}
while (elt->value) {
val.len = elt->len;
val.data = &elt->name[0];
key = hinit->key(val.data, val.len);
ngx_log_error(NGX_LOG_ALERT, hinit->pool->log, 0,
"%ui: %p \"%V\" %ui", i, elt, &val, key);
elt = (ngx_hash_elt_t *) ngx_align_ptr(&elt->name[0] + elt->len,
sizeof(void *));
}
}
#endif
return NGX_OK;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Application Development in WebOSDevelop applications in WebOS Recognize the abstract class Application The operating system accepts classes that impleme...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.