diff --git a/sys/include/lib/kern_trie.h b/sys/include/lib/kern_trie.h new file mode 100644 index 0000000..07e8171 --- /dev/null +++ b/sys/include/lib/kern_trie.h @@ -0,0 +1,51 @@ +/*- + * Copyright (c) 2002-2018 The UbixOS Project. + * All rights reserved. + * + * This was developed by Christopher W. Olsen for the UbixOS Project. + * + * Redistribution and use in source and binary forms, with or without modification, are permitted + * provided that the following conditions are met: + * + * 1) Redistributions of source code must retain the above copyright notice, this list of + * conditions, the following disclaimer and the list of authors. + * 2) Redistributions in binary form must reproduce the above copyright notice, this list of + * conditions, the following disclaimer and the list of authors in the documentation and/or + * other materials provided with the distribution. + * 3) Neither the name of the UbixOS Project nor the names of its contributors may be used to + * endorse or promote products derived from this software without specific prior written + * permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS + * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, + * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef _LIB_KERN_TRIE_H_ +#define _LIB_KERN_TRIE_H_ + +#include + +#define CHAR_SIZE 26 + +struct Trie { + u_int8_t isLeaf; + struct Trie *character[CHAR_SIZE]; + void *e; +}; + + +struct Trie *new_trieNode(); + +void insert_trieNode(struct Trie **, char *, void *); + +struct Trie *search_trieNode(struct Trie *, char *); + +int delete_trieNode(struct Trie **, char *); + +#endif _LIB_LKERN_TRIE_H_ diff --git a/sys/kernel/kern_sysctl.c b/sys/kernel/kern_sysctl.c index 0ab8ae8..eff59a0 100644 --- a/sys/kernel/kern_sysctl.c +++ b/sys/kernel/kern_sysctl.c @@ -36,12 +36,15 @@ #include #include #include +#include static struct sysctl_entry *ctls = 0x0; static struct sysctl_entry *sysctl_find(int *, int); static struct sysctl_entry *sysctl_findMib(char *name, int namelen); +struct Trie *sysctl_headTrie = 0x0; + /* This is a cheat for now */ static void def_ctls() { int name[CTL_MAXNAME], name_len; @@ -119,18 +122,24 @@ } int sysctl_init() { + struct sysctl_entry *tmpCtl = 0x0; + if (ctls != 0x0) { kprintf("sysctl already Initialized\n"); while (1) ; } + /* Initialize Head Trie */ + sysctl_headTrie = (struct Trie *) kmalloc(sizeof(struct Trie)); + ctls = (struct sysctl_entry *) kmalloc(sizeof(struct sysctl_entry)); ctls->prev = 0x0; ctls->id = CTL_UNSPEC; ctls->children = 0x0; sprintf(ctls->name, "unspec"); + insert_trieNode(sysctl_headTrie, &ctls->name, ctls); tmpCtl = (struct sysctl_entry *) kmalloc(sizeof(struct sysctl_entry)); tmpCtl->prev = ctls; @@ -138,6 +147,7 @@ tmpCtl->children = 0x0; sprintf(tmpCtl->name, "kern"); ctls->next = tmpCtl; + insert_trieNode(sysctl_headTrie, &ctls->name, ctls); tmpCtl->next = (struct sysctl_entry *) kmalloc(sizeof(struct sysctl_entry)); tmpCtl->next->prev = tmpCtl; @@ -145,6 +155,7 @@ tmpCtl->id = CTL_VM; tmpCtl->children = 0x0; sprintf(tmpCtl->name, "vm"); + insert_trieNode(sysctl_headTrie, &ctls->name, ctls); tmpCtl->next = (struct sysctl_entry *) kmalloc(sizeof(struct sysctl_entry)); tmpCtl->next->prev = tmpCtl; @@ -152,6 +163,7 @@ tmpCtl->id = CTL_VFS; tmpCtl->children = 0x0; sprintf(tmpCtl->name, "vfs"); + insert_trieNode(sysctl_headTrie, &ctls->name, ctls); tmpCtl->next = (struct sysctl_entry *) kmalloc(sizeof(struct sysctl_entry)); tmpCtl->next->prev = tmpCtl; @@ -159,6 +171,7 @@ tmpCtl->id = CTL_NET; tmpCtl->children = 0x0; sprintf(tmpCtl->name, "net"); + insert_trieNode(sysctl_headTrie, &ctls->name, ctls); tmpCtl->next = (struct sysctl_entry *) kmalloc(sizeof(struct sysctl_entry)); tmpCtl->next->prev = tmpCtl; @@ -166,6 +179,7 @@ tmpCtl->id = CTL_DEBUG; tmpCtl->children = 0x0; sprintf(tmpCtl->name, "debug"); + insert_trieNode(sysctl_headTrie, &ctls->name, ctls); tmpCtl->next = (struct sysctl_entry *) kmalloc(sizeof(struct sysctl_entry)); tmpCtl->next->prev = tmpCtl; @@ -173,6 +187,7 @@ tmpCtl->id = CTL_HW; tmpCtl->children = 0x0; sprintf(tmpCtl->name, "hw"); + insert_trieNode(sysctl_headTrie, &ctls->name, ctls); tmpCtl->next = (struct sysctl_entry *) kmalloc(sizeof(struct sysctl_entry)); tmpCtl->next->prev = tmpCtl; @@ -180,6 +195,7 @@ tmpCtl->id = CTL_MACHDEP; tmpCtl->children = 0x0; sprintf(tmpCtl->name, "machdep"); + insert_trieNode(sysctl_headTrie, &ctls->name, ctls); tmpCtl->next = (struct sysctl_entry *) kmalloc(sizeof(struct sysctl_entry)); tmpCtl->next->prev = tmpCtl; @@ -187,6 +203,7 @@ tmpCtl->id = CTL_USER; tmpCtl->children = 0x0; sprintf(tmpCtl->name, "user"); + insert_trieNode(sysctl_headTrie, &ctls->name, ctls); tmpCtl->next = (struct sysctl_entry *) kmalloc(sizeof(struct sysctl_entry)); tmpCtl->next->prev = tmpCtl; @@ -194,6 +211,7 @@ tmpCtl->id = CTL_P1003_1B; tmpCtl->children = 0x0; sprintf(tmpCtl->name, "p1003_1b"); + insert_trieNode(sysctl_headTrie, &ctls->name, ctls); tmpCtl->next = (struct sysctl_entry *) kmalloc(sizeof(struct sysctl_entry)); tmpCtl->next->prev = tmpCtl; @@ -201,6 +219,7 @@ tmpCtl->id = CTL_UBIX; tmpCtl->children = 0x0; sprintf(tmpCtl->name, "ubix"); + insert_trieNode(sysctl_headTrie, &ctls->name, ctls); def_ctls(); @@ -312,6 +331,10 @@ kprintf("FMIB: %s", mib); + + lCtl = (struct sysctl_entry *) search_trieNode(sysctl_headTrie, mib)->e; + kprintf("FT: %s", lCtl->name); + /* Loop Name Len */ for (i = 0x0; i < namelen; i++) { for (tmpCtl = lCtl; tmpCtl != 0x0; tmpCtl = tmpCtl->next) { @@ -356,6 +379,7 @@ tmpCtl->children->next = 0x0; tmpCtl->children->id = name[namelen - 1]; sprintf(tmpCtl->children->name, str_name); + insert_trieNode(sysctl_headTrie, &tmpCtl->children->name); tmpCtl->children->value = (void *) kmalloc(buf_size); memcpy(tmpCtl->children->value, buf, buf_size); tmpCtl->children->val_len = buf_size; @@ -367,6 +391,7 @@ newCtl->children = 0x0; newCtl->id = name[namelen - 1]; sprintf(newCtl->name, str_name); + insert_trieNode(sysctl_headTrie, &newCtl->name); newCtl->value = (void *) kmalloc(buf_size); memcpy(newCtl->value, buf, buf_size); newCtl->val_len = buf_size; diff --git a/sys/lib/kern_trie.c b/sys/lib/kern_trie.c new file mode 100644 index 0000000..06d4647 --- /dev/null +++ b/sys/lib/kern_trie.c @@ -0,0 +1,149 @@ +/*- + * Copyright (c) 2018 The UbixOS Project. + * All rights reserved. + * + * This was developed by Christopher W. Olsen for the UbixOS Project. + * + * Redistribution and use in source and binary forms, with or without modification, are permitted + * provided that the following conditions are met: + * + * 1) Redistributions of source code must retain the above copyright notice, this list of + * conditions, the following disclaimer and the list of authors. + * 2) Redistributions in binary form must reproduce the above copyright notice, this list of + * conditions, the following disclaimer and the list of authors in the documentation and/or + * other materials provided with the distribution. + * 3) Neither the name of the UbixOS Project nor the names of its contributors may be used to + * endorse or promote products derived from this software without specific prior written + * permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS + * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, + * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include +#include +#include + +struct Trie *new_trieNode() { + + struct Trie *node = (struct Trie *) kmalloc(sizeof(struct Trie)); + + node->isLeaf = 0; + + for (int i = 0; i < CHAR_SIZE; i++) + node->character[i] = NULL; + + return (node); +} + +// Insert Trie +void insert_trieNode(struct Trie **head, char* str, void *e) { + + // start from root node + struct Trie* curr = *head; + + while (*str) { + + // create a new node if path doesn't exists + if (curr->character[*str - 'a'] == NULL) { + curr->character[*str - 'a'] = new_trieNode(); + } + + // go to next node + curr = curr->character[*str - 'a']; + // move to next character + str++; + } + + curr->e = e; + // mark current node as leaf + curr->isLeaf = 1; +} + + +struct Trie *search_trieNode(struct Trie *head, char *str) { + + // return 0 if Trie is empty + if (head == NULL) + return (0); + + struct Trie *curr = head; + + while (*str) { + + // go to next node + curr = curr->character[*str - 'a']; + + // if string is invalid (reached end of path in Trie) + if (curr == NULL) + return (0); + + // move to next character + str++; + } + + // if current node is a leaf and we have reached the + // end of the string, return 1 + return (curr); +} + + + +// Recursive function to delete a string in Trie +int delete_trieNode(struct Trie **curr, char *str) { + + // return if Trie is empty + if (*curr == NULL) + return (0); + + // if we have not reached the end of the string + if (*str) { + // recurse for the node corresponding to next character in + // the string and if it returns 1, delete current node + // (if it is non-leaf) + if (*curr != NULL && (*curr)->character[*str - 'a'] != NULL && deletion(&((*curr)->character[*str - 'a']), str + 1) && (*curr)->isLeaf == 0) { + if (!haveChildren(*curr)) { + free(*curr); + (*curr) = NULL; + return (1); + } + else { + return (0); + } + } + } + + // if we have reached the end of the string + if (*str == '\0' && (*curr)->isLeaf) { + // if current node is a leaf node and don't have any children + if (!haveChildren(*curr)) { + free(*curr); // delete current node + (*curr) = NULL; + return (1); // delete non-leaf parent nodes + } + + // if current node is a leaf node and have children + else { + // mark current node as non-leaf node (DON'T DELETE IT) + (*curr)->isLeaf = 0; + return (0); // don't delete its parent nodes + } + } + + return (0); +} + +// returns 1 if given node has any children +int haveChildren(struct Trie* curr) { + for (int i = 0; i < CHAR_SIZE; i++) + if (curr->character[i]) + return (1); // child found + + return (0); +}