| File: | src/usr.bin/tmux/hyperlinks.c |
| Warning: | line 89, column 23 The left operand of '-' is a garbage value |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | /* $OpenBSD: hyperlinks.c,v 1.3 2023/06/30 13:19:32 nicm Exp $ */ | |||
| 2 | ||||
| 3 | /* | |||
| 4 | * Copyright (c) 2021 Will <author@will.party> | |||
| 5 | * Copyright (c) 2022 Jeff Chiang <pobomp@gmail.com> | |||
| 6 | * | |||
| 7 | * Permission to use, copy, modify, and distribute this software for any | |||
| 8 | * purpose with or without fee is hereby granted, provided that the above | |||
| 9 | * copyright notice and this permission notice appear in all copies. | |||
| 10 | * | |||
| 11 | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES | |||
| 12 | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF | |||
| 13 | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR | |||
| 14 | * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES | |||
| 15 | * WHATSOEVER RESULTING FROM LOSS OF MIND, USE, DATA OR PROFITS, WHETHER | |||
| 16 | * IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING | |||
| 17 | * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. | |||
| 18 | */ | |||
| 19 | ||||
| 20 | #include <sys/types.h> | |||
| 21 | ||||
| 22 | #include <stdlib.h> | |||
| 23 | #include <string.h> | |||
| 24 | #include <vis.h> | |||
| 25 | ||||
| 26 | #include "tmux.h" | |||
| 27 | ||||
| 28 | /* | |||
| 29 | * OSC 8 hyperlinks, described at: | |||
| 30 | * | |||
| 31 | * https://gist.github.com/egmontkob/eb114294efbcd5adb1944c9f3cb5feda | |||
| 32 | * | |||
| 33 | * Each hyperlink and ID combination is assigned a number ("inner" in this | |||
| 34 | * file) which is stored in an extended grid cell and maps into a tree here. | |||
| 35 | * | |||
| 36 | * Each URI has one inner number and one external ID (which tmux uses to send | |||
| 37 | * the hyperlink to the terminal) and one internal ID (which is received from | |||
| 38 | * the sending application inside tmux). | |||
| 39 | * | |||
| 40 | * Anonymous hyperlinks are each unique and are not reused even if they have | |||
| 41 | * the same URI (terminals will not want to tie them together). | |||
| 42 | */ | |||
| 43 | ||||
| 44 | #define MAX_HYPERLINKS5000 5000 | |||
| 45 | ||||
| 46 | static long long hyperlinks_next_external_id = 1; | |||
| 47 | static u_int global_hyperlinks_count; | |||
| 48 | ||||
| 49 | struct hyperlinks_uri { | |||
| 50 | struct hyperlinks *tree; | |||
| 51 | ||||
| 52 | u_int inner; | |||
| 53 | const char *internal_id; | |||
| 54 | const char *external_id; | |||
| 55 | const char *uri; | |||
| 56 | ||||
| 57 | TAILQ_ENTRY(hyperlinks_uri)struct { struct hyperlinks_uri *tqe_next; struct hyperlinks_uri **tqe_prev; } list_entry; | |||
| 58 | RB_ENTRY(hyperlinks_uri)struct { struct hyperlinks_uri *rbe_left; struct hyperlinks_uri *rbe_right; struct hyperlinks_uri *rbe_parent; int rbe_color ; } by_inner_entry; | |||
| 59 | RB_ENTRY(hyperlinks_uri)struct { struct hyperlinks_uri *rbe_left; struct hyperlinks_uri *rbe_right; struct hyperlinks_uri *rbe_parent; int rbe_color ; } by_uri_entry; /* by internal ID and URI */ | |||
| 60 | }; | |||
| 61 | RB_HEAD(hyperlinks_by_uri_tree, hyperlinks_uri)struct hyperlinks_by_uri_tree { struct hyperlinks_uri *rbh_root ; }; | |||
| 62 | RB_HEAD(hyperlinks_by_inner_tree, hyperlinks_uri)struct hyperlinks_by_inner_tree { struct hyperlinks_uri *rbh_root ; }; | |||
| 63 | ||||
| 64 | TAILQ_HEAD(hyperlinks_list, hyperlinks_uri)struct hyperlinks_list { struct hyperlinks_uri *tqh_first; struct hyperlinks_uri **tqh_last; }; | |||
| 65 | static struct hyperlinks_list global_hyperlinks = | |||
| 66 | TAILQ_HEAD_INITIALIZER(global_hyperlinks){ ((void *)0), &(global_hyperlinks).tqh_first }; | |||
| 67 | ||||
| 68 | struct hyperlinks { | |||
| 69 | u_int next_inner; | |||
| 70 | struct hyperlinks_by_inner_tree by_inner; | |||
| 71 | struct hyperlinks_by_uri_tree by_uri; | |||
| 72 | }; | |||
| 73 | ||||
| 74 | static int | |||
| 75 | hyperlinks_by_uri_cmp(struct hyperlinks_uri *left, struct hyperlinks_uri *right) | |||
| 76 | { | |||
| 77 | int r; | |||
| 78 | ||||
| 79 | if (*left->internal_id == '\0' || *right->internal_id == '\0') { | |||
| 80 | /* | |||
| 81 | * If both URIs are anonymous, use the inner for comparison so | |||
| 82 | * that they do not match even if the URI is the same - each | |||
| 83 | * anonymous URI should be unique. | |||
| 84 | */ | |||
| 85 | if (*left->internal_id != '\0') | |||
| 86 | return (-1); | |||
| 87 | if (*right->internal_id != '\0') | |||
| 88 | return (1); | |||
| 89 | return (left->inner - right->inner); | |||
| ||||
| 90 | } | |||
| 91 | ||||
| 92 | r = strcmp(left->internal_id, right->internal_id); | |||
| 93 | if (r != 0) | |||
| 94 | return (r); | |||
| 95 | return (strcmp(left->uri, right->uri)); | |||
| 96 | } | |||
| 97 | RB_PROTOTYPE_STATIC(hyperlinks_by_uri_tree, hyperlinks_uri, by_uri_entry,__attribute__((__unused__)) static void hyperlinks_by_uri_tree_RB_INSERT_COLOR (struct hyperlinks_by_uri_tree *, struct hyperlinks_uri *); __attribute__ ((__unused__)) static void hyperlinks_by_uri_tree_RB_REMOVE_COLOR (struct hyperlinks_by_uri_tree *, struct hyperlinks_uri *, struct hyperlinks_uri *);__attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_uri_tree_RB_REMOVE(struct hyperlinks_by_uri_tree *, struct hyperlinks_uri *); __attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_uri_tree_RB_INSERT(struct hyperlinks_by_uri_tree *, struct hyperlinks_uri *); __attribute__ ((__unused__)) static struct hyperlinks_uri *hyperlinks_by_uri_tree_RB_FIND (struct hyperlinks_by_uri_tree *, struct hyperlinks_uri *); __attribute__ ((__unused__)) static struct hyperlinks_uri *hyperlinks_by_uri_tree_RB_NFIND (struct hyperlinks_by_uri_tree *, struct hyperlinks_uri *); __attribute__ ((__unused__)) static struct hyperlinks_uri *hyperlinks_by_uri_tree_RB_NEXT (struct hyperlinks_uri *); __attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_uri_tree_RB_PREV(struct hyperlinks_uri *); __attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_uri_tree_RB_MINMAX(struct hyperlinks_by_uri_tree *, int); | |||
| 98 | hyperlinks_by_uri_cmp)__attribute__((__unused__)) static void hyperlinks_by_uri_tree_RB_INSERT_COLOR (struct hyperlinks_by_uri_tree *, struct hyperlinks_uri *); __attribute__ ((__unused__)) static void hyperlinks_by_uri_tree_RB_REMOVE_COLOR (struct hyperlinks_by_uri_tree *, struct hyperlinks_uri *, struct hyperlinks_uri *);__attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_uri_tree_RB_REMOVE(struct hyperlinks_by_uri_tree *, struct hyperlinks_uri *); __attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_uri_tree_RB_INSERT(struct hyperlinks_by_uri_tree *, struct hyperlinks_uri *); __attribute__ ((__unused__)) static struct hyperlinks_uri *hyperlinks_by_uri_tree_RB_FIND (struct hyperlinks_by_uri_tree *, struct hyperlinks_uri *); __attribute__ ((__unused__)) static struct hyperlinks_uri *hyperlinks_by_uri_tree_RB_NFIND (struct hyperlinks_by_uri_tree *, struct hyperlinks_uri *); __attribute__ ((__unused__)) static struct hyperlinks_uri *hyperlinks_by_uri_tree_RB_NEXT (struct hyperlinks_uri *); __attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_uri_tree_RB_PREV(struct hyperlinks_uri *); __attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_uri_tree_RB_MINMAX(struct hyperlinks_by_uri_tree *, int);; | |||
| 99 | RB_GENERATE_STATIC(hyperlinks_by_uri_tree, hyperlinks_uri, by_uri_entry,__attribute__((__unused__)) static void hyperlinks_by_uri_tree_RB_INSERT_COLOR (struct hyperlinks_by_uri_tree *head, struct hyperlinks_uri * elm) { struct hyperlinks_uri *parent, *gparent, *tmp; while ( (parent = (elm)->by_uri_entry.rbe_parent) && (parent )->by_uri_entry.rbe_color == 1) { gparent = (parent)->by_uri_entry .rbe_parent; if (parent == (gparent)->by_uri_entry.rbe_left ) { tmp = (gparent)->by_uri_entry.rbe_right; if (tmp && (tmp)->by_uri_entry.rbe_color == 1) { (tmp)->by_uri_entry .rbe_color = 0; do { (parent)->by_uri_entry.rbe_color = 0; (gparent)->by_uri_entry.rbe_color = 1; } while (0); elm = gparent; continue; } if ((parent)->by_uri_entry.rbe_right == elm) { do { (tmp) = (parent)->by_uri_entry.rbe_right; if (((parent)->by_uri_entry.rbe_right = (tmp)->by_uri_entry .rbe_left)) { ((tmp)->by_uri_entry.rbe_left)->by_uri_entry .rbe_parent = (parent); } do {} while (0); if (((tmp)->by_uri_entry .rbe_parent = (parent)->by_uri_entry.rbe_parent)) { if ((parent ) == ((parent)->by_uri_entry.rbe_parent)->by_uri_entry. rbe_left) ((parent)->by_uri_entry.rbe_parent)->by_uri_entry .rbe_left = (tmp); else ((parent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_uri_entry.rbe_left = (parent); (parent )->by_uri_entry.rbe_parent = (tmp); do {} while (0); if (( (tmp)->by_uri_entry.rbe_parent)) do {} while (0); } while ( 0); tmp = parent; parent = elm; elm = tmp; } do { (parent)-> by_uri_entry.rbe_color = 0; (gparent)->by_uri_entry.rbe_color = 1; } while (0); do { (tmp) = (gparent)->by_uri_entry.rbe_left ; if (((gparent)->by_uri_entry.rbe_left = (tmp)->by_uri_entry .rbe_right)) { ((tmp)->by_uri_entry.rbe_right)->by_uri_entry .rbe_parent = (gparent); } do {} while (0); if (((tmp)->by_uri_entry .rbe_parent = (gparent)->by_uri_entry.rbe_parent)) { if (( gparent) == ((gparent)->by_uri_entry.rbe_parent)->by_uri_entry .rbe_left) ((gparent)->by_uri_entry.rbe_parent)->by_uri_entry .rbe_left = (tmp); else ((gparent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_uri_entry.rbe_right = (gparent); (gparent )->by_uri_entry.rbe_parent = (tmp); do {} while (0); if (( (tmp)->by_uri_entry.rbe_parent)) do {} while (0); } while ( 0); } else { tmp = (gparent)->by_uri_entry.rbe_left; if (tmp && (tmp)->by_uri_entry.rbe_color == 1) { (tmp)-> by_uri_entry.rbe_color = 0; do { (parent)->by_uri_entry.rbe_color = 0; (gparent)->by_uri_entry.rbe_color = 1; } while (0); elm = gparent; continue; } if ((parent)->by_uri_entry.rbe_left == elm) { do { (tmp) = (parent)->by_uri_entry.rbe_left; if (((parent)->by_uri_entry.rbe_left = (tmp)->by_uri_entry .rbe_right)) { ((tmp)->by_uri_entry.rbe_right)->by_uri_entry .rbe_parent = (parent); } do {} while (0); if (((tmp)->by_uri_entry .rbe_parent = (parent)->by_uri_entry.rbe_parent)) { if ((parent ) == ((parent)->by_uri_entry.rbe_parent)->by_uri_entry. rbe_left) ((parent)->by_uri_entry.rbe_parent)->by_uri_entry .rbe_left = (tmp); else ((parent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_uri_entry.rbe_right = (parent); (parent )->by_uri_entry.rbe_parent = (tmp); do {} while (0); if (( (tmp)->by_uri_entry.rbe_parent)) do {} while (0); } while ( 0); tmp = parent; parent = elm; elm = tmp; } do { (parent)-> by_uri_entry.rbe_color = 0; (gparent)->by_uri_entry.rbe_color = 1; } while (0); do { (tmp) = (gparent)->by_uri_entry.rbe_right ; if (((gparent)->by_uri_entry.rbe_right = (tmp)->by_uri_entry .rbe_left)) { ((tmp)->by_uri_entry.rbe_left)->by_uri_entry .rbe_parent = (gparent); } do {} while (0); if (((tmp)->by_uri_entry .rbe_parent = (gparent)->by_uri_entry.rbe_parent)) { if (( gparent) == ((gparent)->by_uri_entry.rbe_parent)->by_uri_entry .rbe_left) ((gparent)->by_uri_entry.rbe_parent)->by_uri_entry .rbe_left = (tmp); else ((gparent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_uri_entry.rbe_left = (gparent); (gparent )->by_uri_entry.rbe_parent = (tmp); do {} while (0); if (( (tmp)->by_uri_entry.rbe_parent)) do {} while (0); } while ( 0); } } (head->rbh_root)->by_uri_entry.rbe_color = 0; } __attribute__((__unused__)) static void hyperlinks_by_uri_tree_RB_REMOVE_COLOR (struct hyperlinks_by_uri_tree *head, struct hyperlinks_uri * parent, struct hyperlinks_uri *elm) { struct hyperlinks_uri * tmp; while ((elm == ((void *)0) || (elm)->by_uri_entry.rbe_color == 0) && elm != (head)->rbh_root) { if ((parent)-> by_uri_entry.rbe_left == elm) { tmp = (parent)->by_uri_entry .rbe_right; if ((tmp)->by_uri_entry.rbe_color == 1) { do { (tmp)->by_uri_entry.rbe_color = 0; (parent)->by_uri_entry .rbe_color = 1; } while (0); do { (tmp) = (parent)->by_uri_entry .rbe_right; if (((parent)->by_uri_entry.rbe_right = (tmp)-> by_uri_entry.rbe_left)) { ((tmp)->by_uri_entry.rbe_left)-> by_uri_entry.rbe_parent = (parent); } do {} while (0); if ((( tmp)->by_uri_entry.rbe_parent = (parent)->by_uri_entry. rbe_parent)) { if ((parent) == ((parent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_left) ((parent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_left = (tmp); else ((parent)->by_uri_entry .rbe_parent)->by_uri_entry.rbe_right = (tmp); } else (head )->rbh_root = (tmp); (tmp)->by_uri_entry.rbe_left = (parent ); (parent)->by_uri_entry.rbe_parent = (tmp); do {} while ( 0); if (((tmp)->by_uri_entry.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->by_uri_entry.rbe_right; } if (((tmp)->by_uri_entry.rbe_left == ((void *)0) || ((tmp)-> by_uri_entry.rbe_left)->by_uri_entry.rbe_color == 0) && ((tmp)->by_uri_entry.rbe_right == ((void *)0) || ((tmp)-> by_uri_entry.rbe_right)->by_uri_entry.rbe_color == 0)) { ( tmp)->by_uri_entry.rbe_color = 1; elm = parent; parent = ( elm)->by_uri_entry.rbe_parent; } else { if ((tmp)->by_uri_entry .rbe_right == ((void *)0) || ((tmp)->by_uri_entry.rbe_right )->by_uri_entry.rbe_color == 0) { struct hyperlinks_uri *oleft ; if ((oleft = (tmp)->by_uri_entry.rbe_left)) (oleft)-> by_uri_entry.rbe_color = 0; (tmp)->by_uri_entry.rbe_color = 1; do { (oleft) = (tmp)->by_uri_entry.rbe_left; if (((tmp )->by_uri_entry.rbe_left = (oleft)->by_uri_entry.rbe_right )) { ((oleft)->by_uri_entry.rbe_right)->by_uri_entry.rbe_parent = (tmp); } do {} while (0); if (((oleft)->by_uri_entry.rbe_parent = (tmp)->by_uri_entry.rbe_parent)) { if ((tmp) == ((tmp)-> by_uri_entry.rbe_parent)->by_uri_entry.rbe_left) ((tmp)-> by_uri_entry.rbe_parent)->by_uri_entry.rbe_left = (oleft); else ((tmp)->by_uri_entry.rbe_parent)->by_uri_entry.rbe_right = (oleft); } else (head)->rbh_root = (oleft); (oleft)-> by_uri_entry.rbe_right = (tmp); (tmp)->by_uri_entry.rbe_parent = (oleft); do {} while (0); if (((oleft)->by_uri_entry.rbe_parent )) do {} while (0); } while (0); tmp = (parent)->by_uri_entry .rbe_right; } (tmp)->by_uri_entry.rbe_color = (parent)-> by_uri_entry.rbe_color; (parent)->by_uri_entry.rbe_color = 0; if ((tmp)->by_uri_entry.rbe_right) ((tmp)->by_uri_entry .rbe_right)->by_uri_entry.rbe_color = 0; do { (tmp) = (parent )->by_uri_entry.rbe_right; if (((parent)->by_uri_entry. rbe_right = (tmp)->by_uri_entry.rbe_left)) { ((tmp)->by_uri_entry .rbe_left)->by_uri_entry.rbe_parent = (parent); } do {} while (0); if (((tmp)->by_uri_entry.rbe_parent = (parent)->by_uri_entry .rbe_parent)) { if ((parent) == ((parent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_left) ((parent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_left = (tmp); else ((parent)->by_uri_entry .rbe_parent)->by_uri_entry.rbe_right = (tmp); } else (head )->rbh_root = (tmp); (tmp)->by_uri_entry.rbe_left = (parent ); (parent)->by_uri_entry.rbe_parent = (tmp); do {} while ( 0); if (((tmp)->by_uri_entry.rbe_parent)) do {} while (0); } while (0); elm = (head)->rbh_root; break; } } else { tmp = (parent)->by_uri_entry.rbe_left; if ((tmp)->by_uri_entry .rbe_color == 1) { do { (tmp)->by_uri_entry.rbe_color = 0; (parent)->by_uri_entry.rbe_color = 1; } while (0); do { ( tmp) = (parent)->by_uri_entry.rbe_left; if (((parent)-> by_uri_entry.rbe_left = (tmp)->by_uri_entry.rbe_right)) { ( (tmp)->by_uri_entry.rbe_right)->by_uri_entry.rbe_parent = (parent); } do {} while (0); if (((tmp)->by_uri_entry.rbe_parent = (parent)->by_uri_entry.rbe_parent)) { if ((parent) == ( (parent)->by_uri_entry.rbe_parent)->by_uri_entry.rbe_left ) ((parent)->by_uri_entry.rbe_parent)->by_uri_entry.rbe_left = (tmp); else ((parent)->by_uri_entry.rbe_parent)->by_uri_entry .rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp) ->by_uri_entry.rbe_right = (parent); (parent)->by_uri_entry .rbe_parent = (tmp); do {} while (0); if (((tmp)->by_uri_entry .rbe_parent)) do {} while (0); } while (0); tmp = (parent)-> by_uri_entry.rbe_left; } if (((tmp)->by_uri_entry.rbe_left == ((void *)0) || ((tmp)->by_uri_entry.rbe_left)->by_uri_entry .rbe_color == 0) && ((tmp)->by_uri_entry.rbe_right == ((void *)0) || ((tmp)->by_uri_entry.rbe_right)->by_uri_entry .rbe_color == 0)) { (tmp)->by_uri_entry.rbe_color = 1; elm = parent; parent = (elm)->by_uri_entry.rbe_parent; } else { if ((tmp)->by_uri_entry.rbe_left == ((void *)0) || ((tmp )->by_uri_entry.rbe_left)->by_uri_entry.rbe_color == 0) { struct hyperlinks_uri *oright; if ((oright = (tmp)->by_uri_entry .rbe_right)) (oright)->by_uri_entry.rbe_color = 0; (tmp)-> by_uri_entry.rbe_color = 1; do { (oright) = (tmp)->by_uri_entry .rbe_right; if (((tmp)->by_uri_entry.rbe_right = (oright)-> by_uri_entry.rbe_left)) { ((oright)->by_uri_entry.rbe_left )->by_uri_entry.rbe_parent = (tmp); } do {} while (0); if ( ((oright)->by_uri_entry.rbe_parent = (tmp)->by_uri_entry .rbe_parent)) { if ((tmp) == ((tmp)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_left) ((tmp)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_left = (oright); else ((tmp)->by_uri_entry .rbe_parent)->by_uri_entry.rbe_right = (oright); } else (head )->rbh_root = (oright); (oright)->by_uri_entry.rbe_left = (tmp); (tmp)->by_uri_entry.rbe_parent = (oright); do {} while (0); if (((oright)->by_uri_entry.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->by_uri_entry.rbe_left ; } (tmp)->by_uri_entry.rbe_color = (parent)->by_uri_entry .rbe_color; (parent)->by_uri_entry.rbe_color = 0; if ((tmp )->by_uri_entry.rbe_left) ((tmp)->by_uri_entry.rbe_left )->by_uri_entry.rbe_color = 0; do { (tmp) = (parent)->by_uri_entry .rbe_left; if (((parent)->by_uri_entry.rbe_left = (tmp)-> by_uri_entry.rbe_right)) { ((tmp)->by_uri_entry.rbe_right) ->by_uri_entry.rbe_parent = (parent); } do {} while (0); if (((tmp)->by_uri_entry.rbe_parent = (parent)->by_uri_entry .rbe_parent)) { if ((parent) == ((parent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_left) ((parent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_left = (tmp); else ((parent)->by_uri_entry .rbe_parent)->by_uri_entry.rbe_right = (tmp); } else (head )->rbh_root = (tmp); (tmp)->by_uri_entry.rbe_right = (parent ); (parent)->by_uri_entry.rbe_parent = (tmp); do {} while ( 0); if (((tmp)->by_uri_entry.rbe_parent)) do {} while (0); } while (0); elm = (head)->rbh_root; break; } } } if (elm ) (elm)->by_uri_entry.rbe_color = 0; } __attribute__((__unused__ )) static struct hyperlinks_uri * hyperlinks_by_uri_tree_RB_REMOVE (struct hyperlinks_by_uri_tree *head, struct hyperlinks_uri * elm) { struct hyperlinks_uri *child, *parent, *old = elm; int color; if ((elm)->by_uri_entry.rbe_left == ((void *)0)) child = (elm)->by_uri_entry.rbe_right; else if ((elm)->by_uri_entry .rbe_right == ((void *)0)) child = (elm)->by_uri_entry.rbe_left ; else { struct hyperlinks_uri *left; elm = (elm)->by_uri_entry .rbe_right; while ((left = (elm)->by_uri_entry.rbe_left)) elm = left; child = (elm)->by_uri_entry.rbe_right; parent = ( elm)->by_uri_entry.rbe_parent; color = (elm)->by_uri_entry .rbe_color; if (child) (child)->by_uri_entry.rbe_parent = parent ; if (parent) { if ((parent)->by_uri_entry.rbe_left == elm ) (parent)->by_uri_entry.rbe_left = child; else (parent)-> by_uri_entry.rbe_right = child; do {} while (0); } else (head )->rbh_root = child; if ((elm)->by_uri_entry.rbe_parent == old) parent = elm; (elm)->by_uri_entry = (old)->by_uri_entry ; if ((old)->by_uri_entry.rbe_parent) { if (((old)->by_uri_entry .rbe_parent)->by_uri_entry.rbe_left == old) ((old)->by_uri_entry .rbe_parent)->by_uri_entry.rbe_left = elm; else ((old)-> by_uri_entry.rbe_parent)->by_uri_entry.rbe_right = elm; do {} while (0); } else (head)->rbh_root = elm; ((old)->by_uri_entry .rbe_left)->by_uri_entry.rbe_parent = elm; if ((old)->by_uri_entry .rbe_right) ((old)->by_uri_entry.rbe_right)->by_uri_entry .rbe_parent = elm; if (parent) { left = parent; do { do {} while (0); } while ((left = (left)->by_uri_entry.rbe_parent)); } goto color; } parent = (elm)->by_uri_entry.rbe_parent; color = (elm)->by_uri_entry.rbe_color; if (child) (child)->by_uri_entry .rbe_parent = parent; if (parent) { if ((parent)->by_uri_entry .rbe_left == elm) (parent)->by_uri_entry.rbe_left = child; else (parent)->by_uri_entry.rbe_right = child; do {} while (0); } else (head)->rbh_root = child; color: if (color == 0) hyperlinks_by_uri_tree_RB_REMOVE_COLOR(head, parent, child ); return (old); } __attribute__((__unused__)) static struct hyperlinks_uri * hyperlinks_by_uri_tree_RB_INSERT(struct hyperlinks_by_uri_tree *head, struct hyperlinks_uri *elm) { struct hyperlinks_uri * tmp; struct hyperlinks_uri *parent = ((void *)0); int comp = 0 ; tmp = (head)->rbh_root; while (tmp) { parent = tmp; comp = (hyperlinks_by_uri_cmp)(elm, parent); if (comp < 0) tmp = (tmp)->by_uri_entry.rbe_left; else if (comp > 0) tmp = (tmp)->by_uri_entry.rbe_right; else return (tmp); } do { (elm)->by_uri_entry.rbe_parent = parent; (elm)->by_uri_entry .rbe_left = (elm)->by_uri_entry.rbe_right = ((void *)0); ( elm)->by_uri_entry.rbe_color = 1; } while (0); if (parent != ((void *)0)) { if (comp < 0) (parent)->by_uri_entry.rbe_left = elm; else (parent)->by_uri_entry.rbe_right = elm; do {} while (0); } else (head)->rbh_root = elm; hyperlinks_by_uri_tree_RB_INSERT_COLOR (head, elm); return (((void *)0)); } __attribute__((__unused__ )) static struct hyperlinks_uri * hyperlinks_by_uri_tree_RB_FIND (struct hyperlinks_by_uri_tree *head, struct hyperlinks_uri * elm) { struct hyperlinks_uri *tmp = (head)->rbh_root; int comp ; while (tmp) { comp = hyperlinks_by_uri_cmp(elm, tmp); if (comp < 0) tmp = (tmp)->by_uri_entry.rbe_left; else if (comp > 0) tmp = (tmp)->by_uri_entry.rbe_right; else return ( tmp); } return (((void *)0)); } __attribute__((__unused__)) static struct hyperlinks_uri * hyperlinks_by_uri_tree_RB_NFIND(struct hyperlinks_by_uri_tree *head, struct hyperlinks_uri *elm) { struct hyperlinks_uri *tmp = (head)->rbh_root; struct hyperlinks_uri *res = ((void *)0); int comp; while (tmp) { comp = hyperlinks_by_uri_cmp (elm, tmp); if (comp < 0) { res = tmp; tmp = (tmp)->by_uri_entry .rbe_left; } else if (comp > 0) tmp = (tmp)->by_uri_entry .rbe_right; else return (tmp); } return (res); } __attribute__ ((__unused__)) static struct hyperlinks_uri * hyperlinks_by_uri_tree_RB_NEXT (struct hyperlinks_uri *elm) { if ((elm)->by_uri_entry.rbe_right ) { elm = (elm)->by_uri_entry.rbe_right; while ((elm)-> by_uri_entry.rbe_left) elm = (elm)->by_uri_entry.rbe_left; } else { if ((elm)->by_uri_entry.rbe_parent && (elm == ((elm)->by_uri_entry.rbe_parent)->by_uri_entry.rbe_left )) elm = (elm)->by_uri_entry.rbe_parent; else { while ((elm )->by_uri_entry.rbe_parent && (elm == ((elm)->by_uri_entry .rbe_parent)->by_uri_entry.rbe_right)) elm = (elm)->by_uri_entry .rbe_parent; elm = (elm)->by_uri_entry.rbe_parent; } } return (elm); } __attribute__((__unused__)) static struct hyperlinks_uri * hyperlinks_by_uri_tree_RB_PREV(struct hyperlinks_uri *elm) { if ((elm)->by_uri_entry.rbe_left) { elm = (elm)->by_uri_entry .rbe_left; while ((elm)->by_uri_entry.rbe_right) elm = (elm )->by_uri_entry.rbe_right; } else { if ((elm)->by_uri_entry .rbe_parent && (elm == ((elm)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_right)) elm = (elm)->by_uri_entry.rbe_parent ; else { while ((elm)->by_uri_entry.rbe_parent && ( elm == ((elm)->by_uri_entry.rbe_parent)->by_uri_entry.rbe_left )) elm = (elm)->by_uri_entry.rbe_parent; elm = (elm)->by_uri_entry .rbe_parent; } } return (elm); } __attribute__((__unused__)) static struct hyperlinks_uri * hyperlinks_by_uri_tree_RB_MINMAX(struct hyperlinks_by_uri_tree *head, int val) { struct hyperlinks_uri *tmp = (head)->rbh_root; struct hyperlinks_uri *parent = ( (void *)0); while (tmp) { parent = tmp; if (val < 0) tmp = (tmp)->by_uri_entry.rbe_left; else tmp = (tmp)->by_uri_entry .rbe_right; } return (parent); } | |||
| 100 | hyperlinks_by_uri_cmp)__attribute__((__unused__)) static void hyperlinks_by_uri_tree_RB_INSERT_COLOR (struct hyperlinks_by_uri_tree *head, struct hyperlinks_uri * elm) { struct hyperlinks_uri *parent, *gparent, *tmp; while ( (parent = (elm)->by_uri_entry.rbe_parent) && (parent )->by_uri_entry.rbe_color == 1) { gparent = (parent)->by_uri_entry .rbe_parent; if (parent == (gparent)->by_uri_entry.rbe_left ) { tmp = (gparent)->by_uri_entry.rbe_right; if (tmp && (tmp)->by_uri_entry.rbe_color == 1) { (tmp)->by_uri_entry .rbe_color = 0; do { (parent)->by_uri_entry.rbe_color = 0; (gparent)->by_uri_entry.rbe_color = 1; } while (0); elm = gparent; continue; } if ((parent)->by_uri_entry.rbe_right == elm) { do { (tmp) = (parent)->by_uri_entry.rbe_right; if (((parent)->by_uri_entry.rbe_right = (tmp)->by_uri_entry .rbe_left)) { ((tmp)->by_uri_entry.rbe_left)->by_uri_entry .rbe_parent = (parent); } do {} while (0); if (((tmp)->by_uri_entry .rbe_parent = (parent)->by_uri_entry.rbe_parent)) { if ((parent ) == ((parent)->by_uri_entry.rbe_parent)->by_uri_entry. rbe_left) ((parent)->by_uri_entry.rbe_parent)->by_uri_entry .rbe_left = (tmp); else ((parent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_uri_entry.rbe_left = (parent); (parent )->by_uri_entry.rbe_parent = (tmp); do {} while (0); if (( (tmp)->by_uri_entry.rbe_parent)) do {} while (0); } while ( 0); tmp = parent; parent = elm; elm = tmp; } do { (parent)-> by_uri_entry.rbe_color = 0; (gparent)->by_uri_entry.rbe_color = 1; } while (0); do { (tmp) = (gparent)->by_uri_entry.rbe_left ; if (((gparent)->by_uri_entry.rbe_left = (tmp)->by_uri_entry .rbe_right)) { ((tmp)->by_uri_entry.rbe_right)->by_uri_entry .rbe_parent = (gparent); } do {} while (0); if (((tmp)->by_uri_entry .rbe_parent = (gparent)->by_uri_entry.rbe_parent)) { if (( gparent) == ((gparent)->by_uri_entry.rbe_parent)->by_uri_entry .rbe_left) ((gparent)->by_uri_entry.rbe_parent)->by_uri_entry .rbe_left = (tmp); else ((gparent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_uri_entry.rbe_right = (gparent); (gparent )->by_uri_entry.rbe_parent = (tmp); do {} while (0); if (( (tmp)->by_uri_entry.rbe_parent)) do {} while (0); } while ( 0); } else { tmp = (gparent)->by_uri_entry.rbe_left; if (tmp && (tmp)->by_uri_entry.rbe_color == 1) { (tmp)-> by_uri_entry.rbe_color = 0; do { (parent)->by_uri_entry.rbe_color = 0; (gparent)->by_uri_entry.rbe_color = 1; } while (0); elm = gparent; continue; } if ((parent)->by_uri_entry.rbe_left == elm) { do { (tmp) = (parent)->by_uri_entry.rbe_left; if (((parent)->by_uri_entry.rbe_left = (tmp)->by_uri_entry .rbe_right)) { ((tmp)->by_uri_entry.rbe_right)->by_uri_entry .rbe_parent = (parent); } do {} while (0); if (((tmp)->by_uri_entry .rbe_parent = (parent)->by_uri_entry.rbe_parent)) { if ((parent ) == ((parent)->by_uri_entry.rbe_parent)->by_uri_entry. rbe_left) ((parent)->by_uri_entry.rbe_parent)->by_uri_entry .rbe_left = (tmp); else ((parent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_uri_entry.rbe_right = (parent); (parent )->by_uri_entry.rbe_parent = (tmp); do {} while (0); if (( (tmp)->by_uri_entry.rbe_parent)) do {} while (0); } while ( 0); tmp = parent; parent = elm; elm = tmp; } do { (parent)-> by_uri_entry.rbe_color = 0; (gparent)->by_uri_entry.rbe_color = 1; } while (0); do { (tmp) = (gparent)->by_uri_entry.rbe_right ; if (((gparent)->by_uri_entry.rbe_right = (tmp)->by_uri_entry .rbe_left)) { ((tmp)->by_uri_entry.rbe_left)->by_uri_entry .rbe_parent = (gparent); } do {} while (0); if (((tmp)->by_uri_entry .rbe_parent = (gparent)->by_uri_entry.rbe_parent)) { if (( gparent) == ((gparent)->by_uri_entry.rbe_parent)->by_uri_entry .rbe_left) ((gparent)->by_uri_entry.rbe_parent)->by_uri_entry .rbe_left = (tmp); else ((gparent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_uri_entry.rbe_left = (gparent); (gparent )->by_uri_entry.rbe_parent = (tmp); do {} while (0); if (( (tmp)->by_uri_entry.rbe_parent)) do {} while (0); } while ( 0); } } (head->rbh_root)->by_uri_entry.rbe_color = 0; } __attribute__((__unused__)) static void hyperlinks_by_uri_tree_RB_REMOVE_COLOR (struct hyperlinks_by_uri_tree *head, struct hyperlinks_uri * parent, struct hyperlinks_uri *elm) { struct hyperlinks_uri * tmp; while ((elm == ((void *)0) || (elm)->by_uri_entry.rbe_color == 0) && elm != (head)->rbh_root) { if ((parent)-> by_uri_entry.rbe_left == elm) { tmp = (parent)->by_uri_entry .rbe_right; if ((tmp)->by_uri_entry.rbe_color == 1) { do { (tmp)->by_uri_entry.rbe_color = 0; (parent)->by_uri_entry .rbe_color = 1; } while (0); do { (tmp) = (parent)->by_uri_entry .rbe_right; if (((parent)->by_uri_entry.rbe_right = (tmp)-> by_uri_entry.rbe_left)) { ((tmp)->by_uri_entry.rbe_left)-> by_uri_entry.rbe_parent = (parent); } do {} while (0); if ((( tmp)->by_uri_entry.rbe_parent = (parent)->by_uri_entry. rbe_parent)) { if ((parent) == ((parent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_left) ((parent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_left = (tmp); else ((parent)->by_uri_entry .rbe_parent)->by_uri_entry.rbe_right = (tmp); } else (head )->rbh_root = (tmp); (tmp)->by_uri_entry.rbe_left = (parent ); (parent)->by_uri_entry.rbe_parent = (tmp); do {} while ( 0); if (((tmp)->by_uri_entry.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->by_uri_entry.rbe_right; } if (((tmp)->by_uri_entry.rbe_left == ((void *)0) || ((tmp)-> by_uri_entry.rbe_left)->by_uri_entry.rbe_color == 0) && ((tmp)->by_uri_entry.rbe_right == ((void *)0) || ((tmp)-> by_uri_entry.rbe_right)->by_uri_entry.rbe_color == 0)) { ( tmp)->by_uri_entry.rbe_color = 1; elm = parent; parent = ( elm)->by_uri_entry.rbe_parent; } else { if ((tmp)->by_uri_entry .rbe_right == ((void *)0) || ((tmp)->by_uri_entry.rbe_right )->by_uri_entry.rbe_color == 0) { struct hyperlinks_uri *oleft ; if ((oleft = (tmp)->by_uri_entry.rbe_left)) (oleft)-> by_uri_entry.rbe_color = 0; (tmp)->by_uri_entry.rbe_color = 1; do { (oleft) = (tmp)->by_uri_entry.rbe_left; if (((tmp )->by_uri_entry.rbe_left = (oleft)->by_uri_entry.rbe_right )) { ((oleft)->by_uri_entry.rbe_right)->by_uri_entry.rbe_parent = (tmp); } do {} while (0); if (((oleft)->by_uri_entry.rbe_parent = (tmp)->by_uri_entry.rbe_parent)) { if ((tmp) == ((tmp)-> by_uri_entry.rbe_parent)->by_uri_entry.rbe_left) ((tmp)-> by_uri_entry.rbe_parent)->by_uri_entry.rbe_left = (oleft); else ((tmp)->by_uri_entry.rbe_parent)->by_uri_entry.rbe_right = (oleft); } else (head)->rbh_root = (oleft); (oleft)-> by_uri_entry.rbe_right = (tmp); (tmp)->by_uri_entry.rbe_parent = (oleft); do {} while (0); if (((oleft)->by_uri_entry.rbe_parent )) do {} while (0); } while (0); tmp = (parent)->by_uri_entry .rbe_right; } (tmp)->by_uri_entry.rbe_color = (parent)-> by_uri_entry.rbe_color; (parent)->by_uri_entry.rbe_color = 0; if ((tmp)->by_uri_entry.rbe_right) ((tmp)->by_uri_entry .rbe_right)->by_uri_entry.rbe_color = 0; do { (tmp) = (parent )->by_uri_entry.rbe_right; if (((parent)->by_uri_entry. rbe_right = (tmp)->by_uri_entry.rbe_left)) { ((tmp)->by_uri_entry .rbe_left)->by_uri_entry.rbe_parent = (parent); } do {} while (0); if (((tmp)->by_uri_entry.rbe_parent = (parent)->by_uri_entry .rbe_parent)) { if ((parent) == ((parent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_left) ((parent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_left = (tmp); else ((parent)->by_uri_entry .rbe_parent)->by_uri_entry.rbe_right = (tmp); } else (head )->rbh_root = (tmp); (tmp)->by_uri_entry.rbe_left = (parent ); (parent)->by_uri_entry.rbe_parent = (tmp); do {} while ( 0); if (((tmp)->by_uri_entry.rbe_parent)) do {} while (0); } while (0); elm = (head)->rbh_root; break; } } else { tmp = (parent)->by_uri_entry.rbe_left; if ((tmp)->by_uri_entry .rbe_color == 1) { do { (tmp)->by_uri_entry.rbe_color = 0; (parent)->by_uri_entry.rbe_color = 1; } while (0); do { ( tmp) = (parent)->by_uri_entry.rbe_left; if (((parent)-> by_uri_entry.rbe_left = (tmp)->by_uri_entry.rbe_right)) { ( (tmp)->by_uri_entry.rbe_right)->by_uri_entry.rbe_parent = (parent); } do {} while (0); if (((tmp)->by_uri_entry.rbe_parent = (parent)->by_uri_entry.rbe_parent)) { if ((parent) == ( (parent)->by_uri_entry.rbe_parent)->by_uri_entry.rbe_left ) ((parent)->by_uri_entry.rbe_parent)->by_uri_entry.rbe_left = (tmp); else ((parent)->by_uri_entry.rbe_parent)->by_uri_entry .rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp) ->by_uri_entry.rbe_right = (parent); (parent)->by_uri_entry .rbe_parent = (tmp); do {} while (0); if (((tmp)->by_uri_entry .rbe_parent)) do {} while (0); } while (0); tmp = (parent)-> by_uri_entry.rbe_left; } if (((tmp)->by_uri_entry.rbe_left == ((void *)0) || ((tmp)->by_uri_entry.rbe_left)->by_uri_entry .rbe_color == 0) && ((tmp)->by_uri_entry.rbe_right == ((void *)0) || ((tmp)->by_uri_entry.rbe_right)->by_uri_entry .rbe_color == 0)) { (tmp)->by_uri_entry.rbe_color = 1; elm = parent; parent = (elm)->by_uri_entry.rbe_parent; } else { if ((tmp)->by_uri_entry.rbe_left == ((void *)0) || ((tmp )->by_uri_entry.rbe_left)->by_uri_entry.rbe_color == 0) { struct hyperlinks_uri *oright; if ((oright = (tmp)->by_uri_entry .rbe_right)) (oright)->by_uri_entry.rbe_color = 0; (tmp)-> by_uri_entry.rbe_color = 1; do { (oright) = (tmp)->by_uri_entry .rbe_right; if (((tmp)->by_uri_entry.rbe_right = (oright)-> by_uri_entry.rbe_left)) { ((oright)->by_uri_entry.rbe_left )->by_uri_entry.rbe_parent = (tmp); } do {} while (0); if ( ((oright)->by_uri_entry.rbe_parent = (tmp)->by_uri_entry .rbe_parent)) { if ((tmp) == ((tmp)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_left) ((tmp)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_left = (oright); else ((tmp)->by_uri_entry .rbe_parent)->by_uri_entry.rbe_right = (oright); } else (head )->rbh_root = (oright); (oright)->by_uri_entry.rbe_left = (tmp); (tmp)->by_uri_entry.rbe_parent = (oright); do {} while (0); if (((oright)->by_uri_entry.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->by_uri_entry.rbe_left ; } (tmp)->by_uri_entry.rbe_color = (parent)->by_uri_entry .rbe_color; (parent)->by_uri_entry.rbe_color = 0; if ((tmp )->by_uri_entry.rbe_left) ((tmp)->by_uri_entry.rbe_left )->by_uri_entry.rbe_color = 0; do { (tmp) = (parent)->by_uri_entry .rbe_left; if (((parent)->by_uri_entry.rbe_left = (tmp)-> by_uri_entry.rbe_right)) { ((tmp)->by_uri_entry.rbe_right) ->by_uri_entry.rbe_parent = (parent); } do {} while (0); if (((tmp)->by_uri_entry.rbe_parent = (parent)->by_uri_entry .rbe_parent)) { if ((parent) == ((parent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_left) ((parent)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_left = (tmp); else ((parent)->by_uri_entry .rbe_parent)->by_uri_entry.rbe_right = (tmp); } else (head )->rbh_root = (tmp); (tmp)->by_uri_entry.rbe_right = (parent ); (parent)->by_uri_entry.rbe_parent = (tmp); do {} while ( 0); if (((tmp)->by_uri_entry.rbe_parent)) do {} while (0); } while (0); elm = (head)->rbh_root; break; } } } if (elm ) (elm)->by_uri_entry.rbe_color = 0; } __attribute__((__unused__ )) static struct hyperlinks_uri * hyperlinks_by_uri_tree_RB_REMOVE (struct hyperlinks_by_uri_tree *head, struct hyperlinks_uri * elm) { struct hyperlinks_uri *child, *parent, *old = elm; int color; if ((elm)->by_uri_entry.rbe_left == ((void *)0)) child = (elm)->by_uri_entry.rbe_right; else if ((elm)->by_uri_entry .rbe_right == ((void *)0)) child = (elm)->by_uri_entry.rbe_left ; else { struct hyperlinks_uri *left; elm = (elm)->by_uri_entry .rbe_right; while ((left = (elm)->by_uri_entry.rbe_left)) elm = left; child = (elm)->by_uri_entry.rbe_right; parent = ( elm)->by_uri_entry.rbe_parent; color = (elm)->by_uri_entry .rbe_color; if (child) (child)->by_uri_entry.rbe_parent = parent ; if (parent) { if ((parent)->by_uri_entry.rbe_left == elm ) (parent)->by_uri_entry.rbe_left = child; else (parent)-> by_uri_entry.rbe_right = child; do {} while (0); } else (head )->rbh_root = child; if ((elm)->by_uri_entry.rbe_parent == old) parent = elm; (elm)->by_uri_entry = (old)->by_uri_entry ; if ((old)->by_uri_entry.rbe_parent) { if (((old)->by_uri_entry .rbe_parent)->by_uri_entry.rbe_left == old) ((old)->by_uri_entry .rbe_parent)->by_uri_entry.rbe_left = elm; else ((old)-> by_uri_entry.rbe_parent)->by_uri_entry.rbe_right = elm; do {} while (0); } else (head)->rbh_root = elm; ((old)->by_uri_entry .rbe_left)->by_uri_entry.rbe_parent = elm; if ((old)->by_uri_entry .rbe_right) ((old)->by_uri_entry.rbe_right)->by_uri_entry .rbe_parent = elm; if (parent) { left = parent; do { do {} while (0); } while ((left = (left)->by_uri_entry.rbe_parent)); } goto color; } parent = (elm)->by_uri_entry.rbe_parent; color = (elm)->by_uri_entry.rbe_color; if (child) (child)->by_uri_entry .rbe_parent = parent; if (parent) { if ((parent)->by_uri_entry .rbe_left == elm) (parent)->by_uri_entry.rbe_left = child; else (parent)->by_uri_entry.rbe_right = child; do {} while (0); } else (head)->rbh_root = child; color: if (color == 0) hyperlinks_by_uri_tree_RB_REMOVE_COLOR(head, parent, child ); return (old); } __attribute__((__unused__)) static struct hyperlinks_uri * hyperlinks_by_uri_tree_RB_INSERT(struct hyperlinks_by_uri_tree *head, struct hyperlinks_uri *elm) { struct hyperlinks_uri * tmp; struct hyperlinks_uri *parent = ((void *)0); int comp = 0 ; tmp = (head)->rbh_root; while (tmp) { parent = tmp; comp = (hyperlinks_by_uri_cmp)(elm, parent); if (comp < 0) tmp = (tmp)->by_uri_entry.rbe_left; else if (comp > 0) tmp = (tmp)->by_uri_entry.rbe_right; else return (tmp); } do { (elm)->by_uri_entry.rbe_parent = parent; (elm)->by_uri_entry .rbe_left = (elm)->by_uri_entry.rbe_right = ((void *)0); ( elm)->by_uri_entry.rbe_color = 1; } while (0); if (parent != ((void *)0)) { if (comp < 0) (parent)->by_uri_entry.rbe_left = elm; else (parent)->by_uri_entry.rbe_right = elm; do {} while (0); } else (head)->rbh_root = elm; hyperlinks_by_uri_tree_RB_INSERT_COLOR (head, elm); return (((void *)0)); } __attribute__((__unused__ )) static struct hyperlinks_uri * hyperlinks_by_uri_tree_RB_FIND (struct hyperlinks_by_uri_tree *head, struct hyperlinks_uri * elm) { struct hyperlinks_uri *tmp = (head)->rbh_root; int comp ; while (tmp) { comp = hyperlinks_by_uri_cmp(elm, tmp); if (comp < 0) tmp = (tmp)->by_uri_entry.rbe_left; else if (comp > 0) tmp = (tmp)->by_uri_entry.rbe_right; else return ( tmp); } return (((void *)0)); } __attribute__((__unused__)) static struct hyperlinks_uri * hyperlinks_by_uri_tree_RB_NFIND(struct hyperlinks_by_uri_tree *head, struct hyperlinks_uri *elm) { struct hyperlinks_uri *tmp = (head)->rbh_root; struct hyperlinks_uri *res = ((void *)0); int comp; while (tmp) { comp = hyperlinks_by_uri_cmp (elm, tmp); if (comp < 0) { res = tmp; tmp = (tmp)->by_uri_entry .rbe_left; } else if (comp > 0) tmp = (tmp)->by_uri_entry .rbe_right; else return (tmp); } return (res); } __attribute__ ((__unused__)) static struct hyperlinks_uri * hyperlinks_by_uri_tree_RB_NEXT (struct hyperlinks_uri *elm) { if ((elm)->by_uri_entry.rbe_right ) { elm = (elm)->by_uri_entry.rbe_right; while ((elm)-> by_uri_entry.rbe_left) elm = (elm)->by_uri_entry.rbe_left; } else { if ((elm)->by_uri_entry.rbe_parent && (elm == ((elm)->by_uri_entry.rbe_parent)->by_uri_entry.rbe_left )) elm = (elm)->by_uri_entry.rbe_parent; else { while ((elm )->by_uri_entry.rbe_parent && (elm == ((elm)->by_uri_entry .rbe_parent)->by_uri_entry.rbe_right)) elm = (elm)->by_uri_entry .rbe_parent; elm = (elm)->by_uri_entry.rbe_parent; } } return (elm); } __attribute__((__unused__)) static struct hyperlinks_uri * hyperlinks_by_uri_tree_RB_PREV(struct hyperlinks_uri *elm) { if ((elm)->by_uri_entry.rbe_left) { elm = (elm)->by_uri_entry .rbe_left; while ((elm)->by_uri_entry.rbe_right) elm = (elm )->by_uri_entry.rbe_right; } else { if ((elm)->by_uri_entry .rbe_parent && (elm == ((elm)->by_uri_entry.rbe_parent )->by_uri_entry.rbe_right)) elm = (elm)->by_uri_entry.rbe_parent ; else { while ((elm)->by_uri_entry.rbe_parent && ( elm == ((elm)->by_uri_entry.rbe_parent)->by_uri_entry.rbe_left )) elm = (elm)->by_uri_entry.rbe_parent; elm = (elm)->by_uri_entry .rbe_parent; } } return (elm); } __attribute__((__unused__)) static struct hyperlinks_uri * hyperlinks_by_uri_tree_RB_MINMAX(struct hyperlinks_by_uri_tree *head, int val) { struct hyperlinks_uri *tmp = (head)->rbh_root; struct hyperlinks_uri *parent = ( (void *)0); while (tmp) { parent = tmp; if (val < 0) tmp = (tmp)->by_uri_entry.rbe_left; else tmp = (tmp)->by_uri_entry .rbe_right; } return (parent); }; | |||
| 101 | ||||
| 102 | static int | |||
| 103 | hyperlinks_by_inner_cmp(struct hyperlinks_uri *left, | |||
| 104 | struct hyperlinks_uri *right) | |||
| 105 | { | |||
| 106 | return (left->inner - right->inner); | |||
| 107 | } | |||
| 108 | RB_PROTOTYPE_STATIC(hyperlinks_by_inner_tree, hyperlinks_uri, by_inner_entry,__attribute__((__unused__)) static void hyperlinks_by_inner_tree_RB_INSERT_COLOR (struct hyperlinks_by_inner_tree *, struct hyperlinks_uri *); __attribute__((__unused__)) static void hyperlinks_by_inner_tree_RB_REMOVE_COLOR (struct hyperlinks_by_inner_tree *, struct hyperlinks_uri *, struct hyperlinks_uri *);__attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_inner_tree_RB_REMOVE(struct hyperlinks_by_inner_tree *, struct hyperlinks_uri *); __attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_inner_tree_RB_INSERT(struct hyperlinks_by_inner_tree *, struct hyperlinks_uri *); __attribute__ ((__unused__)) static struct hyperlinks_uri *hyperlinks_by_inner_tree_RB_FIND (struct hyperlinks_by_inner_tree *, struct hyperlinks_uri *); __attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_inner_tree_RB_NFIND (struct hyperlinks_by_inner_tree *, struct hyperlinks_uri *); __attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_inner_tree_RB_NEXT (struct hyperlinks_uri *); __attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_inner_tree_RB_PREV(struct hyperlinks_uri *); __attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_inner_tree_RB_MINMAX(struct hyperlinks_by_inner_tree *, int); | |||
| 109 | hyperlinks_by_inner_cmp)__attribute__((__unused__)) static void hyperlinks_by_inner_tree_RB_INSERT_COLOR (struct hyperlinks_by_inner_tree *, struct hyperlinks_uri *); __attribute__((__unused__)) static void hyperlinks_by_inner_tree_RB_REMOVE_COLOR (struct hyperlinks_by_inner_tree *, struct hyperlinks_uri *, struct hyperlinks_uri *);__attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_inner_tree_RB_REMOVE(struct hyperlinks_by_inner_tree *, struct hyperlinks_uri *); __attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_inner_tree_RB_INSERT(struct hyperlinks_by_inner_tree *, struct hyperlinks_uri *); __attribute__ ((__unused__)) static struct hyperlinks_uri *hyperlinks_by_inner_tree_RB_FIND (struct hyperlinks_by_inner_tree *, struct hyperlinks_uri *); __attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_inner_tree_RB_NFIND (struct hyperlinks_by_inner_tree *, struct hyperlinks_uri *); __attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_inner_tree_RB_NEXT (struct hyperlinks_uri *); __attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_inner_tree_RB_PREV(struct hyperlinks_uri *); __attribute__((__unused__)) static struct hyperlinks_uri *hyperlinks_by_inner_tree_RB_MINMAX(struct hyperlinks_by_inner_tree *, int);; | |||
| 110 | RB_GENERATE_STATIC(hyperlinks_by_inner_tree, hyperlinks_uri, by_inner_entry,__attribute__((__unused__)) static void hyperlinks_by_inner_tree_RB_INSERT_COLOR (struct hyperlinks_by_inner_tree *head, struct hyperlinks_uri *elm) { struct hyperlinks_uri *parent, *gparent, *tmp; while ((parent = (elm)->by_inner_entry.rbe_parent) && ( parent)->by_inner_entry.rbe_color == 1) { gparent = (parent )->by_inner_entry.rbe_parent; if (parent == (gparent)-> by_inner_entry.rbe_left) { tmp = (gparent)->by_inner_entry .rbe_right; if (tmp && (tmp)->by_inner_entry.rbe_color == 1) { (tmp)->by_inner_entry.rbe_color = 0; do { (parent )->by_inner_entry.rbe_color = 0; (gparent)->by_inner_entry .rbe_color = 1; } while (0); elm = gparent; continue; } if (( parent)->by_inner_entry.rbe_right == elm) { do { (tmp) = ( parent)->by_inner_entry.rbe_right; if (((parent)->by_inner_entry .rbe_right = (tmp)->by_inner_entry.rbe_left)) { ((tmp)-> by_inner_entry.rbe_left)->by_inner_entry.rbe_parent = (parent ); } do {} while (0); if (((tmp)->by_inner_entry.rbe_parent = (parent)->by_inner_entry.rbe_parent)) { if ((parent) == ((parent)->by_inner_entry.rbe_parent)->by_inner_entry. rbe_left) ((parent)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_left = (tmp); else ((parent)->by_inner_entry.rbe_parent )->by_inner_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_inner_entry.rbe_left = (parent); (parent )->by_inner_entry.rbe_parent = (tmp); do {} while (0); if ( ((tmp)->by_inner_entry.rbe_parent)) do {} while (0); } while (0); tmp = parent; parent = elm; elm = tmp; } do { (parent)-> by_inner_entry.rbe_color = 0; (gparent)->by_inner_entry.rbe_color = 1; } while (0); do { (tmp) = (gparent)->by_inner_entry. rbe_left; if (((gparent)->by_inner_entry.rbe_left = (tmp)-> by_inner_entry.rbe_right)) { ((tmp)->by_inner_entry.rbe_right )->by_inner_entry.rbe_parent = (gparent); } do {} while (0 ); if (((tmp)->by_inner_entry.rbe_parent = (gparent)->by_inner_entry .rbe_parent)) { if ((gparent) == ((gparent)->by_inner_entry .rbe_parent)->by_inner_entry.rbe_left) ((gparent)->by_inner_entry .rbe_parent)->by_inner_entry.rbe_left = (tmp); else ((gparent )->by_inner_entry.rbe_parent)->by_inner_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_inner_entry .rbe_right = (gparent); (gparent)->by_inner_entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->by_inner_entry.rbe_parent )) do {} while (0); } while (0); } else { tmp = (gparent)-> by_inner_entry.rbe_left; if (tmp && (tmp)->by_inner_entry .rbe_color == 1) { (tmp)->by_inner_entry.rbe_color = 0; do { (parent)->by_inner_entry.rbe_color = 0; (gparent)->by_inner_entry .rbe_color = 1; } while (0); elm = gparent; continue; } if (( parent)->by_inner_entry.rbe_left == elm) { do { (tmp) = (parent )->by_inner_entry.rbe_left; if (((parent)->by_inner_entry .rbe_left = (tmp)->by_inner_entry.rbe_right)) { ((tmp)-> by_inner_entry.rbe_right)->by_inner_entry.rbe_parent = (parent ); } do {} while (0); if (((tmp)->by_inner_entry.rbe_parent = (parent)->by_inner_entry.rbe_parent)) { if ((parent) == ((parent)->by_inner_entry.rbe_parent)->by_inner_entry. rbe_left) ((parent)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_left = (tmp); else ((parent)->by_inner_entry.rbe_parent )->by_inner_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_inner_entry.rbe_right = (parent); (parent )->by_inner_entry.rbe_parent = (tmp); do {} while (0); if ( ((tmp)->by_inner_entry.rbe_parent)) do {} while (0); } while (0); tmp = parent; parent = elm; elm = tmp; } do { (parent)-> by_inner_entry.rbe_color = 0; (gparent)->by_inner_entry.rbe_color = 1; } while (0); do { (tmp) = (gparent)->by_inner_entry. rbe_right; if (((gparent)->by_inner_entry.rbe_right = (tmp )->by_inner_entry.rbe_left)) { ((tmp)->by_inner_entry.rbe_left )->by_inner_entry.rbe_parent = (gparent); } do {} while (0 ); if (((tmp)->by_inner_entry.rbe_parent = (gparent)->by_inner_entry .rbe_parent)) { if ((gparent) == ((gparent)->by_inner_entry .rbe_parent)->by_inner_entry.rbe_left) ((gparent)->by_inner_entry .rbe_parent)->by_inner_entry.rbe_left = (tmp); else ((gparent )->by_inner_entry.rbe_parent)->by_inner_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_inner_entry .rbe_left = (gparent); (gparent)->by_inner_entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->by_inner_entry.rbe_parent )) do {} while (0); } while (0); } } (head->rbh_root)-> by_inner_entry.rbe_color = 0; } __attribute__((__unused__)) static void hyperlinks_by_inner_tree_RB_REMOVE_COLOR(struct hyperlinks_by_inner_tree *head, struct hyperlinks_uri *parent, struct hyperlinks_uri * elm) { struct hyperlinks_uri *tmp; while ((elm == ((void *)0) || (elm)->by_inner_entry.rbe_color == 0) && elm != (head)->rbh_root) { if ((parent)->by_inner_entry.rbe_left == elm) { tmp = (parent)->by_inner_entry.rbe_right; if (( tmp)->by_inner_entry.rbe_color == 1) { do { (tmp)->by_inner_entry .rbe_color = 0; (parent)->by_inner_entry.rbe_color = 1; } while (0); do { (tmp) = (parent)->by_inner_entry.rbe_right; if ( ((parent)->by_inner_entry.rbe_right = (tmp)->by_inner_entry .rbe_left)) { ((tmp)->by_inner_entry.rbe_left)->by_inner_entry .rbe_parent = (parent); } do {} while (0); if (((tmp)->by_inner_entry .rbe_parent = (parent)->by_inner_entry.rbe_parent)) { if ( (parent) == ((parent)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_left) ((parent)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_left = (tmp); else ((parent)->by_inner_entry.rbe_parent )->by_inner_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_inner_entry.rbe_left = (parent); (parent )->by_inner_entry.rbe_parent = (tmp); do {} while (0); if ( ((tmp)->by_inner_entry.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->by_inner_entry.rbe_right; } if (((tmp )->by_inner_entry.rbe_left == ((void *)0) || ((tmp)->by_inner_entry .rbe_left)->by_inner_entry.rbe_color == 0) && ((tmp )->by_inner_entry.rbe_right == ((void *)0) || ((tmp)->by_inner_entry .rbe_right)->by_inner_entry.rbe_color == 0)) { (tmp)->by_inner_entry .rbe_color = 1; elm = parent; parent = (elm)->by_inner_entry .rbe_parent; } else { if ((tmp)->by_inner_entry.rbe_right == ((void *)0) || ((tmp)->by_inner_entry.rbe_right)->by_inner_entry .rbe_color == 0) { struct hyperlinks_uri *oleft; if ((oleft = (tmp)->by_inner_entry.rbe_left)) (oleft)->by_inner_entry .rbe_color = 0; (tmp)->by_inner_entry.rbe_color = 1; do { ( oleft) = (tmp)->by_inner_entry.rbe_left; if (((tmp)->by_inner_entry .rbe_left = (oleft)->by_inner_entry.rbe_right)) { ((oleft) ->by_inner_entry.rbe_right)->by_inner_entry.rbe_parent = (tmp); } do {} while (0); if (((oleft)->by_inner_entry.rbe_parent = (tmp)->by_inner_entry.rbe_parent)) { if ((tmp) == ((tmp )->by_inner_entry.rbe_parent)->by_inner_entry.rbe_left) ((tmp)->by_inner_entry.rbe_parent)->by_inner_entry.rbe_left = (oleft); else ((tmp)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_right = (oleft); } else (head)->rbh_root = (oleft); ( oleft)->by_inner_entry.rbe_right = (tmp); (tmp)->by_inner_entry .rbe_parent = (oleft); do {} while (0); if (((oleft)->by_inner_entry .rbe_parent)) do {} while (0); } while (0); tmp = (parent)-> by_inner_entry.rbe_right; } (tmp)->by_inner_entry.rbe_color = (parent)->by_inner_entry.rbe_color; (parent)->by_inner_entry .rbe_color = 0; if ((tmp)->by_inner_entry.rbe_right) ((tmp )->by_inner_entry.rbe_right)->by_inner_entry.rbe_color = 0; do { (tmp) = (parent)->by_inner_entry.rbe_right; if (( (parent)->by_inner_entry.rbe_right = (tmp)->by_inner_entry .rbe_left)) { ((tmp)->by_inner_entry.rbe_left)->by_inner_entry .rbe_parent = (parent); } do {} while (0); if (((tmp)->by_inner_entry .rbe_parent = (parent)->by_inner_entry.rbe_parent)) { if ( (parent) == ((parent)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_left) ((parent)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_left = (tmp); else ((parent)->by_inner_entry.rbe_parent )->by_inner_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_inner_entry.rbe_left = (parent); (parent )->by_inner_entry.rbe_parent = (tmp); do {} while (0); if ( ((tmp)->by_inner_entry.rbe_parent)) do {} while (0); } while (0); elm = (head)->rbh_root; break; } } else { tmp = (parent )->by_inner_entry.rbe_left; if ((tmp)->by_inner_entry.rbe_color == 1) { do { (tmp)->by_inner_entry.rbe_color = 0; (parent )->by_inner_entry.rbe_color = 1; } while (0); do { (tmp) = (parent)->by_inner_entry.rbe_left; if (((parent)->by_inner_entry .rbe_left = (tmp)->by_inner_entry.rbe_right)) { ((tmp)-> by_inner_entry.rbe_right)->by_inner_entry.rbe_parent = (parent ); } do {} while (0); if (((tmp)->by_inner_entry.rbe_parent = (parent)->by_inner_entry.rbe_parent)) { if ((parent) == ((parent)->by_inner_entry.rbe_parent)->by_inner_entry. rbe_left) ((parent)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_left = (tmp); else ((parent)->by_inner_entry.rbe_parent )->by_inner_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_inner_entry.rbe_right = (parent); (parent )->by_inner_entry.rbe_parent = (tmp); do {} while (0); if ( ((tmp)->by_inner_entry.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->by_inner_entry.rbe_left; } if (((tmp )->by_inner_entry.rbe_left == ((void *)0) || ((tmp)->by_inner_entry .rbe_left)->by_inner_entry.rbe_color == 0) && ((tmp )->by_inner_entry.rbe_right == ((void *)0) || ((tmp)->by_inner_entry .rbe_right)->by_inner_entry.rbe_color == 0)) { (tmp)->by_inner_entry .rbe_color = 1; elm = parent; parent = (elm)->by_inner_entry .rbe_parent; } else { if ((tmp)->by_inner_entry.rbe_left == ((void *)0) || ((tmp)->by_inner_entry.rbe_left)->by_inner_entry .rbe_color == 0) { struct hyperlinks_uri *oright; if ((oright = (tmp)->by_inner_entry.rbe_right)) (oright)->by_inner_entry .rbe_color = 0; (tmp)->by_inner_entry.rbe_color = 1; do { ( oright) = (tmp)->by_inner_entry.rbe_right; if (((tmp)-> by_inner_entry.rbe_right = (oright)->by_inner_entry.rbe_left )) { ((oright)->by_inner_entry.rbe_left)->by_inner_entry .rbe_parent = (tmp); } do {} while (0); if (((oright)->by_inner_entry .rbe_parent = (tmp)->by_inner_entry.rbe_parent)) { if ((tmp ) == ((tmp)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_left) ((tmp)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_left = (oright); else ((tmp)->by_inner_entry.rbe_parent )->by_inner_entry.rbe_right = (oright); } else (head)-> rbh_root = (oright); (oright)->by_inner_entry.rbe_left = ( tmp); (tmp)->by_inner_entry.rbe_parent = (oright); do {} while (0); if (((oright)->by_inner_entry.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->by_inner_entry.rbe_left ; } (tmp)->by_inner_entry.rbe_color = (parent)->by_inner_entry .rbe_color; (parent)->by_inner_entry.rbe_color = 0; if ((tmp )->by_inner_entry.rbe_left) ((tmp)->by_inner_entry.rbe_left )->by_inner_entry.rbe_color = 0; do { (tmp) = (parent)-> by_inner_entry.rbe_left; if (((parent)->by_inner_entry.rbe_left = (tmp)->by_inner_entry.rbe_right)) { ((tmp)->by_inner_entry .rbe_right)->by_inner_entry.rbe_parent = (parent); } do {} while (0); if (((tmp)->by_inner_entry.rbe_parent = (parent )->by_inner_entry.rbe_parent)) { if ((parent) == ((parent) ->by_inner_entry.rbe_parent)->by_inner_entry.rbe_left) ( (parent)->by_inner_entry.rbe_parent)->by_inner_entry.rbe_left = (tmp); else ((parent)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp) ->by_inner_entry.rbe_right = (parent); (parent)->by_inner_entry .rbe_parent = (tmp); do {} while (0); if (((tmp)->by_inner_entry .rbe_parent)) do {} while (0); } while (0); elm = (head)-> rbh_root; break; } } } if (elm) (elm)->by_inner_entry.rbe_color = 0; } __attribute__((__unused__)) static struct hyperlinks_uri * hyperlinks_by_inner_tree_RB_REMOVE(struct hyperlinks_by_inner_tree *head, struct hyperlinks_uri *elm) { struct hyperlinks_uri * child, *parent, *old = elm; int color; if ((elm)->by_inner_entry .rbe_left == ((void *)0)) child = (elm)->by_inner_entry.rbe_right ; else if ((elm)->by_inner_entry.rbe_right == ((void *)0)) child = (elm)->by_inner_entry.rbe_left; else { struct hyperlinks_uri *left; elm = (elm)->by_inner_entry.rbe_right; while ((left = (elm)->by_inner_entry.rbe_left)) elm = left; child = (elm )->by_inner_entry.rbe_right; parent = (elm)->by_inner_entry .rbe_parent; color = (elm)->by_inner_entry.rbe_color; if ( child) (child)->by_inner_entry.rbe_parent = parent; if (parent ) { if ((parent)->by_inner_entry.rbe_left == elm) (parent) ->by_inner_entry.rbe_left = child; else (parent)->by_inner_entry .rbe_right = child; do {} while (0); } else (head)->rbh_root = child; if ((elm)->by_inner_entry.rbe_parent == old) parent = elm; (elm)->by_inner_entry = (old)->by_inner_entry; if ((old)->by_inner_entry.rbe_parent) { if (((old)->by_inner_entry .rbe_parent)->by_inner_entry.rbe_left == old) ((old)->by_inner_entry .rbe_parent)->by_inner_entry.rbe_left = elm; else ((old)-> by_inner_entry.rbe_parent)->by_inner_entry.rbe_right = elm ; do {} while (0); } else (head)->rbh_root = elm; ((old)-> by_inner_entry.rbe_left)->by_inner_entry.rbe_parent = elm; if ((old)->by_inner_entry.rbe_right) ((old)->by_inner_entry .rbe_right)->by_inner_entry.rbe_parent = elm; if (parent) { left = parent; do { do {} while (0); } while ((left = (left) ->by_inner_entry.rbe_parent)); } goto color; } parent = (elm )->by_inner_entry.rbe_parent; color = (elm)->by_inner_entry .rbe_color; if (child) (child)->by_inner_entry.rbe_parent = parent; if (parent) { if ((parent)->by_inner_entry.rbe_left == elm) (parent)->by_inner_entry.rbe_left = child; else ( parent)->by_inner_entry.rbe_right = child; do {} while (0) ; } else (head)->rbh_root = child; color: if (color == 0) hyperlinks_by_inner_tree_RB_REMOVE_COLOR (head, parent, child); return (old); } __attribute__((__unused__ )) static struct hyperlinks_uri * hyperlinks_by_inner_tree_RB_INSERT (struct hyperlinks_by_inner_tree *head, struct hyperlinks_uri *elm) { struct hyperlinks_uri *tmp; struct hyperlinks_uri *parent = ((void *)0); int comp = 0; tmp = (head)->rbh_root; while (tmp) { parent = tmp; comp = (hyperlinks_by_inner_cmp)(elm, parent ); if (comp < 0) tmp = (tmp)->by_inner_entry.rbe_left; else if (comp > 0) tmp = (tmp)->by_inner_entry.rbe_right; else return (tmp); } do { (elm)->by_inner_entry.rbe_parent = parent ; (elm)->by_inner_entry.rbe_left = (elm)->by_inner_entry .rbe_right = ((void *)0); (elm)->by_inner_entry.rbe_color = 1; } while (0); if (parent != ((void *)0)) { if (comp < 0 ) (parent)->by_inner_entry.rbe_left = elm; else (parent)-> by_inner_entry.rbe_right = elm; do {} while (0); } else (head )->rbh_root = elm; hyperlinks_by_inner_tree_RB_INSERT_COLOR (head, elm); return (((void *)0)); } __attribute__((__unused__ )) static struct hyperlinks_uri * hyperlinks_by_inner_tree_RB_FIND (struct hyperlinks_by_inner_tree *head, struct hyperlinks_uri *elm) { struct hyperlinks_uri *tmp = (head)->rbh_root; int comp; while (tmp) { comp = hyperlinks_by_inner_cmp(elm, tmp) ; if (comp < 0) tmp = (tmp)->by_inner_entry.rbe_left; else if (comp > 0) tmp = (tmp)->by_inner_entry.rbe_right; else return (tmp); } return (((void *)0)); } __attribute__((__unused__ )) static struct hyperlinks_uri * hyperlinks_by_inner_tree_RB_NFIND (struct hyperlinks_by_inner_tree *head, struct hyperlinks_uri *elm) { struct hyperlinks_uri *tmp = (head)->rbh_root; struct hyperlinks_uri *res = ((void *)0); int comp; while (tmp) { comp = hyperlinks_by_inner_cmp(elm, tmp); if (comp < 0) { res = tmp; tmp = (tmp)->by_inner_entry.rbe_left; } else if (comp > 0) tmp = (tmp)->by_inner_entry.rbe_right; else return (tmp); } return (res); } __attribute__((__unused__)) static struct hyperlinks_uri * hyperlinks_by_inner_tree_RB_NEXT(struct hyperlinks_uri *elm) { if ((elm)->by_inner_entry.rbe_right) { elm = (elm )->by_inner_entry.rbe_right; while ((elm)->by_inner_entry .rbe_left) elm = (elm)->by_inner_entry.rbe_left; } else { if ((elm)->by_inner_entry.rbe_parent && (elm == ((elm )->by_inner_entry.rbe_parent)->by_inner_entry.rbe_left) ) elm = (elm)->by_inner_entry.rbe_parent; else { while ((elm )->by_inner_entry.rbe_parent && (elm == ((elm)-> by_inner_entry.rbe_parent)->by_inner_entry.rbe_right)) elm = (elm)->by_inner_entry.rbe_parent; elm = (elm)->by_inner_entry .rbe_parent; } } return (elm); } __attribute__((__unused__)) static struct hyperlinks_uri * hyperlinks_by_inner_tree_RB_PREV(struct hyperlinks_uri *elm) { if ((elm)->by_inner_entry.rbe_left ) { elm = (elm)->by_inner_entry.rbe_left; while ((elm)-> by_inner_entry.rbe_right) elm = (elm)->by_inner_entry.rbe_right ; } else { if ((elm)->by_inner_entry.rbe_parent && (elm == ((elm)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_right)) elm = (elm)->by_inner_entry.rbe_parent; else { while ((elm)->by_inner_entry.rbe_parent && (elm == ((elm)->by_inner_entry.rbe_parent)->by_inner_entry.rbe_left )) elm = (elm)->by_inner_entry.rbe_parent; elm = (elm)-> by_inner_entry.rbe_parent; } } return (elm); } __attribute__( (__unused__)) static struct hyperlinks_uri * hyperlinks_by_inner_tree_RB_MINMAX (struct hyperlinks_by_inner_tree *head, int val) { struct hyperlinks_uri *tmp = (head)->rbh_root; struct hyperlinks_uri *parent = ( (void *)0); while (tmp) { parent = tmp; if (val < 0) tmp = (tmp)->by_inner_entry.rbe_left; else tmp = (tmp)->by_inner_entry .rbe_right; } return (parent); } | |||
| 111 | hyperlinks_by_inner_cmp)__attribute__((__unused__)) static void hyperlinks_by_inner_tree_RB_INSERT_COLOR (struct hyperlinks_by_inner_tree *head, struct hyperlinks_uri *elm) { struct hyperlinks_uri *parent, *gparent, *tmp; while ((parent = (elm)->by_inner_entry.rbe_parent) && ( parent)->by_inner_entry.rbe_color == 1) { gparent = (parent )->by_inner_entry.rbe_parent; if (parent == (gparent)-> by_inner_entry.rbe_left) { tmp = (gparent)->by_inner_entry .rbe_right; if (tmp && (tmp)->by_inner_entry.rbe_color == 1) { (tmp)->by_inner_entry.rbe_color = 0; do { (parent )->by_inner_entry.rbe_color = 0; (gparent)->by_inner_entry .rbe_color = 1; } while (0); elm = gparent; continue; } if (( parent)->by_inner_entry.rbe_right == elm) { do { (tmp) = ( parent)->by_inner_entry.rbe_right; if (((parent)->by_inner_entry .rbe_right = (tmp)->by_inner_entry.rbe_left)) { ((tmp)-> by_inner_entry.rbe_left)->by_inner_entry.rbe_parent = (parent ); } do {} while (0); if (((tmp)->by_inner_entry.rbe_parent = (parent)->by_inner_entry.rbe_parent)) { if ((parent) == ((parent)->by_inner_entry.rbe_parent)->by_inner_entry. rbe_left) ((parent)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_left = (tmp); else ((parent)->by_inner_entry.rbe_parent )->by_inner_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_inner_entry.rbe_left = (parent); (parent )->by_inner_entry.rbe_parent = (tmp); do {} while (0); if ( ((tmp)->by_inner_entry.rbe_parent)) do {} while (0); } while (0); tmp = parent; parent = elm; elm = tmp; } do { (parent)-> by_inner_entry.rbe_color = 0; (gparent)->by_inner_entry.rbe_color = 1; } while (0); do { (tmp) = (gparent)->by_inner_entry. rbe_left; if (((gparent)->by_inner_entry.rbe_left = (tmp)-> by_inner_entry.rbe_right)) { ((tmp)->by_inner_entry.rbe_right )->by_inner_entry.rbe_parent = (gparent); } do {} while (0 ); if (((tmp)->by_inner_entry.rbe_parent = (gparent)->by_inner_entry .rbe_parent)) { if ((gparent) == ((gparent)->by_inner_entry .rbe_parent)->by_inner_entry.rbe_left) ((gparent)->by_inner_entry .rbe_parent)->by_inner_entry.rbe_left = (tmp); else ((gparent )->by_inner_entry.rbe_parent)->by_inner_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_inner_entry .rbe_right = (gparent); (gparent)->by_inner_entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->by_inner_entry.rbe_parent )) do {} while (0); } while (0); } else { tmp = (gparent)-> by_inner_entry.rbe_left; if (tmp && (tmp)->by_inner_entry .rbe_color == 1) { (tmp)->by_inner_entry.rbe_color = 0; do { (parent)->by_inner_entry.rbe_color = 0; (gparent)->by_inner_entry .rbe_color = 1; } while (0); elm = gparent; continue; } if (( parent)->by_inner_entry.rbe_left == elm) { do { (tmp) = (parent )->by_inner_entry.rbe_left; if (((parent)->by_inner_entry .rbe_left = (tmp)->by_inner_entry.rbe_right)) { ((tmp)-> by_inner_entry.rbe_right)->by_inner_entry.rbe_parent = (parent ); } do {} while (0); if (((tmp)->by_inner_entry.rbe_parent = (parent)->by_inner_entry.rbe_parent)) { if ((parent) == ((parent)->by_inner_entry.rbe_parent)->by_inner_entry. rbe_left) ((parent)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_left = (tmp); else ((parent)->by_inner_entry.rbe_parent )->by_inner_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_inner_entry.rbe_right = (parent); (parent )->by_inner_entry.rbe_parent = (tmp); do {} while (0); if ( ((tmp)->by_inner_entry.rbe_parent)) do {} while (0); } while (0); tmp = parent; parent = elm; elm = tmp; } do { (parent)-> by_inner_entry.rbe_color = 0; (gparent)->by_inner_entry.rbe_color = 1; } while (0); do { (tmp) = (gparent)->by_inner_entry. rbe_right; if (((gparent)->by_inner_entry.rbe_right = (tmp )->by_inner_entry.rbe_left)) { ((tmp)->by_inner_entry.rbe_left )->by_inner_entry.rbe_parent = (gparent); } do {} while (0 ); if (((tmp)->by_inner_entry.rbe_parent = (gparent)->by_inner_entry .rbe_parent)) { if ((gparent) == ((gparent)->by_inner_entry .rbe_parent)->by_inner_entry.rbe_left) ((gparent)->by_inner_entry .rbe_parent)->by_inner_entry.rbe_left = (tmp); else ((gparent )->by_inner_entry.rbe_parent)->by_inner_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_inner_entry .rbe_left = (gparent); (gparent)->by_inner_entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->by_inner_entry.rbe_parent )) do {} while (0); } while (0); } } (head->rbh_root)-> by_inner_entry.rbe_color = 0; } __attribute__((__unused__)) static void hyperlinks_by_inner_tree_RB_REMOVE_COLOR(struct hyperlinks_by_inner_tree *head, struct hyperlinks_uri *parent, struct hyperlinks_uri * elm) { struct hyperlinks_uri *tmp; while ((elm == ((void *)0) || (elm)->by_inner_entry.rbe_color == 0) && elm != (head)->rbh_root) { if ((parent)->by_inner_entry.rbe_left == elm) { tmp = (parent)->by_inner_entry.rbe_right; if (( tmp)->by_inner_entry.rbe_color == 1) { do { (tmp)->by_inner_entry .rbe_color = 0; (parent)->by_inner_entry.rbe_color = 1; } while (0); do { (tmp) = (parent)->by_inner_entry.rbe_right; if ( ((parent)->by_inner_entry.rbe_right = (tmp)->by_inner_entry .rbe_left)) { ((tmp)->by_inner_entry.rbe_left)->by_inner_entry .rbe_parent = (parent); } do {} while (0); if (((tmp)->by_inner_entry .rbe_parent = (parent)->by_inner_entry.rbe_parent)) { if ( (parent) == ((parent)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_left) ((parent)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_left = (tmp); else ((parent)->by_inner_entry.rbe_parent )->by_inner_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_inner_entry.rbe_left = (parent); (parent )->by_inner_entry.rbe_parent = (tmp); do {} while (0); if ( ((tmp)->by_inner_entry.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->by_inner_entry.rbe_right; } if (((tmp )->by_inner_entry.rbe_left == ((void *)0) || ((tmp)->by_inner_entry .rbe_left)->by_inner_entry.rbe_color == 0) && ((tmp )->by_inner_entry.rbe_right == ((void *)0) || ((tmp)->by_inner_entry .rbe_right)->by_inner_entry.rbe_color == 0)) { (tmp)->by_inner_entry .rbe_color = 1; elm = parent; parent = (elm)->by_inner_entry .rbe_parent; } else { if ((tmp)->by_inner_entry.rbe_right == ((void *)0) || ((tmp)->by_inner_entry.rbe_right)->by_inner_entry .rbe_color == 0) { struct hyperlinks_uri *oleft; if ((oleft = (tmp)->by_inner_entry.rbe_left)) (oleft)->by_inner_entry .rbe_color = 0; (tmp)->by_inner_entry.rbe_color = 1; do { ( oleft) = (tmp)->by_inner_entry.rbe_left; if (((tmp)->by_inner_entry .rbe_left = (oleft)->by_inner_entry.rbe_right)) { ((oleft) ->by_inner_entry.rbe_right)->by_inner_entry.rbe_parent = (tmp); } do {} while (0); if (((oleft)->by_inner_entry.rbe_parent = (tmp)->by_inner_entry.rbe_parent)) { if ((tmp) == ((tmp )->by_inner_entry.rbe_parent)->by_inner_entry.rbe_left) ((tmp)->by_inner_entry.rbe_parent)->by_inner_entry.rbe_left = (oleft); else ((tmp)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_right = (oleft); } else (head)->rbh_root = (oleft); ( oleft)->by_inner_entry.rbe_right = (tmp); (tmp)->by_inner_entry .rbe_parent = (oleft); do {} while (0); if (((oleft)->by_inner_entry .rbe_parent)) do {} while (0); } while (0); tmp = (parent)-> by_inner_entry.rbe_right; } (tmp)->by_inner_entry.rbe_color = (parent)->by_inner_entry.rbe_color; (parent)->by_inner_entry .rbe_color = 0; if ((tmp)->by_inner_entry.rbe_right) ((tmp )->by_inner_entry.rbe_right)->by_inner_entry.rbe_color = 0; do { (tmp) = (parent)->by_inner_entry.rbe_right; if (( (parent)->by_inner_entry.rbe_right = (tmp)->by_inner_entry .rbe_left)) { ((tmp)->by_inner_entry.rbe_left)->by_inner_entry .rbe_parent = (parent); } do {} while (0); if (((tmp)->by_inner_entry .rbe_parent = (parent)->by_inner_entry.rbe_parent)) { if ( (parent) == ((parent)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_left) ((parent)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_left = (tmp); else ((parent)->by_inner_entry.rbe_parent )->by_inner_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_inner_entry.rbe_left = (parent); (parent )->by_inner_entry.rbe_parent = (tmp); do {} while (0); if ( ((tmp)->by_inner_entry.rbe_parent)) do {} while (0); } while (0); elm = (head)->rbh_root; break; } } else { tmp = (parent )->by_inner_entry.rbe_left; if ((tmp)->by_inner_entry.rbe_color == 1) { do { (tmp)->by_inner_entry.rbe_color = 0; (parent )->by_inner_entry.rbe_color = 1; } while (0); do { (tmp) = (parent)->by_inner_entry.rbe_left; if (((parent)->by_inner_entry .rbe_left = (tmp)->by_inner_entry.rbe_right)) { ((tmp)-> by_inner_entry.rbe_right)->by_inner_entry.rbe_parent = (parent ); } do {} while (0); if (((tmp)->by_inner_entry.rbe_parent = (parent)->by_inner_entry.rbe_parent)) { if ((parent) == ((parent)->by_inner_entry.rbe_parent)->by_inner_entry. rbe_left) ((parent)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_left = (tmp); else ((parent)->by_inner_entry.rbe_parent )->by_inner_entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->by_inner_entry.rbe_right = (parent); (parent )->by_inner_entry.rbe_parent = (tmp); do {} while (0); if ( ((tmp)->by_inner_entry.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->by_inner_entry.rbe_left; } if (((tmp )->by_inner_entry.rbe_left == ((void *)0) || ((tmp)->by_inner_entry .rbe_left)->by_inner_entry.rbe_color == 0) && ((tmp )->by_inner_entry.rbe_right == ((void *)0) || ((tmp)->by_inner_entry .rbe_right)->by_inner_entry.rbe_color == 0)) { (tmp)->by_inner_entry .rbe_color = 1; elm = parent; parent = (elm)->by_inner_entry .rbe_parent; } else { if ((tmp)->by_inner_entry.rbe_left == ((void *)0) || ((tmp)->by_inner_entry.rbe_left)->by_inner_entry .rbe_color == 0) { struct hyperlinks_uri *oright; if ((oright = (tmp)->by_inner_entry.rbe_right)) (oright)->by_inner_entry .rbe_color = 0; (tmp)->by_inner_entry.rbe_color = 1; do { ( oright) = (tmp)->by_inner_entry.rbe_right; if (((tmp)-> by_inner_entry.rbe_right = (oright)->by_inner_entry.rbe_left )) { ((oright)->by_inner_entry.rbe_left)->by_inner_entry .rbe_parent = (tmp); } do {} while (0); if (((oright)->by_inner_entry .rbe_parent = (tmp)->by_inner_entry.rbe_parent)) { if ((tmp ) == ((tmp)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_left) ((tmp)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_left = (oright); else ((tmp)->by_inner_entry.rbe_parent )->by_inner_entry.rbe_right = (oright); } else (head)-> rbh_root = (oright); (oright)->by_inner_entry.rbe_left = ( tmp); (tmp)->by_inner_entry.rbe_parent = (oright); do {} while (0); if (((oright)->by_inner_entry.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->by_inner_entry.rbe_left ; } (tmp)->by_inner_entry.rbe_color = (parent)->by_inner_entry .rbe_color; (parent)->by_inner_entry.rbe_color = 0; if ((tmp )->by_inner_entry.rbe_left) ((tmp)->by_inner_entry.rbe_left )->by_inner_entry.rbe_color = 0; do { (tmp) = (parent)-> by_inner_entry.rbe_left; if (((parent)->by_inner_entry.rbe_left = (tmp)->by_inner_entry.rbe_right)) { ((tmp)->by_inner_entry .rbe_right)->by_inner_entry.rbe_parent = (parent); } do {} while (0); if (((tmp)->by_inner_entry.rbe_parent = (parent )->by_inner_entry.rbe_parent)) { if ((parent) == ((parent) ->by_inner_entry.rbe_parent)->by_inner_entry.rbe_left) ( (parent)->by_inner_entry.rbe_parent)->by_inner_entry.rbe_left = (tmp); else ((parent)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp) ->by_inner_entry.rbe_right = (parent); (parent)->by_inner_entry .rbe_parent = (tmp); do {} while (0); if (((tmp)->by_inner_entry .rbe_parent)) do {} while (0); } while (0); elm = (head)-> rbh_root; break; } } } if (elm) (elm)->by_inner_entry.rbe_color = 0; } __attribute__((__unused__)) static struct hyperlinks_uri * hyperlinks_by_inner_tree_RB_REMOVE(struct hyperlinks_by_inner_tree *head, struct hyperlinks_uri *elm) { struct hyperlinks_uri * child, *parent, *old = elm; int color; if ((elm)->by_inner_entry .rbe_left == ((void *)0)) child = (elm)->by_inner_entry.rbe_right ; else if ((elm)->by_inner_entry.rbe_right == ((void *)0)) child = (elm)->by_inner_entry.rbe_left; else { struct hyperlinks_uri *left; elm = (elm)->by_inner_entry.rbe_right; while ((left = (elm)->by_inner_entry.rbe_left)) elm = left; child = (elm )->by_inner_entry.rbe_right; parent = (elm)->by_inner_entry .rbe_parent; color = (elm)->by_inner_entry.rbe_color; if ( child) (child)->by_inner_entry.rbe_parent = parent; if (parent ) { if ((parent)->by_inner_entry.rbe_left == elm) (parent) ->by_inner_entry.rbe_left = child; else (parent)->by_inner_entry .rbe_right = child; do {} while (0); } else (head)->rbh_root = child; if ((elm)->by_inner_entry.rbe_parent == old) parent = elm; (elm)->by_inner_entry = (old)->by_inner_entry; if ((old)->by_inner_entry.rbe_parent) { if (((old)->by_inner_entry .rbe_parent)->by_inner_entry.rbe_left == old) ((old)->by_inner_entry .rbe_parent)->by_inner_entry.rbe_left = elm; else ((old)-> by_inner_entry.rbe_parent)->by_inner_entry.rbe_right = elm ; do {} while (0); } else (head)->rbh_root = elm; ((old)-> by_inner_entry.rbe_left)->by_inner_entry.rbe_parent = elm; if ((old)->by_inner_entry.rbe_right) ((old)->by_inner_entry .rbe_right)->by_inner_entry.rbe_parent = elm; if (parent) { left = parent; do { do {} while (0); } while ((left = (left) ->by_inner_entry.rbe_parent)); } goto color; } parent = (elm )->by_inner_entry.rbe_parent; color = (elm)->by_inner_entry .rbe_color; if (child) (child)->by_inner_entry.rbe_parent = parent; if (parent) { if ((parent)->by_inner_entry.rbe_left == elm) (parent)->by_inner_entry.rbe_left = child; else ( parent)->by_inner_entry.rbe_right = child; do {} while (0) ; } else (head)->rbh_root = child; color: if (color == 0) hyperlinks_by_inner_tree_RB_REMOVE_COLOR (head, parent, child); return (old); } __attribute__((__unused__ )) static struct hyperlinks_uri * hyperlinks_by_inner_tree_RB_INSERT (struct hyperlinks_by_inner_tree *head, struct hyperlinks_uri *elm) { struct hyperlinks_uri *tmp; struct hyperlinks_uri *parent = ((void *)0); int comp = 0; tmp = (head)->rbh_root; while (tmp) { parent = tmp; comp = (hyperlinks_by_inner_cmp)(elm, parent ); if (comp < 0) tmp = (tmp)->by_inner_entry.rbe_left; else if (comp > 0) tmp = (tmp)->by_inner_entry.rbe_right; else return (tmp); } do { (elm)->by_inner_entry.rbe_parent = parent ; (elm)->by_inner_entry.rbe_left = (elm)->by_inner_entry .rbe_right = ((void *)0); (elm)->by_inner_entry.rbe_color = 1; } while (0); if (parent != ((void *)0)) { if (comp < 0 ) (parent)->by_inner_entry.rbe_left = elm; else (parent)-> by_inner_entry.rbe_right = elm; do {} while (0); } else (head )->rbh_root = elm; hyperlinks_by_inner_tree_RB_INSERT_COLOR (head, elm); return (((void *)0)); } __attribute__((__unused__ )) static struct hyperlinks_uri * hyperlinks_by_inner_tree_RB_FIND (struct hyperlinks_by_inner_tree *head, struct hyperlinks_uri *elm) { struct hyperlinks_uri *tmp = (head)->rbh_root; int comp; while (tmp) { comp = hyperlinks_by_inner_cmp(elm, tmp) ; if (comp < 0) tmp = (tmp)->by_inner_entry.rbe_left; else if (comp > 0) tmp = (tmp)->by_inner_entry.rbe_right; else return (tmp); } return (((void *)0)); } __attribute__((__unused__ )) static struct hyperlinks_uri * hyperlinks_by_inner_tree_RB_NFIND (struct hyperlinks_by_inner_tree *head, struct hyperlinks_uri *elm) { struct hyperlinks_uri *tmp = (head)->rbh_root; struct hyperlinks_uri *res = ((void *)0); int comp; while (tmp) { comp = hyperlinks_by_inner_cmp(elm, tmp); if (comp < 0) { res = tmp; tmp = (tmp)->by_inner_entry.rbe_left; } else if (comp > 0) tmp = (tmp)->by_inner_entry.rbe_right; else return (tmp); } return (res); } __attribute__((__unused__)) static struct hyperlinks_uri * hyperlinks_by_inner_tree_RB_NEXT(struct hyperlinks_uri *elm) { if ((elm)->by_inner_entry.rbe_right) { elm = (elm )->by_inner_entry.rbe_right; while ((elm)->by_inner_entry .rbe_left) elm = (elm)->by_inner_entry.rbe_left; } else { if ((elm)->by_inner_entry.rbe_parent && (elm == ((elm )->by_inner_entry.rbe_parent)->by_inner_entry.rbe_left) ) elm = (elm)->by_inner_entry.rbe_parent; else { while ((elm )->by_inner_entry.rbe_parent && (elm == ((elm)-> by_inner_entry.rbe_parent)->by_inner_entry.rbe_right)) elm = (elm)->by_inner_entry.rbe_parent; elm = (elm)->by_inner_entry .rbe_parent; } } return (elm); } __attribute__((__unused__)) static struct hyperlinks_uri * hyperlinks_by_inner_tree_RB_PREV(struct hyperlinks_uri *elm) { if ((elm)->by_inner_entry.rbe_left ) { elm = (elm)->by_inner_entry.rbe_left; while ((elm)-> by_inner_entry.rbe_right) elm = (elm)->by_inner_entry.rbe_right ; } else { if ((elm)->by_inner_entry.rbe_parent && (elm == ((elm)->by_inner_entry.rbe_parent)->by_inner_entry .rbe_right)) elm = (elm)->by_inner_entry.rbe_parent; else { while ((elm)->by_inner_entry.rbe_parent && (elm == ((elm)->by_inner_entry.rbe_parent)->by_inner_entry.rbe_left )) elm = (elm)->by_inner_entry.rbe_parent; elm = (elm)-> by_inner_entry.rbe_parent; } } return (elm); } __attribute__( (__unused__)) static struct hyperlinks_uri * hyperlinks_by_inner_tree_RB_MINMAX (struct hyperlinks_by_inner_tree *head, int val) { struct hyperlinks_uri *tmp = (head)->rbh_root; struct hyperlinks_uri *parent = ( (void *)0); while (tmp) { parent = tmp; if (val < 0) tmp = (tmp)->by_inner_entry.rbe_left; else tmp = (tmp)->by_inner_entry .rbe_right; } return (parent); }; | |||
| 112 | ||||
| 113 | /* Remove a hyperlink. */ | |||
| 114 | static void | |||
| 115 | hyperlinks_remove(struct hyperlinks_uri *hlu) | |||
| 116 | { | |||
| 117 | struct hyperlinks *hl = hlu->tree; | |||
| 118 | ||||
| 119 | TAILQ_REMOVE(&global_hyperlinks, hlu, list_entry)do { if (((hlu)->list_entry.tqe_next) != ((void *)0)) (hlu )->list_entry.tqe_next->list_entry.tqe_prev = (hlu)-> list_entry.tqe_prev; else (&global_hyperlinks)->tqh_last = (hlu)->list_entry.tqe_prev; *(hlu)->list_entry.tqe_prev = (hlu)->list_entry.tqe_next; ; ; } while (0); | |||
| 120 | global_hyperlinks_count--; | |||
| 121 | ||||
| 122 | RB_REMOVE(hyperlinks_by_inner_tree, &hl->by_inner, hlu)hyperlinks_by_inner_tree_RB_REMOVE(&hl->by_inner, hlu); | |||
| 123 | RB_REMOVE(hyperlinks_by_uri_tree, &hl->by_uri, hlu)hyperlinks_by_uri_tree_RB_REMOVE(&hl->by_uri, hlu); | |||
| 124 | ||||
| 125 | free((void *)hlu->internal_id); | |||
| 126 | free((void *)hlu->external_id); | |||
| 127 | free((void *)hlu->uri); | |||
| 128 | free(hlu); | |||
| 129 | } | |||
| 130 | ||||
| 131 | /* Store a new hyperlink or return if it already exists. */ | |||
| 132 | u_int | |||
| 133 | hyperlinks_put(struct hyperlinks *hl, const char *uri_in, | |||
| 134 | const char *internal_id_in) | |||
| 135 | { | |||
| 136 | struct hyperlinks_uri find, *hlu; | |||
| 137 | char *uri, *internal_id, *external_id; | |||
| 138 | ||||
| 139 | /* | |||
| 140 | * Anonymous URI are stored with an empty internal ID and the tree | |||
| 141 | * comparator will make sure they never match each other (so each | |||
| 142 | * anonymous URI is unique). | |||
| 143 | */ | |||
| 144 | if (internal_id_in == NULL((void *)0)) | |||
| ||||
| 145 | internal_id_in = ""; | |||
| 146 | ||||
| 147 | utf8_stravis(&uri, uri_in, VIS_OCTAL0x01|VIS_CSTYLE0x02); | |||
| 148 | utf8_stravis(&internal_id, internal_id_in, VIS_OCTAL0x01|VIS_CSTYLE0x02); | |||
| 149 | ||||
| 150 | if (*internal_id_in != '\0') { | |||
| 151 | find.uri = uri; | |||
| 152 | find.internal_id = internal_id; | |||
| 153 | ||||
| 154 | hlu = RB_FIND(hyperlinks_by_uri_tree, &hl->by_uri, &find)hyperlinks_by_uri_tree_RB_FIND(&hl->by_uri, &find); | |||
| 155 | if (hlu != NULL((void *)0)) { | |||
| 156 | free (uri); | |||
| 157 | free (internal_id); | |||
| 158 | return (hlu->inner); | |||
| 159 | } | |||
| 160 | } | |||
| 161 | xasprintf(&external_id, "tmux%llX", hyperlinks_next_external_id++); | |||
| 162 | ||||
| 163 | hlu = xcalloc(1, sizeof *hlu); | |||
| 164 | hlu->inner = hl->next_inner++; | |||
| 165 | hlu->internal_id = internal_id; | |||
| 166 | hlu->external_id = external_id; | |||
| 167 | hlu->uri = uri; | |||
| 168 | hlu->tree = hl; | |||
| 169 | RB_INSERT(hyperlinks_by_uri_tree, &hl->by_uri, hlu)hyperlinks_by_uri_tree_RB_INSERT(&hl->by_uri, hlu); | |||
| 170 | RB_INSERT(hyperlinks_by_inner_tree, &hl->by_inner, hlu)hyperlinks_by_inner_tree_RB_INSERT(&hl->by_inner, hlu); | |||
| 171 | ||||
| 172 | TAILQ_INSERT_TAIL(&global_hyperlinks, hlu, list_entry)do { (hlu)->list_entry.tqe_next = ((void *)0); (hlu)->list_entry .tqe_prev = (&global_hyperlinks)->tqh_last; *(&global_hyperlinks )->tqh_last = (hlu); (&global_hyperlinks)->tqh_last = &(hlu)->list_entry.tqe_next; } while (0); | |||
| 173 | if (++global_hyperlinks_count == MAX_HYPERLINKS5000) | |||
| 174 | hyperlinks_remove(TAILQ_FIRST(&global_hyperlinks)((&global_hyperlinks)->tqh_first)); | |||
| 175 | ||||
| 176 | return (hlu->inner); | |||
| 177 | } | |||
| 178 | ||||
| 179 | /* Get hyperlink by inner number. */ | |||
| 180 | int | |||
| 181 | hyperlinks_get(struct hyperlinks *hl, u_int inner, const char **uri_out, | |||
| 182 | const char **internal_id_out, const char **external_id_out) | |||
| 183 | { | |||
| 184 | struct hyperlinks_uri find, *hlu; | |||
| 185 | ||||
| 186 | find.inner = inner; | |||
| 187 | ||||
| 188 | hlu = RB_FIND(hyperlinks_by_inner_tree, &hl->by_inner, &find)hyperlinks_by_inner_tree_RB_FIND(&hl->by_inner, &find ); | |||
| 189 | if (hlu == NULL((void *)0)) | |||
| 190 | return (0); | |||
| 191 | if (internal_id_out != NULL((void *)0)) | |||
| 192 | *internal_id_out = hlu->internal_id; | |||
| 193 | if (external_id_out != NULL((void *)0)) | |||
| 194 | *external_id_out = hlu->external_id; | |||
| 195 | *uri_out = hlu->uri; | |||
| 196 | return (1); | |||
| 197 | } | |||
| 198 | ||||
| 199 | /* Initialize hyperlink set. */ | |||
| 200 | struct hyperlinks * | |||
| 201 | hyperlinks_init(void) | |||
| 202 | { | |||
| 203 | struct hyperlinks *hl; | |||
| 204 | ||||
| 205 | hl = xcalloc(1, sizeof *hl); | |||
| 206 | hl->next_inner = 1; | |||
| 207 | RB_INIT(&hl->by_uri)do { (&hl->by_uri)->rbh_root = ((void *)0); } while (0); | |||
| 208 | RB_INIT(&hl->by_inner)do { (&hl->by_inner)->rbh_root = ((void *)0); } while (0); | |||
| 209 | return (hl); | |||
| 210 | } | |||
| 211 | ||||
| 212 | /* Free all hyperlinks but not the set itself. */ | |||
| 213 | void | |||
| 214 | hyperlinks_reset(struct hyperlinks *hl) | |||
| 215 | { | |||
| 216 | struct hyperlinks_uri *hlu, *hlu1; | |||
| 217 | ||||
| 218 | RB_FOREACH_SAFE(hlu, hyperlinks_by_inner_tree, &hl->by_inner, hlu1)for ((hlu) = hyperlinks_by_inner_tree_RB_MINMAX(&hl->by_inner , -1); ((hlu) != ((void *)0)) && ((hlu1) = hyperlinks_by_inner_tree_RB_NEXT (hlu), 1); (hlu) = (hlu1)) | |||
| 219 | hyperlinks_remove(hlu); | |||
| 220 | } | |||
| 221 | ||||
| 222 | /* Free hyperlink set. */ | |||
| 223 | void | |||
| 224 | hyperlinks_free(struct hyperlinks *hl) | |||
| 225 | { | |||
| 226 | hyperlinks_reset(hl); | |||
| 227 | free(hl); | |||
| 228 | } |