########################### What is this package? ########################### Well, it's (yet another) implemetation of an avl tree in C. Pretty simple, and I'm nearly sure it's not the best thing out there, but it does work! Little extras include a fairly efficient stop-motion traversal function, and the ability to work on any data types (via void*). The reason for its existance despite the presence of better pre-existing libraries? Well, licencing. Most _good_ free libraries are gpl'ed. Now, I actually prefer GPL licencing. However, CircleMUD, and in turn DikuMUD licencing conflicts with GPL licenses. So, you can't use GPL with circle unless you don't want to distribute it. (See the associated comments on licencing below) If you're not ready to use a generic sort of data structure package, then don't use this one. It is actually pretty simple to use, but you need to understand when and how to do certain things, and at least the basic principals of data encapsulation. If you have, in the past month, asked for help on just c-programming issues, this is probably not for you. Wait for an integrated package. There will be one eventually. ########################### What does this do for my game? ########################### Good question. If you had to ask, it does nothing. If you're just reading in order, you probably already realize that it's just going to make a programmers life easier, while adding no functional changes to anything that a player or administrator sees. However, if you think that putting it in will make your mud a haven for coders, you are wrong. Do not integrate this code with your mud unless you are a programmer, a competent one, and know you have a need for it. ########################### What licencing? ########################### I've never placed any licencing restrictions upon anything I've written for circle, barring some external supplements which use the GPL licencing scheme. This is because circle (because of Diku) is already too restrictive. I straight out do not like that license. So, here's mine, in a nutshell: This package is only for use in circlemud. If you use it with anything else, you are breaking the licensing restrictions I place on my work. Don't do it. Why place this restriction? Because 1) there are better avl tree libraries out there, GPL'ed most likely, and 2) I like GPL and struggled about releasing something useful outside of it. I don't want this used in public domain, and I'm offering it as a stopgap solution until circle is rewritten to the point where it's no longer under the diku licence, or the diku team removes their restriction. If you don't like it, you're under no obligation to use my code, feel free to roll your own. ########################### How do I use it ########################### Look at the examples in the provided command 'avltest'. In brief though, all operations start with the creation of a tree, which requires a comparison function: ie. struct avl_tree *avl_tree = avl_create(number_compare) Comparison functions must take two void pointers and return an int that is less than, greater than, or equal to zero, for tree creation. See the number_compare example. Insertions are simple: avl_insert(avl_tree,(void *) yourdata); Deletions are about the same. Realize though, that you have to create a temporary structure of your data type, to delete, just fill in the key: struct my_data_struct temp; struct my_data_struct *retval; my_data_struct.key = 1; retval= avl_delete(avl_tree,temp); if(retval) { free_data_struct_or_operate_it(retval); } THIS IS IMPORTANT: Correct use of insertions and deletions depends upon knowledge of the tree->retval member. If delete is successful, retval will be pointing at the data of the just-deleted node. Insert will use retval as well, if it finds a node with the same key, it will replace the old data with the new; retval will point to the old data. This is useful; say you have an olc process making changes to a copy of a piece of data; instead of line-by-line transfering the changes over (since it's abstracted, you can't just assign addresses for nodes), you just delete the old, insert the new. Or, do it in one step with an insert. Searches work just like you'd expect. They return the data you're looking for with a specified key. there's also an 'avl_count()' function that returns the number of nodes. Needs little explanation. However, that function comes in handy when you're traversing a tree, especially for choosing, say, a random node. Traversals require a bit of work though. Start by initalizing your traversal struct avl_tree_traverse *trav = init_traverse_tree(avl_tree); Then, call avl_traverse each time you want the next node: while(trav) { my_new_data = avl_traverse(&trav); /* do something on data maybe? */ } If you want to skip out before you're done traversing, just make sure to call avl_traverse_free(trav) to free up the memory associated with the traversal information. I'd do it, but I'm lazy. And it's limiting to do it another way. There is also a delete_all function for when you want to entirely clear out a tree, and it takes a pointer to a function that will free your data. For an int, you could probably just pass it free(), but for something more complicated you'll have to make your own. ########################### What is an avl tree? ########################### An avl tree is a binary tree. A binary tree is a fairly simple data structure, and quite a useful one at that. Anyone who thinks linked lists are the end-all-be-all of organization really ought to pay attention here. A binary tree is like a linked list, where the node connects to two other linked lists, instead of just one at a time. ie: Depth O O 1 | / \ O O O 2 | O 3 Linked list Binary tree For convience, we'll say that those two links to other nodes in a binary tree are called left and right, so you can visualize better. Usually, there's some sort of comparison that decides if something goes to the left or right. For example, I could put the higher numbers on the left and the lower on the right. That little tree above could come out like one of the following, depending on data and comparisons: h 50 {room 3001} / \ / \ / \ a z -20 9991 {room 25600} {room 12} (first to last) (lowest to highest) (highest to lowest) Various data types with various comparions in a binary tree The important thing to notice here is the depth. The depth is the number of levels you have to traverse to get to the lowest level. For the first example, the linked list has a depth of 3, and the binary tree has a depth of 2. This depth is important, for example, if we fill out the 3'd depth level of the binary tree (add 4 more nodes, 2 at the bottom of each of the 2'nd depth level) we'll have a total of 7 nodes, and only have a depth of 3. A linked list will have a depth of 7 still. O / \ O O / \ / \ O O O O Binary tree with 7 nodes (depth of 3) This scales pretty well, actually; a tree can hold ((2^n) -1) data items, where n is the depth. A tree with 32 levels can hold 4294967295 data items (at most). Now lets get to why the depth is important. Lets say we have a linked list of 10 circlemud-style room structs. We want to find room 40. To do that we have to go through each one and check the key (the room number). Best case, we have 1 search, worst case 10. Now, lets look at 10 room structs in a binary tree. Each time we are at a node, we look to see if the value we're looking for is less than or greater than the node we're in now. If it's neither, we've found our data. Otherwise, we go to the left or right link (a branch of the tree). You keep doing that till you either get to something where it says to go left or right and there are no lefts or rights (which means to stop and you didn't find it). Simple? Yeah. But look again - each time when you choose to go left or right you cut down the number of nodes you have to search by a half! 10 nodes will fit into 4 levels in a binary tree (2^4 = 16 -1 = 15), so at MOST you'll have 4 searches, at best, 1. An exercise i'll leave to you; look at the differences between searching a list with 4294967295 nodes, and a binary tree with the same number. (Hint, 4294967295 to 32). Sound good? It is. Cept there's one problem. If you just keep inserting, you could end up with all left branches. That means it's basically just as bad as a linked list. Some people are okay with that, but I'm not one of them. What I want is for my binary tree to always have the most shallow depth. In the venacular of discrete mathematics, this is called a balanced binary tree (or AVL tree, named after the guys who designed it). The discusson of it is far too difficult for me to explain using just ascii text, but i did find a decent link; http://www.dgp.toronto.edu/people/JamesStewart/applets/bst/bst-rotation.html This decribes the algorithms required to keep a binary tree balanced. They're a bit hairy, but heck, that's why I wrote the stupid functions. So you don't have to. ########################## Anything else? ########################## Think of this like a preview version. It's only intended for audiences with the ability to have done it themselves. When/If I finally get the time, I'll write up a version which re-orders the data handling structure we have now, basically switching most of the major data structures from linked lists to this. The topology will be something like: World tree contains all zones trees zone trees contain all obj,mob,room trees room trees contain all zone command trees/lists (these are executed in order, no real reason to make them a tree...) The intial version, I think will use linkage via lookup.. ie, instead of storing a pointer to the next room over on a door, you store the room number, and a lookup must be performed. Currently, you use this number to do a direct lookup into the array of rooms (very fast, but not very safe). Bugs, comments, fixes, etc can be submitted to dughi@imaxx.net. I don't need, nor do I desire, credit or listing in any work that uses this code. Don't bother putting me into your credit/start up screen unless you feel deep down that some universal wrong would otherwise be done. If you are in the (Currently, as of 6/5/01) Austin area, you can get me a beer and we'll talk code. I prefer Guinness, but I'll take harp, bass, or shiner in it's place. Wings are optional.