自学教程：C++ tree_new函数代码示例

END_TESTSTART_TEST(test_tree_size){  TreeNode *t = tree_new();  t->left = tree_new();  t->right = tree_new();  ck_assert_int_eq(tree_size(t), 3);  tree_free(t);}

/*This may be too slow because the tree could end up very unbalanced if presented in alphabetical order.Probably better to switch to C++ and use STL.Or could hash the strings first.Or use a balancing data structure.*/TREE_T *tree_get(TREE_T *t,char *name){	int x=strcmp(name,t->s);	if (x==0) return t;	if (x<0)	{		if (!t->lt) t->lt=tree_new(name);		return tree_get(t->lt,name);	}	if (!t->gt) t->gt=tree_new(name);	return tree_get(t->gt,name);}

static intuserlist_insertname (session *sess, struct User *newuser){	if (!sess->usertree)	{		sess->usertree = tree_new ((tree_cmp_func *)nick_cmp, sess->server);		sess->usertree_alpha = tree_new ((tree_cmp_func *)nick_cmp_alpha, sess->server);	}	tree_insert (sess->usertree_alpha, newuser);	return tree_insert (sess->usertree, newuser);}

static tree_t get_bool_lit(tree_t t, bool v){   tree_t fdecl = tree_ref(t);   assert(tree_kind(fdecl) == T_FUNC_DECL);   static type_t bool_type = NULL;   if (bool_type == NULL) {      lib_t std = lib_find("std", true, true);      assert(std != NULL);      tree_t standard = lib_get(std, ident_new("STD.STANDARD"));      assert(standard != NULL);      const int ndecls = tree_decls(standard);      for (int i = 0; (i < ndecls) && (bool_type == NULL); i++) {         tree_t d = tree_decl(standard, i);         if (tree_ident(d) == std_bool_i)            bool_type = tree_type(d);      }      assert(bool_type != NULL);   }   tree_t lit = type_enum_literal(bool_type, v ? 1 : 0);   tree_t b = tree_new(T_REF);   tree_set_loc(b, tree_loc(t));   tree_set_ref(b, lit);   tree_set_type(b, bool_type);   tree_set_ident(b, tree_ident(lit));   return b;}

struct strings *strings_new() {    struct strings *strings = malloc(sizeof(*strings));    if (!strings) {        return NULL;    }    strings->hashes = block_new(PAGE_SIZE);    strings->strings = block_new(PAGE_SIZE);    strings->index = block_new(PAGE_SIZE);    if (!strings->hashes || !strings->strings || !strings->index) {        goto error;    }    tree_new(&strings->hash_map);    strings->total = 0;    strings->hash_seed = 5381;    return strings;error:    if (strings->hashes) {        block_free(strings->hashes);    }    if (strings->strings) {        block_free(strings->strings);    }    if (strings->index) {        block_free(strings->index);    }    free(strings);    return NULL;}

bool strings_restore(struct strings *strings,                     const struct strings_snapshot *snapshot) {    struct block *block = strings->index;    if (snapshot->index.count == block->count &&            snapshot->index.offset == block->offsets[block->count - 1]) {        return true;    }    if (!block_restore(strings->strings, &snapshot->strings) ||            !block_restore(strings->hashes, &snapshot->hashes) ||            !block_restore(strings->index, &snapshot->index)) {        return false;    }    strings->total = snapshot->total;    tree_new(&strings->hash_map);    tree_node_t *node, *existing;    for (size_t page = 0; page < block->count; page++) {        for (size_t offset = 0; offset < block->offsets[page];                offset += sizeof(tree_node_t)) {            node = (tree_node_t *)((uintptr_t)block->pages[page] + offset);            existing = find_node(strings, node->hash);            if (existing) {                while (existing->next) {                    existing = existing->next;                }                existing->next = node;            } else {                tree_insert(&strings->hash_map, node);            }        }    }    return true;}

static void search_requirements(struct hash *hash, struct node *n,                                struct tree *d){    struct tree_node *t, *u;    struct tree *providers;    t = tree_first(n->need->root);    while (t) {        providers = tree_new();        get_all_providers(t->n, providers);        u = tree_first(providers->root);        while (u) {            if (!tree_search_node(d, u->n->name))                tree_insert(d, hash_search(hash, u->n->name));            u = tree_next(u);        }        tree_free_all_nodes(providers);        tree_free(providers);        t = tree_next(t);    }    t = tree_first(n->provide->root);    while (t) {        search_requirements(hash, t->n, d);        t = tree_next(t);    }}

int count_providers(struct hash *hash, char *name){    int count;    struct node *n;    struct tree *all;    count = 0;    if ((n = hash_search(hash, name)) == NULL) {        fprintf(stderr,                "bee-dep: count_providers: cannot find /"%s/"/n",                name);        return -1;    }    if (IS_PKG(n)) {        fprintf(stderr,                "bee-dep: count_providers: error: /"%s/" is a package/n",                name);        return -1;    }    all = tree_new();    get_all_providers(n, all);    count = tree_count(all);    tree_free_all_nodes(all);    tree_free(all);    return count;}

int count_removable(struct hash *hash, char *remove){    struct node *n;    struct tree *t;    int c;    if ((n = hash_search(hash, remove)) == NULL) {        fprintf(stderr,                "bee-dep: print_removable: cannot find /"%s/"/n",                remove);        return -1;    }    if (!IS_PKG(n)) {        fprintf(stderr,                "bee-dep: print_removable: /"%s/": no such package/n",                remove);        return -1;    }    t = tree_new();    search_removable(hash, n, t, remove);    c = tree_count(t);    tree_free(t);    return c;}

int print_removable(struct hash *hash, char *remove){    struct node *n;    struct tree *t;    struct tree_node *e;    char **dirs, **files;    int cnt, dir_cnt, file_cnt, i;    if ((n = hash_search(hash, remove)) == NULL) {        fprintf(stderr,                "bee-dep: print_removable: cannot find /"%s/"/n",                remove);        return 1;    }    if (!IS_PKG(n)) {        fprintf(stderr,                "bee-dep: print_removable: /"%s/": no such package/n",                remove);        return 1;    }    t = tree_new();    search_removable(hash, n, t, remove);    cnt = tree_count(t);    if ((dirs = calloc(cnt, sizeof(*dirs))) == NULL        || (files = calloc(cnt, sizeof(*files))) == NULL) {        perror("bee-dep: print_removable: calloc");        return 1;    }    e = tree_first(t->root);    dir_cnt = file_cnt = 0;    while (e) {        if (IS_DIR(e->n))            dirs[dir_cnt++]   = e->n->name;        else            files[file_cnt++] = e->n->name;        e = tree_next(e);    }    sort_dirs(dirs, dir_cnt);    for (i = 0; i < file_cnt; i++)        puts(files[i]);    for (i = 0; i < dir_cnt; i++)        puts(dirs[i]);    free(dirs);    free(files);    tree_free(t);    return 0;}

int print_broken(struct hash *hash, char print){    int c, i;    char h;    struct tree_node *t;    struct tree *dry;    c = 0;    for (i = 0; i < TBLSIZE; i++) {        t = tree_first(hash->tbl[i]->root);        while (t) {            h = 0;            if (IS_PKG(t->n)) {                dry = tree_new();                print_broken_nodes(t->n, &c, &h, print, dry);                tree_free(dry);            }            t = tree_next(t);        }    }    return c;}

/* Show tree in a box, not on a panel */char *tree_box (const char *current_dir){    WTree    *mytree;    Dlg_head *dlg;    char     *val;    WButtonBar *bar;    /* Create the components */    dlg = create_dlg (0, 0, TREE_Y, TREE_X, dialog_colors,		      tree_callback, "[Directory Tree]", NULL, DLG_CENTER | DLG_REVERSE);    mytree = tree_new (0, 2, 2, TREE_Y - 6, TREE_X - 5);    add_widget (dlg, mytree);    bar = buttonbar_new(1);    add_widget (dlg, bar);    bar->widget.x = 0;    bar->widget.y = LINES - 1;        run_dlg (dlg);    if (dlg->ret_value == B_ENTER)	val = g_strdup (tree_selected_name (mytree));    else	val = 0;        destroy_dlg (dlg);    return val;}

char *tree (char *current_dir){    WTree    *mytree;    Dlg_head *dlg;    char     *val;    WButtonBar *bar;    tree_colors [3] = dialog_colors [0];    tree_colors [1] = dialog_colors [1];        /* Create the components */    dlg = create_dlg (0, 0, TREE_Y, TREE_X, tree_colors,		      tree_callback, "[Directory Tree]", "tree", DLG_CENTER);    mytree = tree_new (0, 2, 2, TREE_Y - 6, TREE_X - 5);    add_widget (dlg, mytree);    bar = buttonbar_new(1);    add_widget (dlg, bar);    bar->widget.x = 0;    bar->widget.y = LINES - 1;        run_dlg (dlg);    if (dlg->ret_value == B_ENTER)	val = strdup (mytree->selected_ptr->name);    else	val = 0;        destroy_dlg (dlg);    return val;}

static voidurl_add (char *urltext, int len){	char *data = malloc (len + 1);	if (!data)		return;	memcpy (data, urltext, len);	data[len] = 0;	if (data[len - 1] == '.')	/* chop trailing dot */	{		len--;		data[len] = 0;	}	if (data[len - 1] == ')')	/* chop trailing ) */		data[len - 1] = 0;	if (url_find (data))	{		free (data);		return;	}	if (!url_tree)		url_tree = tree_new ((tree_cmp_func *)strcasecmp, NULL);	tree_insert (url_tree, data);	fe_url_add (data);}

int main(){	BinTree *tree = tree_new();	/*tree_insert(tree, 5);	tree_insert(tree, 7);	tree_insert(tree, 3);	tree_insert(tree, 8);	tree_insert(tree, 1);	tree_insert(tree, 0);	tree_insert(tree, 2);	tree_insert(tree, 6);	tree_insert(tree, 4);	//tree_remove(tree, 6);	printf("%d/n", tree_height(tree));	printf("%d/n", tree_find(tree, 5));	tree_print(tree);	*/	int i;	for (i = 0; i < TAM; i++)		tree_insert(tree, i+1);	//demora aprox 22 segundos a pesquisar todos os elementos da lista 	for (i = 0; i < TAM; i++)		tree_find(tree, i);		tree_destroy(tree);		return 0;}

static ksp_tree_t* args(ksp_parser_t* parser){	ksp_lexer_t* lexer = parser->lexer;	ksp_word_next_tag(lexer, TAG_RBL);	ksp_word_t* w = ksp_word_look(lexer);	if (w->tag == TAG_RBR) {		ksp_word_next_tag(lexer, TAG_RBR);		return K_NULL;	}	ksp_tree_t* left = tree_new3(parser, PARAM, w);	ksp_word_next_tag(lexer, TAG_ID);	w = ksp_word_look(lexer);	while (w->tag != TAG_RBR) {		ksp_word_next_tag(lexer, TAG_COMMA);		w = ksp_word_next_tag(lexer, TAG_ID);		ksp_tree_t* right = tree_new3(parser, PARAM, w);		ksp_tree_t* t = tree_new(parser, PARAMS);		tree_set_left(t, left);		tree_set_right(t, right);		left = t;		w = ksp_word_look(lexer);	}	ksp_word_next_tag(lexer, TAG_RBR);	return left;}

char *tree_box (const char *current_dir){    WTree *mytree;    WDialog *dlg;    Widget *wd;    char *val = NULL;    WButtonBar *bar;    (void) current_dir;    /* Create the components */    dlg = dlg_create (TRUE, 0, 0, LINES - 9, COLS - 20, dialog_colors, tree_callback, NULL,                      "[Directory Tree]", _("Directory tree"), DLG_CENTER);    wd = WIDGET (dlg);    mytree = tree_new (2, 2, wd->lines - 6, wd->cols - 5, FALSE);    add_widget_autopos (dlg, mytree, WPOS_KEEP_ALL, NULL);    add_widget_autopos (dlg, hline_new (wd->lines - 4, 1, -1), WPOS_KEEP_BOTTOM, NULL);    bar = buttonbar_new (TRUE);    add_widget (dlg, bar);    /* restore ButtonBar coordinates after add_widget() */    WIDGET (bar)->x = 0;    WIDGET (bar)->y = LINES - 1;    if (dlg_run (dlg) == B_ENTER)    {        const vfs_path_t *selected_name;        selected_name = tree_selected_name (mytree);        val = g_strdup (vfs_path_as_str (selected_name));    }    dlg_destroy (dlg);    return val;}

tree_t make_ref(tree_t to){   tree_t t = tree_new(T_REF);   tree_set_ident(t, tree_ident(to));   tree_set_ref(t, to);   tree_set_type(t, tree_type(to));   return t;}

tree_ptr tree_new_assign(tree_ptr l, tree_ptr r) {	// TODO: Check l's type.	tree_ptr t = tree_new(eval_assign);	t->child = darray_new();	darray_append(t->child, l);	darray_append(t->child, r);	return t;}

tree_ptr tree_new_ternary(tree_ptr cond, tree_ptr t1, tree_ptr t2) {	tree_ptr t = tree_new(eval_ternary);	t->child = darray_new();	darray_append(t->child, cond);	darray_append(t->child, t1);	darray_append(t->child, t2);	return t;}

tree_ptr tree_new_define(tree_ptr id, tree_ptr parm, tree_ptr body) {	tree_ptr t = tree_new(eval_define);	t->child = darray_new();	darray_append(t->child, id);	darray_append(t->child, parm);	darray_append(t->child, body);	return t;}

tree_ptr tree_new_z(const char* s) {	element_ptr e = (element_ptr)pbc_malloc(sizeof(*e));	element_init(e, M);	element_set_str(e, s, 0);	tree_ptr t = tree_new(eval_elem);	t->elem = e;	return t;}

type_t type_universal_int(void){   static type_t t = NULL;   if (t == NULL) {      tree_t min = tree_new(T_LITERAL);      tree_set_subkind(min, L_INT);      tree_set_ival(min, -INT_MAX);      tree_t max = tree_new(T_LITERAL);      tree_set_subkind(max, L_INT);      tree_set_ival(max, INT_MAX);      t = type_make_universal(T_INTEGER, "universal integer", min, max);   }   return t;}

type_t type_universal_real(void){   static type_t t = NULL;   if (t == NULL) {      tree_t min = tree_new(T_LITERAL);      tree_set_subkind(min, L_REAL);      tree_set_dval(min, -DBL_MAX);      tree_t max = tree_new(T_LITERAL);      tree_set_subkind(max, L_REAL);      tree_set_dval(max, DBL_MAX);      t = type_make_universal(T_REAL, "universal real", min, max);   }   return t;}

tree_t get_real_lit(tree_t t, double r){   tree_t f = tree_new(T_LITERAL);   tree_set_loc(f, tree_loc(t));   tree_set_subkind(f, L_REAL);   tree_set_dval(f, r);   tree_set_type(f, tree_type(t));   return f;}

static ksp_tree_t* block(ksp_parser_t* parser){	ksp_lexer_t* lexer = parser->lexer;	ksp_word_next_tag(parser->lexer, TAG_BBL);	ksp_tree_t* t = tree_new(parser, BLOCK);	ksp_tree_t* left = statements(parser);	tree_set_left(t, left);	ksp_word_next_tag(lexer,TAG_BBR);	return t;}