Author: bdonlan
Date: 2005-01-01 00:15:18 -0500 (Sat, 01 Jan 2005)
New Revision: 497
Modified:
trunk/
trunk/clients/havercurs/TODO
trunk/clients/havercurs/cmdline.c
trunk/clients/havercurs/cmdline.h
Log:
[EMAIL PROTECTED]: bdonlan | 2005-01-01T05:15:03.142926Z
Completed command-line trie implementation.
Happy new year!
Property changes on: trunk
___________________________________________________________________
Name: svk:merge
- 1f59643a-e6e5-0310-bc24-f7d4c744f460:/haver/local/trunk:10261
27e50396-46e3-0310-8b22-ae223a1f35ce:/local:212
edfcd8bd-4ce7-0310-a97e-bb1efd40edf3:/local:238
+ 1f59643a-e6e5-0310-bc24-f7d4c744f460:/haver/local/trunk:10263
27e50396-46e3-0310-8b22-ae223a1f35ce:/local:212
edfcd8bd-4ce7-0310-a97e-bb1efd40edf3:/local:238
Modified: trunk/clients/havercurs/TODO
===================================================================
--- trunk/clients/havercurs/TODO 2005-01-01 02:33:30 UTC (rev 496)
+++ trunk/clients/havercurs/TODO 2005-01-01 05:15:18 UTC (rev 497)
@@ -3,13 +3,13 @@
* basic display
* event loop (fd polling, timers)
* Synchronous connection
+* Line-oriented buffered I/O
+* Hash table
Debugging:
-* Line-oriented buffered I/O
+* /-command parser
TODO:
-* Hash table
-* /-command parser
* Haver protocol parser
* Authentication
* Chat
Modified: trunk/clients/havercurs/cmdline.c
===================================================================
--- trunk/clients/havercurs/cmdline.c 2005-01-01 02:33:30 UTC (rev 496)
+++ trunk/clients/havercurs/cmdline.c 2005-01-01 05:15:18 UTC (rev 497)
@@ -35,9 +35,15 @@
struct trie *ptrs[TRIE_CHARS];
cmdline_handler *handler;
void *baton;
+ int children; /* number of commands under here - sum of ptrs[]->children,
+ * plus one if handler is non-null
+ */
+ struct trie *parent;
+ int depth;
+ char c;
} trie;
-static trie *root = NULL;
+static trie root;
/** trie_trans_char
*
@@ -49,7 +55,7 @@
* Return value:
* Index of character, or -1 if not found
*/
-static inline int trie_find_char(char c) {
+static inline char trie_find_char(char c) {
char *p = strchr(trie_chars, c);
if (!p)
return -1;
@@ -75,7 +81,7 @@
int create
)
{
- trie *cur = root;
+ trie *cur = &root;
while (*prefix && cur) {
trie *next;
int idx = trie_find_char(*prefix);
@@ -89,6 +95,9 @@
next = mymalloc(sizeof *next);
next->handler = NULL;
next->baton = NULL;
+ next->parent = cur;
+ next->c = idx;
+ next->depth = cur->depth + 1;
for (i = 0; i < TRIE_CHARS; i++)
next->ptrs[i] = NULL;
cur->ptrs[idx] = next;
@@ -98,18 +107,46 @@
return cur;
}
+/** trie_purge
+ *
+ * Remove and free all children of this node.
+ *
+ * Arguments:
+ * node - the node to act upon
+ */
+static void trie_purge(trie *node) {
+ int i;
+ for (i = 0; i < TRIE_CHARS; i++) {
+ if (node->ptrs[i]) {
+ trie_purge(node->ptrs[i]);
+ free(node->ptrs[i]);
+ node->ptrs[i] = NULL;
+ }
+ }
+ if (node->handler)
+ node->children = 1;
+ else
+ node->children = 0;
+}
+
/** cmdline_init()
*
* Initializes the module. Must be called before any other functions in this
header.
*/
-void cmdline_init(void);
+void cmdline_init(void) {
+ /* NO-OP */
+}
/** cmdline_free()
*
* De-initializes the module. cmdline_init() must be called again after
calling this,
* before any other functions from this header are called
*/
-void cmdline_free(void);
+void cmdline_free(void) {
+ trie_purge(root);
+ root->handler = NULL;
+ root->children = 0;
+}
/** cmdline_register()
*
@@ -127,7 +164,21 @@
const char *command,
cmdline_handler *cb,
void *baton
- );
+ )
+{
+ cmdline_handler *old;
+ trie *node = trie_find_level(command, 1);
+ old = node->handler;
+ node->handler = cb;
+ node->baton = baton;
+ if (!old) {
+ while (node) {
+ node->children++;
+ node = node->parent;
+ }
+ }
+ return old;
+}
/** cmdline_unregister()
*
@@ -139,8 +190,55 @@
* Return value:
* Previous handler or NULL if none
*/
-cmdline_handler *cmdline_unregister(const char *command);
+cmdline_handler *cmdline_unregister(const char *command) {
+ trie *prev = NULL;
+ cmdline_handler *old;
+ trie *targ = trie_lookup(command, 0);
+ if (!targ)
+ return NULL;
+ old = targ->handler;
+ targ->handler = NULL;
+
+ /* Update children counts up the trie. We keep track of the last node,
+ * and when we transition from zero to nonzero, purge the last node and
+ * free it.
+ */
+ while (targ) {
+ targ->children--;
+ if (last && !last->children && targ->children) {
+ trie_purge(last);
+ targ->ptrs[last->c] = NULL;
+ free(last);
+ }
+ last = targ;
+ targ = targ->parent;
+ }
+
+ return old;
+}
+struct lookup_baton {
+ void *baton;
+ cmdline_handler *handler;
+};
+
+/** lookup_cb()
+ *
+ * Callback used by cmdline_lookup() with cmdline_enum()
+ */
+static int lookup_cb(
+ void *baton,
+ const char *command,
+ cmdline_handler *handler,
+ void *h_baton
+ )
+{
+ struct lookup_baton *lb = baton;
+ lb->baton = h_baton;
+ lb->handler = handler;
+ return 0;
+}
+
/** cmdline_lookup()
*
* Obtains the handler for a given command
@@ -152,13 +250,29 @@
* int partial - 1 if partial matching should be attempted
*
* Return value:
- * Handler callback, or NULL if none
+ * Handler callback, or NULL if none or ambiguous
*/
cmdline_handler *cmdline_lookup(
const char *command,
void **baton,
int partial
- );
+ )
+{
+ struct lookup_baton lb;
+ trie *targ = trie_lookup(command, 0);
+ if (targ) {
+ if (baton)
+ *baton = targ->baton;
+ return targ->handler;
+ }
+ if (!partial)
+ return NULL;
+ if (1 != cmdline_enum(command, lookup_cb, &lb))
+ return NULL;
+ if (baton)
+ *baton = lb.baton;
+ return lb.handler;
+}
/** cmdline_process()
*
@@ -166,7 +280,7 @@
*
* Arguments:
* const char *cmdline - full command line to process
- * int particl - 1 if partial matching should be attempted
+ * int partial - 1 if partial matching should be attempted
*
* Return value:
* 2 if command was processed with a partial match
@@ -174,8 +288,80 @@
* 0 if no handler was found
* -1 if multiple partial matches were found; no action will be taken
*/
-int cmdline_process(const char *cmdline);
+int cmdline_process(const char *cmdline, int partial) {
+ char *cmdstr;
+ char *endcmd = cmdline;
+ cmdline_handler *h;
+ void *baton;
+ struct lookup_baton lb;
+ size_t ret;
+ while (*endcmd && strchr(trie_chars, *endcmd))
+ endcmd++;
+ cmdstr = mymalloc(endcmd - cmdline + 1);
+ memcpy(cmdstr, cmdline, endcmd - cmdline);
+ cmdstr[endcmd - cmdline] = '\0';
+
+ h = cmdline_lookup(cmdstr, &baton);
+ if (h) {
+ h(baton, cmdline);
+ return 1;
+ }
+ if (!partial)
+ return 0;
+
+ ret = cmdline_enum(cmdstr, lookup_cb, &lb);
+ if (ret == 0)
+ return 0;
+ if (ret != 1)
+ return -1;
+ lb.handler(lb.baton, cmdline);
+ return 2;
+}
+
+/** enum_recurs()
+ *
+ * Recursively scan the trie node given, returning the count of non-NULL
+ * handlers found. Call cb() on each handler found, as long as *cont is
+ * nonzero. Sets *cont to the return of cb().
+ *
+ * Arguments:
+ * trie *node - node to start from
+ * cmdline_enum_callback *cb - callback to call once a handler is found
+ * void *baton - baton to pass to *cb
+ * int *cont - flag to terminate searching
+ */
+void enum_recurs(
+ trie *node,
+ cmdline_enum_callback *cb,
+ void *baton,
+ int *cont
+ )
+{
+ int i;
+ if (node->handler && *cont) {
+ /* figure out what our name is
+ * XXX: we malloc and free far too often - should use a single buffer
+ */
+ trie *cur = node;
+ char *cmdname = mymalloc(node->depth + 1);
+ cmdname[node->depth] = '\0';
+ while (cur->parent) {
+ cmdname[cur->depth - 1] = trie_chars[cur->c];
+ cur = cur->parent;
+ }
+
+ *cont = cb(baton, cmdname, node->handler, node->baton);
+ free(cmdname);
+ }
+ for (i = 0; i < TRIE_CHARS; i++) {
+ if (!*cont)
+ return;
+ if (node->ptrs[i])
+ enum_recurs(node->ptrs[i], cb, baton, cont);
+ }
+}
+
/** cmdline_enum()
*
* Obtain a complete listing of partial matches for a command prefix
@@ -192,4 +378,12 @@
const char *prefix,
cmdline_enum_callback *cb,
void *baton
- );
+ )
+{
+ trie *node = trie_find_level(prefix, 0);
+ int cont = 1;
+ if (!node)
+ return 0;
+ enum_recurs(node, cb, baton, &cont);
+ return node->children;
+}
Modified: trunk/clients/havercurs/cmdline.h
===================================================================
--- trunk/clients/havercurs/cmdline.h 2005-01-01 02:33:30 UTC (rev 496)
+++ trunk/clients/havercurs/cmdline.h 2005-01-01 05:15:18 UTC (rev 497)
@@ -108,7 +108,7 @@
* int partial - 1 if partial matching should be attempted
*
* Return value:
- * Handler callback, or NULL if none
+ * Handler callback, or NULL if none or ambiguous
*/
cmdline_handler *cmdline_lookup(
const char *command,
