improve memory efficiency

[aaronwu2017]

using pointer instead of array for trie still faces heap memory shortage

ifndef TRIE_H

define TRIE_H

include

include

define ALPHABET_SIZE 26 // Number of characters in the English alphabet

// Forward declaration of the TrieNode struct typedef struct TrieNode TrieNode;

// Definition of the TrieNode struct struct TrieNode { TrieNode *children; // Dynamic array of pointers to child nodes unsigned char numChildren; // Number of actual children TrieNode parent; // Pointer to the parent node // Use bit-field to save heap memory char character; unsigned int isEndOfWord : 1; unsigned int level : 4; // The maximum word length is 15 characters unsigned int bip39Number : 11; // 2048 words in total for bip39Number };

// Function prototypes TrieNode createNode(int level); void addChildNode(TrieNode parent, TrieNode child, char childChar); void insert(TrieNode root, const char key, int number); TrieNode findChildNode(TrieNode parentNode, char targetChar); char getChildChar(TrieNode parentNode, TrieNode child); // Add prototypes for any other functions you might have // For example, if you have a deleteTrie function, declare it here void deleteTrie(TrieNode root);

endif // TRIE_H

[aaronwu2017]

include "Trie.h"

include

// Creates a new Trie node initialized to NULL TrieNode createNode(int level) { TrieNode node = (TrieNode *)malloc(sizeof(TrieNode)); if (node) { node->children = NULL; node->numChildren = 0; node->parent = NULL; node->isEndOfWord = 0; node->level = level; node->bip39Number = 0; // Initialize with 0, indicating no number assigned yet } return node; }

// Dynamically adds a new child node to a parent node void addChildNode(TrieNode parent, TrieNode child, char childChar) { child->character = childChar; // Set the character for the child node parent->children = (TrieNode *)realloc(parent->children, (parent->numChildren + 1) sizeof(TrieNode *)); parent->children[parent->numChildren] = child; parent->numChildren++; }

// Inserts a word into the trie void insert(TrieNode root, const char key, int number) { ESP_LOGE("trie", "insert.");

int length = strlen(key);
TrieNode *pCrawl = root;

for (int i = 0; i < length; i++) {
    char currentChar = key[i];
    TrieNode *child = findChildNode(pCrawl, currentChar);

    if (!child) {
        child = createNode(pCrawl->level + 1);
        child->parent = pCrawl;
        addChildNode(pCrawl, child, currentChar);
    }
    pCrawl = child;
}
  ESP_LOGE("trie", "final marking");
// Mark last node as leaf
pCrawl->isEndOfWord = 1;
pCrawl->bip39Number = number;
  ESP_LOGE("trie", "finish insert");

}

// Finds a child node of a given parent node that corresponds to a character TrieNode findChildNode(TrieNode parentNode, char targetChar) { ESP_LOGE("trie", "findChildNode."); if (!parentNode || parentNode->numChildren == 0) { return NULL; }

for (int i = 0; i < parentNode->numChildren; i++) {
    if (getChildChar(parentNode, parentNode->children[i]) == targetChar) {
        return parentNode->children[i];
    }
}
return NULL;

}

// Placeholder for the getChildChar function or similar logic char getChildChar(TrieNode parentNode, TrieNode child) { return child->character; }

// Recursively deletes a trie from memory void deleteTrie(TrieNode *root) { if (root == NULL) return;

for (int i = 0; i < root->numChildren; i++) {
    deleteTrie(root->children[i]);
}

free(root->children);
free(root);

}

[aaronwu2017]

resolved by https://github.com/aaronwu2017/KeyFlint/commit/e95e925e5ab3f610581f4409136980b158774197