Vladimir Marko (Yilard of VisionMUD * beargie.kryha.sk 5000) email: yilard@earthling.net ============================================================================== COMMAND SEARCH TREE for CircleMUD by Yilard of VisionMUD -------------------------------------------------------- This snippet can by used to improve performance of Master command table searching in CircleMUD 3.0. It was developed under bpl14 but it should work on any other patchlevel and with slight modifications it can be used with any other codebase. It was tested under Linux but there shouldn't be any problem also in other environments. This code makes command table searching about 13-times faster ;) than stock sequential search algorhitm. This result was achieved when searching for existing commands. The searching of nonexisting commands is yet MUCH faster. There should be no problems with older code because whole master command table is there and we are just replacing the bit of code responsible for searching. There may be some bugs, altough it has been fully playtested and works fine. NOTE: This makes searching faster but eats a bit of memory because we are making quite complex pointer linked list. It takes about 44kB extra using my very large master command table (about 415 commands). CONDITIONS FOR USAGE OF THIS SNIPPET: There are no special conditions for using this snippet except you're supposed to send me an email (yilard@earthling.net) to let me know for what you have you used it. You could include the name and URL of your mud and your handle or what. You can also inform me about bugs via email. You haven't to credit me (just don't credit yourself for this code), but it would be nice to mention me somewhere, where you usually mention "asorted" contributors, especially if you're developing public codebase. INSTRUCTIONS how to get it work (Circle 3.0): 1. Somewhere at the beginning of interpreter.h add: ------< snip >-------------------------------------------------------------- /* Undefine this to return to the sequential command search algorhitm Suggestion: DO NOT UNDEFINE THIS UNLESS YOU EXPERIENCE PROBLEMS - it will slow down the search process */ #define CMD_TREE_SEARCH ------< snip >-------------------------------------------------------------- 2. in interpreter.c before void command_interpreter(): ------< snip >-------------------------------------------------------------- /* COMMAND SEARCH TREE algorhitm ver 1.0 Faster than light command searching by Yilard of VisionMUD Copyright (C)1999 Electronic Phantasies */ #ifdef CMD_TREE_SEARCH struct letter_info { int cmd_index; int min_level; struct letter_dir *next; }; struct letter_dir { int num; char *letter_string; struct letter_info *letters; }; struct letter_dir *cmd_tree = NULL; #define CMD_LEVEL(cmd) (cmd_info[cmd].minimum_level) void add_cmd(int cmd) { struct letter_dir **tmpdir = &cmd_tree; int i = 0, inx; char buf[2], c; char *ptr; while (i < strlen(CMD_NAME)) { c = tolower(CMD_NAME[i]); if (*tmpdir) { ptr = strchr((*tmpdir)->letter_string, c); if (ptr) { inx = ptr - (*tmpdir)->letter_string; if ((*tmpdir)->letters[inx].min_level > CMD_LEVEL(cmd)) (*tmpdir)->letters[inx].min_level = CMD_LEVEL(cmd); tmpdir = &((*tmpdir)->letters[inx].next); } else { ((*tmpdir)->num)++; ptr = (char *) malloc(sizeof(char) * (strlen((*tmpdir)->letter_string) +2)); strcpy(ptr, (*tmpdir)->letter_string); ptr[strlen(ptr)+1] = '\0'; ptr[strlen(ptr)] = c; free((*tmpdir)->letter_string); (*tmpdir)->letter_string = ptr; (*tmpdir)->letters = realloc((*tmpdir)->letters, (*tmpdir)->num * sizeof(struct letter_info)); (*tmpdir)->letters[(*tmpdir)->num - 1].cmd_index = cmd; (*tmpdir)->letters[(*tmpdir)->num - 1].min_level = CMD_LEVEL(cmd); (*tmpdir)->letters[(*tmpdir)->num - 1].next = NULL; tmpdir = &((*tmpdir)->letters[(*tmpdir)->num - 1].next); } } else { buf[0] = c; buf[1] = '\000'; *tmpdir = (struct letter_dir*)malloc(sizeof(struct letter_dir)); (*tmpdir)->letter_string = strdup(buf); (*tmpdir)->num = 1; (*tmpdir)->letters = (struct letter_info*)malloc(sizeof(struct letter_info)); (*tmpdir)->letters[0].cmd_index = cmd; (*tmpdir)->letters[0].min_level = CMD_LEVEL(cmd); (*tmpdir)->letters[0].next = NULL; tmpdir = &((*tmpdir)->letters[0].next); } i++; } } int build_cmd_tree(void) { int cmd = 1; while (CMD_NAME[0] != '\n') add_cmd(cmd++); return cmd - 1; } int find_command_level(struct letter_dir *dir, int level) { int i, r; for (i = 0; i < dir->num; i++) if (CMD_LEVEL(dir->letters[i].cmd_index) <= level) return dir->letters[i].cmd_index; for (i = 0; i < dir->num; i++) if (dir->letters[i].next) { r = find_command_level(dir->letters[i].next, level); if (r >= 0) return r; } return -1; } int tree_cmd_search(char *s, int level) { register struct letter_dir *tmp = cmd_tree; register int i = 0; int inx = -1; char *ptr; while (i < strlen(s)) { if (tmp) { ptr = strchr(tmp->letter_string, s[i]); if (ptr) { inx = ptr - tmp->letter_string; if (tmp->letters[inx].min_level > level) return -1; if (i + 1 >= strlen(s)) { if (CMD_LEVEL(tmp->letters[inx].cmd_index) <= level) return tmp->letters[inx].cmd_index; if (tmp->letters[inx].next) return find_command_level(tmp->letters[inx].next, level); else return -1; } tmp = tmp->letters[inx].next; } else return -1; } else { return -1; } i++; } return -1; } #endif ------< snip >-------------------------------------------------------------- 3. in function command_interpreter() change: /* otherwise, find the command */ for (length = strlen(arg), cmd = 0; *cmd_info[cmd].command != '\n'; cmd++) if (!strncmp(cmd_info[cmd].command, arg, length)) if (GET_LEVEL(ch) >= cmd_info[cmd].minimum_level) break; if (*cmd_info[cmd].command == '\n') ------< snip >-------------------------------------------------------------- to: ------< snip >-------------------------------------------------------------- /* otherwise, find the command */ #ifdef CMD_TREE_SEARCH cmd = tree_cmd_search(arg, GET_LEVEL(ch)); #else for (length = strlen(arg), cmd = 0; *cmd_info[cmd].command != '\n'; cmd++) if (!strncmp(cmd_info[cmd].command, arg, length)) if (GET_LEVEL(ch) >= cmd_info[cmd].minimum_level) break; #endif if (cmd == -1 || *cmd_info[cmd].command == '\n') send_to_char("Huh?!?\r\n", ch); ------< snip >-------------------------------------------------------------- 4. in db.c add somewhere extern func declaration int build_cmd_tree(void) and in function boot_db() after call to reset_time() add: ------< snip >-------------------------------------------------------------- #ifdef CMD_TREE_SEARCH log("Building command search tree:"); log(" %d commands. Done.", build_cmd_tree()); #endif ------< snip >-------------------------------------------------------------- I hope I haven't forgot anything ;) HAVE A NICE DAY -- Yilard of VisionMUD (yilard@earthling.net)