From 7ee0a6f2cad69d1a013befc758022e9ae22ceb1e Mon Sep 17 00:00:00 2001 From: Igor Pashev Date: Tue, 13 Dec 2022 10:20:22 +0200 Subject: Make primary a tree-based implementation --- Makefile | 2 - mendeleev-tree.c | 182 ------------------------------------------------------- mendeleev.c | 161 ++++++++++++++++++++++++------------------------ 3 files changed, 80 insertions(+), 265 deletions(-) delete mode 100644 mendeleev-tree.c diff --git a/Makefile b/Makefile index 51fcc76..49a7570 100644 --- a/Makefile +++ b/Makefile @@ -4,7 +4,6 @@ BINARIES := \ mendeleev-f \ mendeleev-hs \ mendeleev-py \ - mendeleev-tree-c \ LISP := \ clisp:mendeleev.lisp \ @@ -53,7 +52,6 @@ prof: \ prof-mendeleev-f.txt \ prof-mendeleev-hs.txt \ prof-mendeleev-py.txt \ - prof-mendeleev-tree-c.txt \ %.gmon: % $(RM) $<-gmon.* diff --git a/mendeleev-tree.c b/mendeleev-tree.c deleted file mode 100644 index 2ab20e1..0000000 --- a/mendeleev-tree.c +++ /dev/null @@ -1,182 +0,0 @@ -#include -#include -#include - -static const char *const ELEMENTS[] = { "?", - "Ac", "Ag", "Al", "Am", "Ar", "As", "At", "Au", "B", "Ba", "Be", "Bh", - "Bi", "Bk", "Br", "C", "Ca", "Cd", "Ce", "Cf", "Cl", "Cm", "Cn", "Co", - "Cr", "Cs", "Cu", "Db", "Ds", "Dy", "Er", "Es", "Eu", "F", "Fe", "Fl", - "Fm", "Fr", "Ga", "Gd", "Ge", "H", "He", "Hf", "Hg", "Ho", "Hs", "I", - "In", "Ir", "K", "Kr", "La", "Li", "Lr", "Lu", "Lv", "Mc", "Md", "Mg", - "Mn", "Mo", "Mt", "N", "Na", "Nb", "Nd", "Ne", "Nh", "Ni", "No", "Np", - "O", "Og", "Os", "P", "Pa", "Pb", "Pd", "Pm", "Po", "Pr", "Pt", "Pu", - "Ra", "Rb", "Re", "Rf", "Rg", "Rh", "Rn", "Ru", "S", "Sb", "Sc", "Se", - "Sg", "Si", "Sm", "Sn", "Sr", "Ta", "Tb", "Tc", "Te", "Th", "Ti", "Tl", - "Tm", "Ts", "U", "V", "W", "Xe", "Y", "Yb", "Zn", "Zr" -}; - -static const size_t NELEMENTS = sizeof (ELEMENTS) / sizeof (const char *) - 1; - -typedef struct element -{ - size_t n; - const char *tail; - struct element *sibs; - struct element *next; -} element_t; - -static void -search (size_t *start, size_t *len, size_t shift, char c) -{ - size_t l, m, u; - c |= ' '; - - u = *start + *len; - l = *start; - while (l < u) - { - m = (l + u) / 2; - if ((ELEMENTS[m][shift] | ' ') < c) - l = m + 1; - else - u = m; - } - - if ((l == *start + *len) || ((ELEMENTS[l][shift] | ' ') != c)) - { - *len = 0; - return; - } - - u = *start + *len; - *start = l; - while (l < u) - { - m = (l + u) / 2; - if (c < (ELEMENTS[m][shift] | ' ')) - u = m; - else - l = m + 1; - } - - *len = u - *start; -} - -static element_t * -divide (const char *tail) -{ - element_t *head = NULL; - element_t *last = NULL; - - size_t start = 1; - size_t len = NELEMENTS; - size_t shift = 0; - - while (tail[shift]) - { - search (&start, &len, shift, tail[shift]); - if (!len) - break; - - shift++; - if (!ELEMENTS[start][shift]) - { - element_t *el = (element_t *) malloc (sizeof (element_t)); - if (!el) - break; - - if (!head) - head = el; - - if (last) - last->sibs = el; - - last = el; - last->n = start; - last->tail = &tail[shift]; - start++; - len--; - } - } - - if (!head) - { - head = (element_t *) malloc (sizeof (element_t)); - if (!head) - return NULL; - head->n = 0; - head->tail = &tail[1]; - last = head; - } - - last->sibs = NULL; - - return head; -} - -static element_t * -explode (const char *word) -{ - element_t *root = divide (word); - for (element_t * el = root; el; el = el->sibs) - el->next = *el->tail ? explode (el->tail) : NULL; - return root; -} - -static void -free_elements (element_t * el) -{ - while (el) - { - if (el->next) - free_elements (el->next); - element_t *sib = el->sibs; - free (el); - el = sib; - } -} - -static void -print_plain (const element_t * current, size_t *formula, size_t n) -{ - for (const element_t * el = current; el; el = el->sibs) - { - formula[n] = el->n; - if (el->next) - print_plain (el->next, formula, n + 1); - else - { - for (size_t i = 0; i <= n; i++) - printf (" %s", ELEMENTS[formula[i]]); - printf ("\n"); - } - } -} - -int -main (int argc, const char *argv[]) -{ - for (int i = 1; i < argc; i++) - { - const char *word = argv[i]; - printf ("%s:\n", word); - - size_t len = strlen (word); - if (!len) - continue; - - element_t *root = explode (word); - if (!root) - return EXIT_FAILURE; - - size_t *formula = (size_t *) malloc (len * sizeof (size_t)); - if (!formula) - return EXIT_FAILURE; - - print_plain (root, formula, 0); - free (formula); - free_elements (root); - } - - return EXIT_SUCCESS; -} diff --git a/mendeleev.c b/mendeleev.c index e48b129..2ab20e1 100644 --- a/mendeleev.c +++ b/mendeleev.c @@ -17,14 +17,13 @@ static const char *const ELEMENTS[] = { "?", static const size_t NELEMENTS = sizeof (ELEMENTS) / sizeof (const char *) - 1; -typedef struct formula +typedef struct element { - const char *tail; size_t n; - size_t *els; - struct formula *next; -} formula_t; - + const char *tail; + struct element *sibs; + struct element *next; +} element_t; static void search (size_t *start, size_t *len, size_t shift, char c) @@ -63,48 +62,11 @@ search (size_t *start, size_t *len, size_t shift, char c) *len = u - *start; } -static formula_t * -new_formula (const char *tail, size_t n, const size_t *els) -{ - formula_t *f = (formula_t *) malloc (sizeof (formula_t)); - if (!f) - return NULL; - - f->els = (size_t *) malloc (sizeof (*f->els) * (n + strlen (tail))); - if (!f->els) - { - free (f); - return NULL; - } - - if (n > 0) - (void) memcpy (f->els, els, n * sizeof (*f->els)); - - f->n = n; - f->tail = tail; - f->next = NULL; - - return f; -} - -static void -free_formula (formula_t * f) +static element_t * +divide (const char *tail) { - while (f) - { - formula_t *next = f->next; - if (f->els) - free (f->els); - free (f); - f = next; - } -} - -static void -advance (formula_t * f) -{ - const char *tail = f->tail; - size_t n = f->n; + element_t *head = NULL; + element_t *last = NULL; size_t start = 1; size_t len = NELEMENTS; @@ -119,64 +81,101 @@ advance (formula_t * f) shift++; if (!ELEMENTS[start][shift]) { - if (n != f->n) - { - formula_t *g = new_formula (tail, n, f->els); - if (!g) - break; - g->next = f->next; - f->next = g; - f = g; - } - - f->els[f->n++] = start; - f->tail = &tail[shift]; + element_t *el = (element_t *) malloc (sizeof (element_t)); + if (!el) + break; + + if (!head) + head = el; + + if (last) + last->sibs = el; + + last = el; + last->n = start; + last->tail = &tail[shift]; start++; len--; } } - if (n == f->n) + if (!head) { - f->els[f->n++] = 0; - f->tail += 1; + head = (element_t *) malloc (sizeof (element_t)); + if (!head) + return NULL; + head->n = 0; + head->tail = &tail[1]; + last = head; } + + last->sibs = NULL; + + return head; } -static formula_t * +static element_t * explode (const char *word) { - formula_t *formula = new_formula (word, 0, NULL); - if (!formula) - return NULL; + element_t *root = divide (word); + for (element_t * el = root; el; el = el->sibs) + el->next = *el->tail ? explode (el->tail) : NULL; + return root; +} - for (formula_t * f = formula; f; f = f->next) - while (*f->tail) - advance (f); +static void +free_elements (element_t * el) +{ + while (el) + { + if (el->next) + free_elements (el->next); + element_t *sib = el->sibs; + free (el); + el = sib; + } +} - return formula; +static void +print_plain (const element_t * current, size_t *formula, size_t n) +{ + for (const element_t * el = current; el; el = el->sibs) + { + formula[n] = el->n; + if (el->next) + print_plain (el->next, formula, n + 1); + else + { + for (size_t i = 0; i <= n; i++) + printf (" %s", ELEMENTS[formula[i]]); + printf ("\n"); + } + } } int main (int argc, const char *argv[]) { - for (int w = 1; w < argc; w++) + for (int i = 1; i < argc; i++) { - const char *word = argv[w]; + const char *word = argv[i]; printf ("%s:\n", word); - formula_t *formula = explode (word); + size_t len = strlen (word); + if (!len) + continue; + + element_t *root = explode (word); + if (!root) + return EXIT_FAILURE; + + size_t *formula = (size_t *) malloc (len * sizeof (size_t)); if (!formula) return EXIT_FAILURE; - for (formula_t * f = formula; f; f = f->next) - { - for (size_t i = 0; i < f->n; i++) - printf (" %s", ELEMENTS[f->els[i]]); - if (f->n) - printf ("\n"); - } - free_formula (formula); + print_plain (root, formula, 0); + free (formula); + free_elements (root); } return EXIT_SUCCESS; -- cgit v1.2.3