いつもの副業マニアのスタイルを引き継いで、当初構想していた赤黒ツリー拡張版を一晩で完成させました。
rbtree.h:
/* * Copyright (C) Bipedal Bit * Verson 1.0.0.2 */ #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; /* count of nodes in the subtree whose root is the current node */ int node_cnt; }; /* 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); /* foundational visit function pointer */ typedef void (*rbtree_visit_p) (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); \ (node)->node_cnt = 0 /* 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); /* get node by key */ rbtree_node_t* rbtree_find(rbtree_t* tree, rbtree_key_t key); /* get node by order number */ rbtree_node_t* rbtree_index(rbtree_t* tree, int index); int rbtree_height(rbtree_t* tree, rbtree_node_t* node); int rbtree_count(rbtree_t* tree); void rbtree_visit(rbtree_node_t* node); void rbtree_traversal(rbtree_t* tree, rbtree_node_t* node, rbtree_visit_p); #endif /* _RBTREE_H_INCLUDED_ */シリアル番号によるノードの検索、ツリーの高さの検索、ノードの数の検索、ノードへのアクセスのトラバーサル メソッドの書き換えなど、いくつかの機能を追加していることがわかります。
シリアル番号によるノードの検索効率を向上させるために、現在のノードがルートであるサブツリー上のノードの総数を表すノード項目node_cntを追加しました。このように、シリアル番号によるノードの検索プロセスは二分探索となり、時間効率はキーによる検索と同じ O(log2n) になります。
走査方法は再帰的な順序走査を使用します。デフォルトのノードアクセス方法は空のメソッドであり、ユーザーが自分で書き換えることができます。
rbtree.c:
/* * Copyright (C) Bipedal Bit * Verson 1.0.0.2 */ #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] parent = node->parent; if (node == tree->root) { tree->root = tmp; } else if (node == node->parent->left) { /* downward: left[p[node]] parent->left = tmp; } else { /* downward: right[p[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; /* fix node_cnt */ node->node_cnt = node->left->node_cnt + tmp->left->node_cnt + 1; tmp->node_cnt = node->node_cnt + tmp->right->node_cnt + 1; /* replace y with left[y] */ /* downward: right[x] right = tmp->left; /* if left[[y] is not NIL it has a parent */ if (tmp->left != tree->sentinel) { /* upward: p[left[y]] 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; /* fix node_cnt */ node->node_cnt = node->right->node_cnt + tmp->right->node_cnt + 1; tmp->node_cnt = node->node_cnt + tmp->left->node_cnt + 1; /* 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; /* update node_cnt */ (parent->node_cnt)++; tmp = (node->key 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_visit(rbtree_node_t* node) { /* visiting the current 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; /* update node_cnt */ rbtree_node_t* tmp = cover->parent; while(tmp != sentinel) { (tmp->node_cnt)--; tmp = tmp->parent; } 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; /* next line is just fot test */ // 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 key) ? tmp->left : tmp->right; } return NULL; } /* find the node in the tree corresponding to the given order number */ rbtree_node_t* rbtree_index(rbtree_t* tree, int index) { if (index = rbtree_count(tree)) { return NULL; } rbtree_node_t* tmp = tree->root; int left_cnt = 0; int sub_left_cnt; while(tmp->node_cnt > 0) { sub_left_cnt = tmp->left->node_cnt; if (left_cnt + sub_left_cnt == index) { return tmp; } if (left_cnt + sub_left_cnt right; } else { tmp = tmp->left; } } } /* get the height of the subtree */ int rbtree_height(rbtree_t* tree, rbtree_node_t* node) { if (node == tree->sentinel) { return 0; } int left_height = rbtree_height(tree, node->left); int right_height = rbtree_height(tree, node->right); int sub_height = (left_height > right_height) ? left_height : right_height; return sub_height+1; } /* get the count of nodes in the tree */ int rbtree_count(rbtree_t* tree) { return tree->root->node_cnt; } /* visit every node of the subtree whose root is given in order */ void rbtree_traversal(rbtree_t* tree, rbtree_node_t* node, rbtree_visit_p visit) { if (node != tree->sentinel) { rbtree_traversal(tree, node->left, visit); visit(node); rbtree_traversal(tree, node->right, visit); } } </stddef.h>ストレステストをしてみましょう。
test.c:
#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 = 1key = %d\n", no, rbtree_index(&t, no)->key); long time2 = clock(); room = 48.0*cnt/(1 以前のバージョンのストレス テスト結果: <pre name="code">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.拡張バージョンのストレス テストの結果:
Inserting 1048576 nodes costs 48.00MB and spends 0.467859 seconds. Searching 1024 nodes among 1048576 spends 0.001188 seconds. Indexing 1024 nodes among 1048576 spends 0.001484 seconds. Hash 1024 times spends 0.000355 seconds. Deleting 1024 nodes among 1048576 spends 0.001417 seconds. The height of the tree is 28. Getting it spends 0.021669 seconds. Traversal the tree spends 0.023913 seconds. Count of nodes in the tree is 1047552.の比較は次のとおりです。
1. 挿入中にもう 1 つの node_cnt アイテムが維持されるため、ノードの挿入は少し遅くなります。
2. キーによるノードの検索速度に変更はありません。
3. ハッシュ検索速度に変更はありません。
4. ノードの削除には、ほぼ 2 倍の時間がかかります。これは、ノードを削除するたびに、node_cnt を最後まで更新する必要があるためです。これは、キーによるクエリとほぼ同等です。
5. シリアル番号によるクエリは、正しいサブツリーに入るたびに追加を 1 つ行う必要があるため、キーによるクエリよりも少し遅くなります。
6. トラバースにかかる時間は、本質的にツリーをトラバースするため、ツリーの高さを見つけるのと同じであり、時間効率はそれぞれ O(n) のオーダーです。特定のポイントはそれぞれ 2n ノードのアクセスです。ノードがスタックにプッシュされ、スタックからポップアウトされるとき。
最大値、最小値、中間値がどこにあるかは聞かないでください。シリアル番号で確認できますか?
著作権声明: この記事はブロガーによるオリジナルの記事であり、ブロガーの許可なく複製することはできません。
上記では、nginx データ構造 3 - 拡張赤黒ツリーを内容の側面も含めて紹介していますが、PHP チュートリアルに興味のある友人に役立つことを願っています。

セッション関連のXSS攻撃からアプリケーションを保護するには、次の測定が必要です。1。セッションCookieを保護するためにHTTPonlyとセキュアフラグを設定します。 2。すべてのユーザー入力のエクスポートコード。 3.コンテンツセキュリティポリシー(CSP)を実装して、スクリプトソースを制限します。これらのポリシーを通じて、セッション関連のXSS攻撃を効果的に保護し、ユーザーデータを確保できます。

PHPセッションのパフォーマンスを最適化する方法は次のとおりです。1。遅延セッション開始、2。データベースを使用してセッションを保存します。これらの戦略は、高い並行性環境でのアプリケーションの効率を大幅に改善できます。

thesession.gc_maxlifettinginttinginphpdethinesthelifsessessiondata、setinseconds.1)it'sconfiguredinphp.iniorviaini_set()。 2)AbalanceSneededToAvoidPerformanceIssues andunexpectedLogouts.3)php'sgarbagecollectionisisprobabilistic、影響を受けたBygc_probabi

PHPでは、session_name()関数を使用してセッション名を構成できます。特定の手順は次のとおりです。1。session_name()関数を使用して、session_name( "my_session")などのセッション名を設定します。 2。セッション名を設定した後、session_start()を呼び出してセッションを開始します。セッション名の構成は、複数のアプリケーション間のセッションデータの競合を回避し、セキュリティを強化することができますが、セッション名の一意性、セキュリティ、長さ、設定タイミングに注意してください。

セッションIDは、機密操作の前、30分ごとにログイン時に定期的に再生する必要があります。 1.セッション固定攻撃を防ぐためにログインするときにセッションIDを再生します。 2。安全性を向上させるために、敏感な操作の前に再生します。 3.定期的な再生は長期的な利用リスクを減らしますが、ユーザーエクスペリエンスの重量を量る必要があります。

PHPのセッションCookieパラメーターの設定は、session_set_cookie_params()関数を通じて達成できます。 1)この関数を使用して、有効期限、パス、ドメイン名、セキュリティフラグなどのパラメーターを設定します。 2)session_start()を呼び出して、パラメーターを有効にします。 3)ユーザーログインステータスなど、ニーズに応じてパラメーターを動的に調整します。 4)セキュリティを改善するために、セキュアとhttponlyフラグを設定することに注意してください。

PHPでセッションを使用する主な目的は、異なるページ間でユーザーのステータスを維持することです。 1)セッションはsession_start()関数を介して開始され、一意のセッションIDを作成し、ユーザーCookieに保存します。 2)セッションデータはサーバーに保存され、ログインステータスやショッピングカートのコンテンツなど、さまざまなリクエスト間でデータを渡すことができます。

サブドメイン間でセッションを共有する方法は?一般的なドメイン名にセッションCookieを設定することにより実装されます。 1.セッションCookieのドメインをサーバー側の.example.comに設定します。 2。メモリ、データベース、分散キャッシュなど、適切なセッションストレージ方法を選択します。 3. Cookieを介してセッションIDを渡すと、サーバーはIDに基づいてセッションデータを取得および更新します。


ホットAIツール

Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。

Undress AI Tool
脱衣画像を無料で

Clothoff.io
AI衣類リムーバー

Video Face Swap
完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

人気の記事

ホットツール

メモ帳++7.3.1
使いやすく無料のコードエディター

DVWA
Damn Vulnerable Web App (DVWA) は、非常に脆弱な PHP/MySQL Web アプリケーションです。その主な目的は、セキュリティ専門家が法的環境でスキルとツールをテストするのに役立ち、Web 開発者が Web アプリケーションを保護するプロセスをより深く理解できるようにし、教師/生徒が教室環境で Web アプリケーションを教え/学習できるようにすることです。安全。 DVWA の目標は、シンプルでわかりやすいインターフェイスを通じて、さまざまな難易度で最も一般的な Web 脆弱性のいくつかを実践することです。このソフトウェアは、

MantisBT
Mantis は、製品の欠陥追跡を支援するために設計された、導入が簡単な Web ベースの欠陥追跡ツールです。 PHP、MySQL、Web サーバーが必要です。デモおよびホスティング サービスをチェックしてください。

SublimeText3 中国語版
中国語版、とても使いやすい

mPDF
mPDF は、UTF-8 でエンコードされた HTML から PDF ファイルを生成できる PHP ライブラリです。オリジナルの作者である Ian Back は、Web サイトから「オンザフライ」で PDF ファイルを出力し、さまざまな言語を処理するために mPDF を作成しました。 HTML2FPDF などのオリジナルのスクリプトよりも遅く、Unicode フォントを使用すると生成されるファイルが大きくなりますが、CSS スタイルなどをサポートし、多くの機能強化が施されています。 RTL (アラビア語とヘブライ語) や CJK (中国語、日本語、韓国語) を含むほぼすべての言語をサポートします。ネストされたブロックレベル要素 (P、DIV など) をサポートします。
