avl.vtc

Unix下的MUD客户端程序

Ttree ?:= new_assoc();

func make_tree(compare_func) [tree] {
	tree = alloc(2, Ttree);
	tree->cfunc = compare_func;
	tree->root = NULL;
	return tree;
}

func avlrot(n, d) [t] { t = n[d]; t[4] -= n[4]; n[4] = -t[4];
			n[d] = t[5 - d]; t[5 - d] = n; return t; }
func avlrot2(n, d) [t] { t = n[d][5 - d]; n[4] = -(n[4] == t[4]);
			 n[d][4] = (n[4] == -t[4]); n[d][5 - d] = t[d];
			 t[d] = n[d]; n[d] = t[5 - d]; t[5 - d] = n;
			 return t; }

func avlins(f, nptr, new) [n, dir] {
	n = *nptr;
	if (!n) {
		*nptr = new;
		return 1;
	}
	dir = (*f)(*new, *n);
	if (!dir) {
		acopy(n, new, 2);
		return 0;
	} else if (dir < 0 && avlins(f, &n[2], new) && --n[4] == -2) {
		*nptr = n[2][4] == 1 ? avlrot2(n, 2) : avlrot(n, 2);
		return (*nptr)[4];
	} else if (dir > 0 && avlins(f, &n[3], new) && ++n[4] == 2) {
		*nptr = n[3][4] == -1 ? avlrot2(n, 3) : avlrot(n, 3);
		return (*nptr)[4];
	}
}

func insert_tree(t, k, d) {
	avlins(t->cfunc, &t->root, table(k, d, NULL, NULL, 0));
}

func find_tree(tree, key) [node, dir] {
	node = tree->root;
	while (node) {
		dir = (*tree->cfunc)(key, *node);
		if (!dir)
			return node[1];
		else
			node = (dir < 0) ? node[2] : node[3];
	}
	return NULL;
}

func delete_tree(tree, key) [node, dir] {
	node = tree->root;
	while (node) {
		dir = (*tree->cfunc)(key, *node);
		if (!dir) {
		       node[1] = NULL;
		       return 1;
		} else
		       node = dir < 0 ? node[2] : node[3];
	}
}

func traverse_tree(tree, map_func) {
	callv(.inttt, -1, tree->root, argc - 1, argv + 1);
}

func inttt(node, map_func) {
	if (!node)
		return;
	callv(.inttt, -1, node[2], argc - 1, argv + 1);
	if (node[1])
		callv(map_func, 2, node, argc - 2, argv + 2);
	callv(.inttt, -1, node[3], argc - 1, argv + 1);
}

func del_smatches(tree, pattern) {
	dsmfound = 0;
	traverse_tree(tree, .intdsm, tree, pattern);
	if (!dsmfound)
		printf("Could not find %s\n", pattern);
}

func intdsm(name, node, tree, pattern) {
	if (smatch(pattern, name)) {
		delete_tree(tree, name);
		dsmfound = 1;
	}
}