shellTire.c

/*
 * Copyright (c) 2019 TAOS Data, Inc. <jhtao@taosdata.com>
 *
 * This program is free software: you can use, redistribute, and/or modify
 * it under the terms of the GNU Affero General Public License, version 3
 * or later ("AGPL"), as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 */

#define __USE_XOPEN

#include "os.h"
#include "shellTire.h"

// ----------- interface -------------

// create prefix search tree
STire* createTire(char type) {
     STire* tire = taosMemoryMalloc(sizeof(STire));
     memset(tire, 0, sizeof(STire));
     tire->ref    = 1; // init is 1
     tire->type   = type;
     tire->root.d = (STireNode **)taosMemoryCalloc(CHAR_CNT, sizeof(STireNode *));
     return tire;
}

// free tire node
void freeTireNode(STireNode* node) {
    if (node == NULL)
       return ;
  
    // nest free sub node on array d 
    if(node->d) {
        for (int i = 0; i < CHAR_CNT; i++) {
            freeTireNode(node->d[i]);
        }
        taosMemoryFree(node->d);
    }

    // free self
    taosMemoryFree(node);
}

// destroy prefix search tree
void freeTire(STire* tire) {
    // free nodes
    for (int i = 0; i < CHAR_CNT; i++) {
        freeTireNode(tire->root.d[i]);
    }
    taosMemoryFree(tire->root.d);

    // free from list
    StrName * item = tire->head;
    while (item) {
        StrName * next = item->next;
        // free string
        taosMemoryFree(item->name);
        // free node
        taosMemoryFree(item);

        // move next
        item = next;
    }
    tire->head = tire->tail = NULL;

    // free tire
    taosMemoryFree(tire);
}

// insert a new word to list
bool insertToList(STire* tire, char* word) {
    StrName * p = (StrName *)taosMemoryMalloc(sizeof(StrName));
    p->name = strdup(word);
    p->next = NULL;
    
    if(tire->head == NULL) {
        tire->head = p;
        tire->tail = p;
    }else {
        tire->tail->next = p;
        tire->tail = p;
    }

    return true;
}

// insert a new word to tree
bool insertToTree(STire* tire, char* word, int len) {
    int m  = 0;
    STireNode ** nodes = tire->root.d;
    for (int i = 0; i < len; i++) {
        m = word[i] - FIRST_ASCII;
        if (m < 0 || m > CHAR_CNT) {
            return false;
        }

        if (nodes[m] == NULL) {
            // no pointer
            STireNode* p = (STireNode* )taosMemoryMalloc(sizeof(STireNode));
            memset(p, 0, sizeof(STireNode));
            nodes[m] = p;
            if (i == len - 1) {
                // is end
                p->end = true;
                break;
            }            
        }
        
        if (nodes[m]->d == NULL) {
            // malloc d
            nodes[m]->d = (STireNode **)taosMemoryCalloc(CHAR_CNT, sizeof(STireNode *));
        }

        // move to next node
        nodes = nodes[m]->d; 
    }

    // add count
    tire->count += 1;
    return true;
}

// insert a new word 
bool insertWord(STire* tire, char* word) {
    int len = strlen(word);
    if (len >= MAX_WORD_LEN) {
        return false;
    }
    
    switch (tire->type) {
      case TIRE_TREE: 
        return insertToTree(tire, word, len);
      case TIRE_LIST:
        return insertToList(tire, word);
      default:
        break;
    }
    return false;
}

// delete one word from list
bool deleteFromList(STire* tire, char* word) {
    StrName * item = tire->head;
    while (item) {
        if (strcmp(item->name, word) == 0) {
            // found, reset empty to delete
            item->name[0] = 0;
        }
        
        // move next
        item = item->next;
    }
    return true;
}

// delete one word from tree 
bool deleteFromTree(STire* tire, char* word, int len) {
    int m  = 0;
    bool del = false;

    STireNode** nodes = tire->root.d;
    for (int i = 0; i < len; i++) {
        m = word[i] - FIRST_ASCII;
        if (m < 0 || m >= CHAR_CNT) {
            return false;
        }

        if (nodes[m] == NULL) {
            // no found
            return false;
        } else {
            // not null
            if(i == len - 1) {
                // this is last, only set end false , not free node
                nodes[m]->end = false;
                del = true;
                break;
            }
        }

        if(nodes[m]->d == NULL)
          break;
        // move to next node
        nodes = nodes[m]->d;
    }

    // reduce count
    if (del) {
        tire->count -= 1;
    }
    
    return del;
}

// insert a new word 
bool deleteWord(STire* tire, char* word) {
    int len = strlen(word);
    if (len >= MAX_WORD_LEN) {
        return false;
    }
    
    switch (tire->type) {
      case TIRE_TREE: 
        return deleteFromTree(tire, word, len);
      case TIRE_LIST:
        return deleteFromList(tire, word);
      default:
        break;
    }
    return false;
}

void addWordToMatch(SMatch* match, char* word){
    // malloc new
    SMatchNode* node = (SMatchNode* )taosMemoryMalloc(sizeof(SMatchNode));
    memset(node, 0, sizeof(SMatchNode));
    node->word = strdup(word);

    // append to match
    if (match->head == NULL) {
        match->head = match->tail = node;
    } else {
        match->tail->next = node;
        match->tail = node;
    }
    match->count += 1;
}

// enum all words from node
void enumAllWords(STireNode** nodes,  char* prefix, SMatch* match) {
    STireNode * c;
    char word[MAX_WORD_LEN];
    int len = strlen(prefix);
    for (int i = 0; i < CHAR_CNT; i++) {
        c = nodes[i];
        
        if (c == NULL) {
            // chain end node
           continue; 
        } else {
            // combine word string
            memset(word, 0, sizeof(word));
            strcpy(word, prefix);
            word[len] =  FIRST_ASCII + i; // append current char

            // chain middle node
            if (c->end) {
                // have end flag
                addWordToMatch(match, word); 
            }
            // nested call next layer
            if (c->d)
                enumAllWords(c->d, word, match);
        }
    }
}

// match prefix from list
void matchPrefixFromList(STire* tire, char* prefix, SMatch* match) {
    StrName * item = tire->head;
    int len = strlen(prefix);
    while (item) {
        if ( strncmp(item->name, prefix, len) == 0) {
            // prefix matched
            addWordToMatch(match, item->name);
        }

        // move next
        item = item->next;
    }
}

// match prefix words, if match is not NULL , put all item to match and return match
void matchPrefixFromTree(STire* tire, char* prefix, SMatch* match) {
    SMatch* root = match;
    int m  = 0;
    STireNode* c = 0;
    int len = strlen(prefix);
    if (len >= MAX_WORD_LEN) {
        return;
    }

    STireNode** nodes = tire->root.d;
    for (int i = 0; i < len; i++) {
        m = prefix[i] - FIRST_ASCII;
        if (m < 0 || m > CHAR_CNT) {
            return;
        }

        // match
        c = nodes[m];
        if (c == NULL) {
            // arrive end
            break;
        }

        // previous items already matched
        if (i == len - 1) {
            // malloc match if not pass by param match
            if (root == NULL) {                        
                root = (SMatch* )taosMemoryMalloc(sizeof(SMatch));
                memset(root, 0, sizeof(SMatch));
                strcpy(root->pre, prefix);
            }

            // prefix is match to end char
            if (c->d)
                enumAllWords(c->d, prefix, root);
        } else {
            // move to next node continue match
            if(c->d == NULL)
                break;
            nodes = c->d;
        }
    }

    // return 
    return ;
}

SMatch* matchPrefix(STire* tire, char* prefix, SMatch* match) {
    if(match == NULL) {
        match = (SMatch* )taosMemoryMalloc(sizeof(SMatch));
        memset(match, 0, sizeof(SMatch));
    }

    switch (tire->type) {
      case TIRE_TREE: 
        matchPrefixFromTree(tire, prefix, match);
      case TIRE_LIST:
        matchPrefixFromList(tire, prefix, match);
      default:
        break;
    }

    // return if need
    if (match->count == 0) {
        freeMatch(match);
        match = NULL;
    }    

    return match;  
}


// get all items from tires tree
void enumFromList(STire* tire, SMatch* match) {
    StrName * item = tire->head;
    while (item) {
        if (item->name[0] != 0) {
            // not delete
            addWordToMatch(match, item->name);
        }

        // move next
        item = item->next;
    }
}

// get all items from tires tree
void enumFromTree(STire* tire, SMatch* match) {
    char pre[2] ={0, 0};
    STireNode* c;
    
    // enum first layer
    for (int i = 0; i < CHAR_CNT; i++) {
        pre[0] = FIRST_ASCII + i;
        
        // each node
        c = tire->root.d[i];
        if (c == NULL) {
            // this branch no data
            continue;
        }

        // this branch have data
        if(c->end)
          addWordToMatch(match, pre);
        else
          matchPrefix(tire, pre, match);
    }
}

// get all items from tires tree
SMatch* enumAll(STire* tire) {
    SMatch* match = (SMatch* )taosMemoryMalloc(sizeof(SMatch));
    memset(match, 0, sizeof(SMatch));

    switch (tire->type) {
      case TIRE_TREE: 
        enumFromTree(tire, match);
      case TIRE_LIST:
        enumFromList(tire, match);
      default:
        break;
    }

    // return if need
    if (match->count == 0) {
        freeMatch(match);
        match = NULL;
    }    

    return match;
}


// free match result
void freeMatchNode(SMatchNode* node) {
    // first free next
    if (node->next)
      freeMatchNode(node->next);

    // second free self
    if (node->word)
      taosMemoryFree(node->word);
    taosMemoryFree(node);
}

// free match result
void freeMatch(SMatch* match) {
    // first free next
    if (match->head) {
        freeMatchNode(match->head);
    }

    // second free self
    taosMemoryFree(match);
}