aboutsummaryrefslogtreecommitdiff
path: root/src/core
diff options
context:
space:
mode:
Diffstat (limited to 'src/core')
-rw-r--r--src/core/ngx_core.h1
-rw-r--r--src/core/ngx_inet.c35
-rw-r--r--src/core/ngx_inet.h8
-rw-r--r--src/core/ngx_radix_tree.c152
-rw-r--r--src/core/ngx_radix_tree.h34
5 files changed, 230 insertions, 0 deletions
diff --git a/src/core/ngx_core.h b/src/core/ngx_core.h
index 081fc9b2e..ed105e592 100644
--- a/src/core/ngx_core.h
+++ b/src/core/ngx_core.h
@@ -37,6 +37,7 @@ typedef struct ngx_connection_s ngx_connection_t;
#include <ngx_regex.h>
#endif
#include <ngx_rbtree.h>
+#include <ngx_radix_tree.h>
#include <ngx_times.h>
#include <ngx_inet.h>
#include <ngx_cycle.h>
diff --git a/src/core/ngx_inet.c b/src/core/ngx_inet.c
index fd67b7642..5c032a2d0 100644
--- a/src/core/ngx_inet.c
+++ b/src/core/ngx_inet.c
@@ -164,3 +164,38 @@ size_t ngx_inet_ntop(int family, void *addr, u_char *text, size_t len)
"%u.%u.%u.%u", p[0], p[1], p[2], p[3]);
#endif
}
+
+
+/* AF_INET only */
+
+ngx_int_t ngx_ptocidr(ngx_str_t *text, void *cidr)
+{
+ ngx_uint_t i;
+ ngx_inet_cidr_t *in_cidr;
+
+ in_cidr = cidr;
+
+ for (i = 0; i < text->len; i++) {
+ if (text->data[i] == '/') {
+ break;
+ }
+ }
+
+ if (i == text->len) {
+ return NGX_ERROR;
+ }
+
+ text->data[i] = '\0';
+ in_cidr->addr = inet_addr((char *) text->data);
+ text->data[i] = '/';
+ if (in_cidr->addr == INADDR_NONE) {
+ return NGX_ERROR;
+ }
+
+ in_cidr->mask = ngx_atoi(&text->data[i + 1], text->len - (i + 1));
+ if (in_cidr->mask == (in_addr_t) NGX_ERROR) {
+ return NGX_ERROR;
+ }
+
+ return NGX_OK;
+}
diff --git a/src/core/ngx_inet.h b/src/core/ngx_inet.h
index 074d43c94..dbdf6f0b3 100644
--- a/src/core/ngx_inet.h
+++ b/src/core/ngx_inet.h
@@ -2,9 +2,17 @@
#define _NGX_INET_H_INCLUDED_
+typedef struct {
+ in_addr_t addr;
+ in_addr_t mask;
+} ngx_inet_cidr_t;
+
+
size_t ngx_sock_ntop(int family, struct sockaddr *addr, u_char *text,
size_t len);
size_t ngx_inet_ntop(int family, void *addr, u_char *text, size_t len);
+ngx_int_t ngx_ptocidr(ngx_str_t *text, void *cidr);
+
#endif /* _NGX_INET_H_INCLUDED_ */
diff --git a/src/core/ngx_radix_tree.c b/src/core/ngx_radix_tree.c
new file mode 100644
index 000000000..d2716e144
--- /dev/null
+++ b/src/core/ngx_radix_tree.c
@@ -0,0 +1,152 @@
+
+#include <ngx_config.h>
+#include <ngx_core.h>
+
+
+/* STUB: page size */
+#define NGX_RADIX_TREE_POOL_SIZE 4096
+
+
+static void *ngx_radix_alloc(ngx_radix_tree_t *tree, size_t size);
+
+
+ngx_radix_tree_t *ngx_radix_tree_create(ngx_pool_t *pool)
+{
+ ngx_radix_tree_t *tree;
+
+ if (!(tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)))) {
+ return NULL;
+ }
+
+ tree->root = NULL;
+ tree->pool = pool;
+ tree->free = NULL;
+ tree->size = 0;
+
+ return tree;
+}
+
+
+ngx_int_t ngx_radix32tree_insert(ngx_radix_tree_t *tree,
+ uint32_t key, uint32_t mask, uintptr_t value)
+{
+ uint32_t bit;
+ ngx_radix_node_t *node, *new;
+
+ bit = 0x80000000;
+ node = tree->root;
+
+ while (node && (bit & mask)) {
+ if (key & bit) {
+ node = node->right;
+
+ } else {
+ node = node->left;
+ }
+
+ bit >>= 1;
+ }
+
+ if (node) {
+ if (node->value) {
+ return NGX_BUSY;
+ }
+
+ node->value = value;
+ return NGX_OK;
+ }
+
+ while (bit & mask) {
+ if (!(new = ngx_radix_alloc(tree, sizeof(ngx_radix_node_t)))) {
+ return NGX_ERROR;
+ }
+
+ new->value = value;
+
+ if (key & bit) {
+ node->right = new;
+
+ } else {
+ node->left = new;
+ }
+
+ bit >>= 1;
+ new = node;
+ }
+
+ return NGX_OK;
+}
+
+
+void ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask)
+{
+ uint32_t bit;
+ ngx_radix_node_t *node;
+
+ bit = 0x80000000;
+ node = tree->root;
+
+ while (node && (bit & mask)) {
+ if (key & bit) {
+ node = node->right;
+
+ } else {
+ node = node->left;
+ }
+
+ bit >>= 1;
+ }
+
+ if (node) {
+ node->value = (uintptr_t) 0;
+ }
+}
+
+
+uintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
+{
+ uint32_t bit;
+ uintptr_t value;
+ ngx_radix_node_t *node;
+
+ bit = 0x80000000;
+ value = NULL;
+ node = tree->root;
+
+ while (node) {
+ if (node->value) {
+ value = node->value;
+ }
+
+ if (key & bit) {
+ node = node->right;
+
+ } else {
+ node = node->left;
+ }
+
+ bit >>= 1;
+ }
+
+ return value;
+}
+
+
+static void *ngx_radix_alloc(ngx_radix_tree_t *tree, size_t size)
+{
+ char *p;
+
+ if (tree->size < size) {
+ if (!(tree->free = ngx_palloc(tree->pool, NGX_RADIX_TREE_POOL_SIZE))) {
+ return NULL;
+ }
+
+ tree->size = NGX_RADIX_TREE_POOL_SIZE;
+ }
+
+ p = tree->free;
+ tree->free += size;
+ tree->size -= size;
+
+ return p;
+}
diff --git a/src/core/ngx_radix_tree.h b/src/core/ngx_radix_tree.h
new file mode 100644
index 000000000..6fe574b50
--- /dev/null
+++ b/src/core/ngx_radix_tree.h
@@ -0,0 +1,34 @@
+#ifndef _NGX_RADIX_TREE_H_INCLUDED_
+#define _NGX_RADIX_TREE_H_INCLUDED_
+
+
+#include <ngx_config.h>
+#include <ngx_core.h>
+
+
+typedef struct ngx_radix_node_s ngx_radix_node_t;
+
+struct ngx_radix_node_s {
+ uintptr_t value;
+ ngx_radix_node_t *right;
+ ngx_radix_node_t *left;
+};
+
+
+typedef struct {
+ ngx_radix_node_t *root;
+ ngx_pool_t *pool;
+ char *free;
+ size_t size;
+} ngx_radix_tree_t;
+
+
+ngx_radix_tree_t *ngx_radix_tree_create(ngx_pool_t *pool);
+ngx_int_t ngx_radix32tree_insert(ngx_radix_tree_t *tree,
+ uint32_t key, uint32_t mask, uintptr_t value);
+void ngx_radix32tree_delete(ngx_radix_tree_t *tree,
+ uint32_t key, uint32_t mask);
+uintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key);
+
+
+#endif /* _NGX_RADIX_TREE_H_INCLUDED_ */
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-19 15:37:17 +0000