nginx: src/core/ngx_radix_tree.c comparison

comparison src/core/ngx_radix_tree.c @ 5048:2f0862333985 stable-1.2

Merge of r4993, r4994, r4997, r5000: geo ipv6 support. *) Geo: IPv6 support. The "ranges" mode is still limited to IPv4 only. *) Geo: properly initialize ngx_cidr_t when dealing with "default". *) Geo: made "default" affect both IPv4 and IPv6 when using prefixes. Previously, "default" was equivalent to specifying 0.0.0.0/0, now it's equivalent to specifying both 0.0.0.0/0 and ::/0 (if support for IPv6 is enabled) with the same value. *) Geo: improved code readability.

author	Maxim Dounin <mdounin@mdounin.ru>
date	Mon, 11 Feb 2013 12:31:43 +0000
parents	852f40088278
children

comparison

equal deleted inserted replaced

-:852f40088278
+:2f0862333985
 return value;
 }
+#if (NGX_HAVE_INET6)
+ngx_int_t
+ngx_radix128tree_insert(ngx_radix_tree_t *tree, u_char *key, u_char *mask,
+uintptr_t value)
+{
+u_char             bit;
+ngx_uint_t         i;
+ngx_radix_node_t  *node, *next;
+i = 0;
+bit = 0x80;
+node = tree->root;
+next = tree->root;
+while (bit & mask[i]) {
+if (key[i] & bit) {
+next = node->right;
+} else {
+next = node->left;
+}
+if (next == NULL) {
+break;
+}
+bit >>= 1;
+node = next;
+if (bit == 0) {
+if (++i == 16) {
+break;
+}
+bit = 0x80;
+}
+}
+if (next) {
+if (node->value != NGX_RADIX_NO_VALUE) {
+return NGX_BUSY;
+}
+node->value = value;
+return NGX_OK;
+}
+while (bit & mask[i]) {
+next = ngx_radix_alloc(tree);
+if (next == NULL) {
+return NGX_ERROR;
+}
+next->right = NULL;
+next->left = NULL;
+next->parent = node;
+next->value = NGX_RADIX_NO_VALUE;
+if (key[i] & bit) {
+node->right = next;
+} else {
+node->left = next;
+}
+bit >>= 1;
+node = next;
+if (bit == 0) {
+if (++i == 16) {
+break;
+}
+bit = 0x80;
+}
+}
+node->value = value;
+return NGX_OK;
+}
+ngx_int_t
+ngx_radix128tree_delete(ngx_radix_tree_t *tree, u_char *key, u_char *mask)
+{
+u_char             bit;
+ngx_uint_t         i;
+ngx_radix_node_t  *node;
+i = 0;
+bit = 0x80;
+node = tree->root;
+while (node && (bit & mask[i])) {
+if (key[i] & bit) {
+node = node->right;
+} else {
+node = node->left;
+}
+bit >>= 1;
+if (bit == 0) {
+if (++i == 16) {
+break;
+}
+bit = 0x80;
+}
+}
+if (node == NULL) {
+return NGX_ERROR;
+}
+if (node->right || node->left) {
+if (node->value != NGX_RADIX_NO_VALUE) {
+node->value = NGX_RADIX_NO_VALUE;
+return NGX_OK;
+}
+return NGX_ERROR;
+}
+for ( ;; ) {
+if (node->parent->right == node) {
+node->parent->right = NULL;
+} else {
+node->parent->left = NULL;
+}
+node->right = tree->free;
+tree->free = node;
+node = node->parent;
+if (node->right || node->left) {
+break;
+}
+if (node->value != NGX_RADIX_NO_VALUE) {
+break;
+}
+if (node->parent == NULL) {
+break;
+}
+}
+return NGX_OK;
+}
+uintptr_t
+ngx_radix128tree_find(ngx_radix_tree_t *tree, u_char *key)
+{
+u_char             bit;
+uintptr_t          value;
+ngx_uint_t         i;
+ngx_radix_node_t  *node;
+i = 0;
+bit = 0x80;
+value = NGX_RADIX_NO_VALUE;
+node = tree->root;
+while (node) {
+if (node->value != NGX_RADIX_NO_VALUE) {
+value = node->value;
+}
+if (key[i] & bit) {
+node = node->right;
+} else {
+node = node->left;
+}
+bit >>= 1;
+if (bit == 0) {
+i++;
+bit = 0x80;
+}
+}
+return value;
+}
+#endif
 static ngx_radix_node_t *
 ngx_radix_alloc(ngx_radix_tree_t *tree)
 {
 ngx_radix_node_t  *p;

Mercurial > hg > nginx

comparison src/core/ngx_radix_tree.c @ 5048:2f0862333985 stable-1.2