nginx 데이터 구조 2 - 레드-블랙 트리를 직접 다시 작성
더 이상 고민할 필요 없이 코드를 다시 작성해 보겠습니다. 이번에는 영어로 작성된 댓글을 영어 리뷰로 사용하겠습니다.
rbtree.h:
/* * Copyright (C) Bipedal Bit * Verson 1.0.0.1 */ #ifndef _RBTREE_H_INCLUDED_ #define _RBTREE_H_INCLUDED_ /* the node structure of the red-black tree */ typedef struct rbtree_node_s rbtree_node_t; /* Using type int means its range is -0x7fffffff-1~0x7fffffff. */ typedef int rbtree_key_t; /* Abstract type is complicated to achieve with C so I use char* instead. */ typedef char* rbtree_data_t; struct rbtree_node_s { /* key of the node */ rbtree_key_t key; /* pointer of the parent of the node */ rbtree_node_t* parent; /* pointer of the left kid of the node */ rbtree_node_t* left; /* pointer of the right kid of the node */ rbtree_node_t* right; /* color of the node */ unsigned char color; /* pointer of the value of the node corresponding to the key */ rbtree_data_t value; }; /* the tree object stucture of the red-black tree */ typedef struct rbtree_s rbtree_t; /* foundational insert function pointer*/ typedef void (*rbtree_insert_p) (rbtree_t* root, rbtree_node_t* node); struct rbtree_s { /* the pointer of the root node of the tree */ rbtree_node_t* root; /* black leaf nodes as sentinel */ rbtree_node_t* sentinel; /* the polymorphic insert function pointer */ rbtree_insert_p insert; }; /* macros */ #define rbtree_init(tree, s, i) \ rbtree_sentinel_init(s); \ (tree)->root = s; \ (tree)->sentinel = s; \ (tree)->insert = i #define rbtree_red(node) ((node)->color = 1) #define rbtree_black(node) ((node)->color = 0) #define rbtree_is_red(node) ((node)->color) #define rbtree_is_black(node) (!rbtree_is_red(node)) /* copy n2's color to n1 */ #define rbtree_copy_color(n1, n2) (n1->color = n2->color) /* sentinel must be black cuz it's leaf node */ #define rbtree_sentinel_init(node) rbtree_black(node) /* statements of public methods */ void rbtree_insert_value(rbtree_t* tree, rbtree_node_t* node); void rbtree_insert(rbtree_t* tree, rbtree_node_t* node); void rbtree_delete(rbtree_t* tree, rbtree_node_t* node); rbtree_node_t* rbtree_find(rbtree_t* tree, rbtree_key_t key); #endif /* _RBTREE_H_INCLUDED_ */
nginx 소스 코드를 읽어보신 분들은 제 헤더 파일이 ngx_rbree.h에 비해 크게 변하지 않았음을 아실 겁니다. 매우 비슷합니다. .
키 rbtree.c:
/* * Copyright (C) Bipedal Bit * Verson 1.0.0.1 */ #include <stddef.h> #include "rbtree.h" /* inline methods */ /* get the node with the minimum key in a subtree of the red-black tree */ static inline rbtree_node_t* rbtree_subtree_min(rbtree_node_t* node, rbtree_node_t* sentinel) { while(node->left != sentinel) { node = node->left; } return node; } /* replace the node "node" in the tree with node "tmp" */ static inline void rbtree_replace(rbtree_t* tree, rbtree_node_t* node, rbtree_node_t* tmp) { /* upward: p[node] <- p[tmp] */     tmp->parent = node->parent; if (node == tree->root) { tree->root = tmp; } else if (node == node->parent->left) { /* downward: left[p[node]] <- tmp */         node->parent->left = tmp; } else { /* downward: right[p[node]] <- tmp */         node->parent->right = tmp; } node->parent = tmp; } /* change the topologic structure of the tree keeping the order of the nodes */ static inline void rbtree_left_rotate(rbtree_t* tree, rbtree_node_t* node) { /* node as the var x in CLRS while tmp as the var y */ rbtree_node_t* tmp = node->right; /* replace y with left[y] */ /* downward: right[x] <- left[y] */     node->right = tmp->left; /* if left[[y] is not NIL it has a parent */ if (tmp->left != tree->sentinel) { /* upward: p[left[y]] <- x */         tmp->left->parent = node; } /* replace x with y */ rbtree_replace(tree, node, tmp); tmp->left = node; } static inline void rbtree_right_rotate(rbtree_t* tree, rbtree_node_t* node) { rbtree_node_t* tmp = node->left; /* replace y with right[y] */ node->left = tmp->right; if (tmp->right != tree->sentinel) { tmp->right->parent = node; } /* replace x with y */ rbtree_replace(tree, node, tmp); tmp->right = node; } /* static methods */ /* fix the red-black tree after the new node inserted */ static void rbtree_insert_fixup(rbtree_t* tree, rbtree_node_t* node) { while(rbtree_is_red(node->parent)) { if (node->parent == node->parent->parent->left) { /* case 1: node's uncle is red */ if (rbtree_is_red(node->parent->parent->right)) { rbtree_black(node->parent); rbtree_black(node->parent->parent->right); rbtree_red(node->parent->parent); node = node->parent->parent; /* Then we can consider the whole subtree */ /* which is represented by the new "node" as the "node" before */ /* and keep looping till "node" become the root. */ } /* case 2: node's uncle is black */ else { /* ensure node is the left kid of its parent */ if (node == node->parent->right) { node = node->parent; rbtree_left_rotate(tree, node); } /* case 2 -> case 1 */ rbtree_black(node->parent); rbtree_red(node->parent->parent); rbtree_right_rotate(tree, node->parent->parent); } } /* same as the "if" clause before with "left" and "right" exchanged */ else { if (rbtree_is_red(node->parent->parent->left)) { rbtree_black(node->parent); rbtree_black(node->parent->parent->left); rbtree_red(node->parent->parent); node = node->parent->parent; } else { if (node == node->parent->left) { node = node->parent; rbtree_right_rotate(tree, node); } rbtree_black(node->parent); rbtree_red(node->parent->parent); rbtree_left_rotate(tree, node->parent->parent); } } } /* ensure the root node being black */ rbtree_black(tree->root); } static void rbtree_delete_fixup(rbtree_t* tree, rbtree_node_t* node) { rbtree_node_t* brother = NULL; while(node != tree->root && rbtree_is_black(node)) { if (node == node->parent->left) { brother = node->parent->right; if (rbtree_is_red(brother)) { rbtree_black(brother); rbtree_red(node->parent); rbtree_left_rotate(tree, node->parent); /* update brother after topologic change of the tree */ brother = node->parent->right; } if (rbtree_is_black(brother->left) && rbtree_is_black(brother->right)) { rbtree_red(brother); /* go upward and keep on fixing color */ node = node->parent; } else { if (rbtree_is_black(brother->right)) { rbtree_black(brother->left); rbtree_red(brother); rbtree_right_rotate(tree, brother); /* update brother after topologic change of the tree */ brother = node->parent->right; } rbtree_copy_color(brother, node->parent); rbtree_black(node->parent); rbtree_black(brother->right); rbtree_left_rotate(tree, node->parent); /* end the loop and ensure root is black */ node = tree->root; } } /* same as the "if" clause before with "left" and "right" exchanged */ else { brother = node->parent->left; if (rbtree_is_red(brother)) { rbtree_black(brother); rbtree_red(node->parent); rbtree_left_rotate(tree, node->parent); brother = node->parent->left; } if (rbtree_is_black(brother->left) && rbtree_is_black(brother->right)) { rbtree_red(brother); node = node->parent; } else { if (rbtree_is_black(brother->left)) { rbtree_black(brother->right); rbtree_red(brother); rbtree_right_rotate(tree, brother); brother = node->parent->left; } rbtree_copy_color(brother, node->parent); rbtree_black(node->parent); rbtree_black(brother->left); rbtree_left_rotate(tree, node->parent); node = tree->root; } } } rbtree_black(node); } /* public methods */ void rbtree_insert_value(rbtree_t* tree, rbtree_node_t* node) { /* Using ** to know wether the new node will be a left kid */ /* or a right kid of its parent node. */ rbtree_node_t** tmp = &tree->root; rbtree_node_t* parent; while(*tmp != tree->sentinel) { parent = *tmp; tmp = (node->key < parent->key) ? &parent->left : &parent->right; } /* The pointer knows wether the node should be on the left side */ /* or on the right one. */ *tmp = node; node->parent = parent; node->left = tree->sentinel; node->right = tree->sentinel; rbtree_red(node); } void rbtree_insert(rbtree_t* tree, rbtree_node_t* node) { rbtree_node_t* sentinel = tree->sentinel; /* if the tree is empty */ if (tree->root == sentinel) { tree->root = node; node->parent = sentinel; node->left = sentinel; node->right = sentinel; rbtree_black(node); return; } /* generally */ tree->insert(tree, node); rbtree_insert_fixup(tree, node); } void rbtree_delete(rbtree_t* tree, rbtree_node_t* node) { rbtree_node_t* sentinel = tree->sentinel; /* wether "node" is on the left side or the right one */ rbtree_node_t** ptr_to_node = NULL; /* "cover" is the node which is going to cover "node" */ rbtree_node_t* cover = NULL; /* wether we lossing a red node on the edge of the tree */ int loss_red = rbtree_is_red(node); int is_root = (node == tree->root); /* get "cover" & "loss_red" */ /* sentinel in "node"'s kids */ if (node->left == sentinel) { cover = node->right; } else if (node->right == sentinel) { cover = node->left; } /* "node"'s kids are both non-sentinel */ else { /* update "node" & "loss_red" & "is_root" & "cover" */ cover = rbtree_subtree_min(node->right, sentinel); node->key = cover->key; node->value = cover->value; node = cover; loss_red = rbtree_is_red(node); is_root = 0; /* move "cover"'s kids */ /* "cover" can only be a left kid */ /* and can only have a right non-sentinel kid */ /* because of function "rbtree_subtree_min" */ cover = node->right; } if (is_root) { /* update root */ tree->root = cover; } else { /* downward link */ if (node == node->parent->left) { node->parent->left = cover; } else { node->parent->right = cover; } } /* upward link */ cover->parent = node->parent; /* "cover" may be a sentinel */ if (cover != sentinel) { /* set "cover" */ cover->left = node->left; cover->right = node->right; rbtree_copy_color(cover, node); } /* clear "node" since it's useless */ node->key = -1; node->parent = NULL; node->left = NULL; node->right = NULL; node->value = NULL; if (loss_red) { return; } /* When lossing a black node on edge */ /* the fifth rule of red-black tree will be broke. */ /* So the tree need to be fixed. */ rbtree_delete_fixup(tree, cover); } /* find the node in the tree corresponding to the given key value */ rbtree_node_t* rbtree_find(rbtree_t* tree, rbtree_key_t key) { rbtree_node_t* tmp = tree->root; int step_cnt = 0; /* search the binary tree */ while(tmp != tree->sentinel) { /* next line is just fot test */ // step_cnt++; if(key == tmp->key) { /* next line is just for test */ // printf("step count: %d, color: %s, ", step_cnt, rbtree_is_red(tmp) ? "red" : "black"); return tmp; } tmp = (key < tmp->key) ? tmp->left : tmp->right; } return NULL; }
nginx 소스 코드에서 100줄 이상의 긴 함수 본문도 너무 많은 함수를 피하기 위한 최적화라는 것을 알고 있지만 시간과 공간의 오버헤드를 증가시키는 호출에도 불구하고 나는 여전히 모든 기능을 100줄 미만으로 분류하고 나눕니다. 가독성을 높이는 것이 한 가지이지만 약간 강박적일 수도 있습니다. 이후에는 max, min, mid 등 여러 통계 방법이 확장되고 순회 방법도 확장됩니다.
다음은 호출 테스트 test.c입니다.
#include <stdio.h> #include "rbtree.h" int main(int argc, char const *argv[]) { rbtree_t t = {}; rbtree_node_t s = {}; rbtree_init(&t, &s, rbtree_insert_value); const int cnt = 10; const int max_len = 15; #define TEST_VALUES {"apple", "banana", "cherry", "grape", "lemon", "mango", "pear", "pineapple", "strawberry", "watermelon"} /* for gcc */ char* v[] = TEST_VALUES; /* for g++ */ // char v[][max_len] = TEST_VALUES; rbtree_node_t n[cnt]; int i; for (i = 0; i < cnt; i++)     {         n[i].key = i+1;         n[i].value = v[i];         rbtree_insert(&t, &n[i]);     }     rbtree_node_t* p[cnt];     for (i = 1; i <= cnt; i++)     {         printf("key: %d\n", i);         p[i] = rbtree_find(&t, i);         printf("value: %s\n", (p[i] != NULL) ? p[i]->value : "?"); } rbtree_delete(&t, &n[5]); printf("\nafter delete 6->mango:\n\n"); for (i = 1; i <= cnt; i++)     {         printf("key: %d\n", i);         p[i] = rbtree_find(&t, i);         printf("value: %s\n", (p[i] != NULL) ? p[i]->value : "?"); } return 0; }
rbtree_find 메소드에서 테스트 줄 주석을 잠금 해제하고 원활하게 실행합니다.
key: 1 step count: 3, color: black, value: apple key: 2 step count: 2, color: black, value: banana key: 3 step count: 3, color: black, value: cherry key: 4 step count: 1, color: black, value: grape key: 5 step count: 3, color: black, value: lemon key: 6 step count: 2, color: black, value: mango key: 7 step count: 4, color: black, value: pear key: 8 step count: 3, color: red, value: pineapple key: 9 step count: 4, color: black, value: strawberry key: 10 step count: 5, color: red, value: watermelon after delete 6->mango: key: 1 step count: 3, color: black, value: apple key: 2 step count: 2, color: black, value: banana key: 3 step count: 3, color: black, value: cherry key: 4 step count: 1, color: black, value: grape key: 5 step count: 3, color: black, value: lemon key: 6 value: ? key: 7 step count: 2, color: black, value: pear key: 8 step count: 4, color: black, value: pineapple key: 9 step count: 3, color: red, value: strawberry key: 10 step count: 4, color: black, value: watermelon
아래에서 해보겠습니다. 많은 양의 데이터를 사용한 스트레스 테스트입니다. rbtree_find 메서드에서 테스트 줄을 주석으로 처리하지 않으면 결과가 무서울 수 있습니다.
#include <stdio.h> #include <stdlib.h> #include <time.h> #include "rbtree.h" int main(int argc, char const *argv[]) { double duration; double room; rbtree_t t = {}; rbtree_node_t s = {}; rbtree_init(&t, &s, rbtree_insert_value); const int cnt = 1<<20; const int max_len = 15; #define TEST_VALUES {"apple", "banana", "cherry", "grape", "lemon", "mango", "pear", "pineapple", "strawberry", "watermelon"} /* for gcc */ char* v[] = TEST_VALUES; /* for g++ */ // char v[][max_len] = TEST_VALUES; /* Default stack size in Ubuntu Kylin 14.04 is 8MB. */ /* It's not enough. So I use memory in heap which offers a lot larger room. */ rbtree_node_t* n = (rbtree_node_t*)calloc(cnt, sizeof(rbtree_node_t)); int i; long time1 = clock(); for (i = 0; i < cnt; i++) { n[i].key = i+1; n[i].value = v[i%10]; rbtree_insert(&t, &n[i]); } long time2 = clock(); room = 48.0*cnt/(1<<20); duration = (double)(time2 - time1) / CLOCKS_PER_SEC; printf("Inserting %d nodes costs %.2fMB and spends %f seconds.\n", cnt, room, duration); const int search_cnt = 1<<10; srand( (unsigned int)time(0) ); for( i = 0 ; i < search_cnt ; i++ ) { rbtree_find(&t, (rand()%cnt)+1); } long time3 = clock(); duration = (double)(time3 - time2) / CLOCKS_PER_SEC; printf("Searching %d nodes among %d spends %f seconds.\n", search_cnt, cnt, duration); const int delete_cnt = 1<<10; int nums[delete_cnt]; int num; /* Let's hash! */ char* mark = (char*)calloc(cnt, sizeof(char)); memset(mark, 0, cnt*sizeof(char)); for(i = 0; i < delete_cnt; i++) { for(;;) { num = rand()%cnt; if (mark[num] == 0) { mark[num] = 1; nums[i] = num; break; } } } long time4 = clock(); duration = (double)(time4 - time3) / CLOCKS_PER_SEC; printf("Hash %d times spends %f seconds.\n", delete_cnt, duration); for(i = 0; i < delete_cnt; i++) { rbtree_delete(&t, &n[nums[i]]); } long time5 = clock(); duration = (double)(time5 - time4) / CLOCKS_PER_SEC; printf("Deleting %d nodes among %d spends %f seconds.\n", delete_cnt, cnt, duration); free(mark); free(n); return 0; }
결과를 살펴보겠습니다.
Inserting 1048576 nodes costs 48.00MB and spends 0.425416 seconds. Searching 1024 nodes among 1048576 spends 0.001140 seconds. Hash 1024 times spends 0.000334 seconds. Deleting 1024 nodes among 1048576 spends 0.000783 seconds.
통계 및 순회 방법을 작성해 보겠습니다.
저작권 안내: 이 글은 해당 블로거의 원본 글이므로 블로거의 허락 없이 복제할 수 없습니다.
위 내용은 nginx 데이터 구조 2 - 관련 내용을 포함하여 직접 레드-블랙 트리를 다시 작성하는 방법을 소개합니다. PHP 튜토리얼에 관심이 있는 친구들에게 도움이 되기를 바랍니다.

핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

AI Hentai Generator
AI Hentai를 무료로 생성하십시오.

인기 기사

뜨거운 도구

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

드림위버 CS6
시각적 웹 개발 도구

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)

뜨거운 주제











nvm을 사용하여 노드를 삭제하는 방법: 1. "nvm-setup.zip"을 다운로드하여 C 드라이브에 설치합니다. 2. "nvm -v" 명령을 통해 환경 변수를 구성하고 버전 번호를 확인합니다. install" 명령 노드 설치; 4. "nvm uninstall" 명령을 통해 설치된 노드를 삭제합니다.

파일 업로드를 처리하는 방법은 무엇입니까? 다음 글에서는 Express를 사용하여 노드 프로젝트에서 파일 업로드를 처리하는 방법을 소개하겠습니다. 도움이 되길 바랍니다.

이 기간 동안 저는 Tencent 문서의 모든 카테고리에 공통되는 HTML 동적 서비스를 개발 중입니다. 다양한 카테고리에 대한 액세스 생성 및 배포를 촉진하고 클라우드로 이동하는 추세에 부응하기 위해. Docker를 사용하여 서비스 콘텐츠를 수정하고 제품 버전을 균일하게 관리합니다. 이 글에서는 제가 Docker를 서비스하면서 쌓은 최적화 경험을 여러분의 참고용으로 공유하겠습니다.

이 기사에서는 Node의 프로세스 관리 도구인 "pm2"를 공유하고 pm2가 필요한 이유, pm2 설치 및 사용 방법에 대해 설명합니다. 모두에게 도움이 되기를 바랍니다!

Pinetwork 노드에 대한 자세한 설명 및 설치 안내서이 기사에서는 Pinetwork Ecosystem을 자세히 소개합니다. Pi 노드, Pinetwork 생태계의 주요 역할을 수행하고 설치 및 구성을위한 전체 단계를 제공합니다. Pinetwork 블록 체인 테스트 네트워크가 출시 된 후, PI 노드는 다가오는 주요 네트워크 릴리스를 준비하여 테스트에 적극적으로 참여하는 많은 개척자들의 중요한 부분이되었습니다. 아직 Pinetwork를 모른다면 Picoin이 무엇인지 참조하십시오. 리스팅 가격은 얼마입니까? PI 사용, 광업 및 보안 분석. Pinetwork 란 무엇입니까? Pinetwork 프로젝트는 2019 년에 시작되었으며 독점적 인 Cryptocurrency Pi Coin을 소유하고 있습니다. 이 프로젝트는 모든 사람이 참여할 수있는 사람을 만드는 것을 목표로합니다.

nodejs 실행 파일을 pkg로 패키징하는 방법은 무엇입니까? 다음 기사에서는 pkg를 사용하여 Node 프로젝트를 실행 파일로 패키징하는 방법을 소개합니다. 도움이 되기를 바랍니다.

객체 지향 프로그래밍에서 상속을 사용하면 기존 클래스의 속성과 메서드를 상속하는 새 클래스를 만들 수 있습니다. 이 강력한 개념은 프로그램의 코드 재사용, 모듈성 및 확장성을 가능하게 합니다. 상위 클래스 속성에 액세스하기 전에 먼저 살펴보겠습니다.

인증은 모든 웹 애플리케이션에서 가장 중요한 부분 중 하나입니다. 이 튜토리얼에서는 토큰 기반 인증 시스템과 기존 로그인 시스템과의 차이점에 대해 설명합니다. 이 튜토리얼이 끝나면 Angular와 Node.js로 작성된 완벽하게 작동하는 데모를 볼 수 있습니다. 기존 인증 시스템 토큰 기반 인증 시스템으로 넘어가기 전에 기존 인증 시스템을 살펴보겠습니다. 사용자는 로그인 양식에 사용자 이름과 비밀번호를 입력하고 로그인을 클릭합니다. 요청한 후 데이터베이스를 쿼리하여 백엔드에서 사용자를 인증합니다. 요청이 유효하면 데이터베이스에서 얻은 사용자 정보를 이용하여 세션을 생성하고, 세션 정보를 응답 헤더에 반환하여 브라우저에 세션 ID를 저장한다. 다음과 같은 애플리케이션에 대한 액세스를 제공합니다.
