diff options
-rw-r--r-- | Makefile.am | 2 | ||||
-rw-r--r-- | Makefile.in | 8 | ||||
-rw-r--r-- | index.c | 333 | ||||
-rw-r--r-- | index.h | 64 | ||||
-rw-r--r-- | ptrlist.c | 302 | ||||
-rw-r--r-- | ptrlist.h | 69 | ||||
-rw-r--r-- | smenu.c | 863 | ||||
-rw-r--r-- | xmalloc.c | 121 | ||||
-rw-r--r-- | xmalloc.h | 19 |
9 files changed, 924 insertions, 857 deletions
diff --git a/Makefile.am b/Makefile.am index 6f35388..e5304f3 100644 --- a/Makefile.am +++ b/Makefile.am @@ -1,5 +1,5 @@ bin_PROGRAMS = smenu -smenu_SOURCES = smenu.c +smenu_SOURCES = smenu.c ptrlist.c ptrlist.h xmalloc.c xmalloc.h index.c index.h dist_man_MANS = smenu.1 EXTRA_DIST = smenu.spec.in smenu.spec ChangeLog build.sh version \ COPYRIGHT LICENSE.rst README.rst examples build-aux tests diff --git a/Makefile.in b/Makefile.in index 682b74a..2b6d835 100644 --- a/Makefile.in +++ b/Makefile.in @@ -102,7 +102,8 @@ CONFIG_CLEAN_FILES = smenu.spec CONFIG_CLEAN_VPATH_FILES = am__installdirs = "$(DESTDIR)$(bindir)" "$(DESTDIR)$(man1dir)" PROGRAMS = $(bin_PROGRAMS) -am_smenu_OBJECTS = smenu.$(OBJEXT) +am_smenu_OBJECTS = smenu.$(OBJEXT) ptrlist.$(OBJEXT) xmalloc.$(OBJEXT) \ + index.$(OBJEXT) smenu_OBJECTS = $(am_smenu_OBJECTS) smenu_LDADD = $(LDADD) AM_V_P = $(am__v_P_@AM_V@) @@ -305,7 +306,7 @@ target_alias = @target_alias@ top_build_prefix = @top_build_prefix@ top_builddir = @top_builddir@ top_srcdir = @top_srcdir@ -smenu_SOURCES = smenu.c +smenu_SOURCES = smenu.c ptrlist.c ptrlist.h xmalloc.c xmalloc.h index.c index.h dist_man_MANS = smenu.1 EXTRA_DIST = smenu.spec.in smenu.spec ChangeLog build.sh version \ COPYRIGHT LICENSE.rst README.rst examples build-aux tests @@ -419,7 +420,10 @@ mostlyclean-compile: distclean-compile: -rm -f *.tab.c +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/index.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/ptrlist.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/smenu.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/xmalloc.Po@am__quote@ .c.o: @am__fastdepCC_TRUE@ $(AM_V_CC)$(COMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ $< @@ -0,0 +1,333 @@ +/* *************************************************************** */ +/* Ternary Search Tree functions */ +/* Inspired by: https://www.cs.princeton.edu/~rs/strings/tstdemo.c */ +/* *************************************************************** */ + +#include <unistd.h> +#include <wchar.h> +#include <string.h> + +#include "xmalloc.h" +#include "ptrlist.h" +#include "index.h" + +/* List of matching words matching the current search */ +/* """""""""""""""""""""""""""""""""""""""""""""""""" */ +ll_t * tst_search_list; /* Should be initialized by ll_new() before use */ + +/* ====================================== */ +/* Ternary search tree insertion function */ +/* ====================================== */ +tst_node_t * +tst_insert(tst_node_t * p, wchar_t * w, void * data) +{ + if (p == NULL) + { + p = (tst_node_t *)xmalloc(sizeof(tst_node_t)); + p->splitchar = *w; + p->lokid = p->eqkid = p->hikid = NULL; + p->data = NULL; + } + + if (*w < p->splitchar) + p->lokid = tst_insert(p->lokid, w, data); + else if (*w == p->splitchar) + { + if (*w == L'\0') + { + p->data = data; + p->eqkid = NULL; + } + else + p->eqkid = tst_insert(p->eqkid, ++w, data); + } + else + p->hikid = tst_insert(p->hikid, w, data); + + return (p); +} + +#if 0 /* here for coherency but not used. */ +/* ===================================== */ +/* Ternary search tree deletion function */ +/* user data area not cleaned */ +/* ===================================== */ +void +tst_cleanup(tst_node_t * p) +{ + if (p) + { + tst_cleanup(p->lokid); + if (p->splitchar) + tst_cleanup(p->eqkid); + tst_cleanup(p->hikid); + free(p); + } +} +#endif + +/* ========================================================== */ +/* Recursive traversal of a ternary tree. A callback function */ +/* is also called when a complete string is found */ +/* returns 1 if the callback function succeed (returned 1) at */ +/* least once */ +/* the first_call argument is for initializing the static */ +/* variable */ +/* ========================================================== */ +int +tst_traverse(tst_node_t * p, int (*callback)(void *), int first_call) +{ + static int rc; + + if (first_call) + rc = 0; + + if (!p) + return 0; + tst_traverse(p->lokid, callback, 0); + if (p->splitchar != L'\0') + tst_traverse(p->eqkid, callback, 0); + else + rc += (*callback)(p->data); + tst_traverse(p->hikid, callback, 0); + + return !!rc; +} + +/* ======================================================================= */ +/* Traverse the word tst looking for a wchar and build a list of pointers */ +/* containing all the sub-tst * nodes after these node potentially leading */ +/* to words containing the next wchar os the search string */ +/* ======================================================================= */ +int +tst_substring_traverse(tst_node_t * p, int (*callback)(void *), int first_call, + wchar_t w) +{ + static int rc; + + if (first_call) + rc = 0; + + if (!p) + return 0; + + if (p->splitchar == w) + { + ll_node_t * node; + sub_tst_t * sub_tst_data; + + node = tst_search_list->tail; + sub_tst_data = (sub_tst_t *)(node->data); + + if (p->eqkid) + insert_sorted_ptr(&(sub_tst_data->array), &(sub_tst_data->size), + &(sub_tst_data->count), p->eqkid); + + rc = 1; + } + + tst_substring_traverse(p->lokid, callback, 0, w); + if (p->splitchar != L'\0') + tst_substring_traverse(p->eqkid, callback, 0, w); + else if (callback != NULL) + rc += (*callback)(p->data); + tst_substring_traverse(p->hikid, callback, 0, w); + + return !!rc; +} + +/* ======================================================================= */ +/* Traverse the word tst looking for a wchar and build a list of pointers */ +/* containing all the sub-tst * nodes after these node potentially leading */ +/* to words containing the next wchar os the search string */ +/* ======================================================================= */ +int +tst_fuzzy_traverse(tst_node_t * p, int (*callback)(void *), int first_call, + wchar_t w) +{ + static int rc; + wchar_t w1s[2]; + wchar_t w2s[2]; + + w1s[1] = w2s[1] = L'\0'; + + if (first_call) + rc = 0; + + if (!p) + return 0; + + w1s[0] = p->splitchar; + w2s[0] = w; + + if (wcscasecmp(w1s, w2s) == 0) + { + ll_node_t * node; + sub_tst_t * sub_tst_data; + + node = tst_search_list->tail; + sub_tst_data = (sub_tst_t *)(node->data); + + if (p->eqkid != NULL) + insert_sorted_ptr(&(sub_tst_data->array), &(sub_tst_data->size), + &(sub_tst_data->count), p->eqkid); + + rc += 1; + } + + tst_fuzzy_traverse(p->lokid, callback, 0, w); + if (p->splitchar != L'\0') + tst_fuzzy_traverse(p->eqkid, callback, 0, w); + else if (callback != NULL) + rc += (*callback)(p->data); + tst_fuzzy_traverse(p->hikid, callback, 0, w); + + return !!rc; +} + +/* =================================================================== */ +/* Search a complete string in a Ternary tree staring from a root node */ +/* =================================================================== */ +void * +tst_search(tst_node_t * root, wchar_t * w) +{ + tst_node_t * p; + + p = root; + + while (p) + { + if (*w < p->splitchar) + p = p->lokid; + else if (*w == p->splitchar) + { + if (*w++ == L'\0') + return p->data; + p = p->eqkid; + } + else + p = p->hikid; + } + + return NULL; +} + +/* =============================================================== */ +/* Search all strings beginning with the same prefix */ +/* the callback function will be applied to each of theses strings */ +/* returns NULL if no string matched the prefix */ +/* =============================================================== */ +void * +tst_prefix_search(tst_node_t * root, wchar_t * w, int (*callback)(void *)) +{ + tst_node_t * p = root; + size_t len = wcslen(w); + size_t rc; + + while (p) + { + if (*w < p->splitchar) + p = p->lokid; + else if (*w == p->splitchar) + { + len--; + if (*w++ == L'\0') + return p->data; + if (len == 0) + { + rc = tst_traverse(p->eqkid, callback, 1); + return (void *)(long)rc; + } + p = p->eqkid; + } + else + p = p->hikid; + } + + return NULL; +} + +/* ========================================================= */ +/* Insertion of an integer in a already sorted integer array */ +/* without duplications. */ +/* ========================================================= */ +void +insert_sorted_index(long ** array, long * size, long * nb, long value) +{ + long pos = *nb; + long left = 0, right = *nb, middle; + + if (*nb > 0) + { + /* bisection search */ + /* """""""""""""""" */ + while (left < right) + { + middle = (left + right) / 2; + if ((*array)[middle] == value) + return; /* Value already in array */ + + if (value < (*array)[middle]) + right = middle; + else + left = middle + 1; + } + pos = left; + } + + if (*nb == *size) + { + *size += 64; + *array = xrealloc(*array, *size * sizeof(long)); + } + + if (*nb > pos) + memmove((*array) + pos + 1, (*array) + pos, sizeof(value) * (*nb - pos)); + + (*nb)++; + + (*array)[pos] = value; +} + +/* ========================================================= */ +/* Insertion of an pointer in a already sorted pointer array */ +/* without duplications. */ +/* ========================================================= */ +void +insert_sorted_ptr(tst_node_t *** array, unsigned long long * size, + unsigned long long * nb, tst_node_t * ptr) +{ + unsigned long long pos = *nb; + unsigned long long left = 0, right = *nb, middle; + + if (*nb > 0) + { + /* bisection search */ + /* """""""""""""""" */ + while (left < right) + { + middle = (left + right) / 2; + if ((intptr_t)((*array)[middle]) == (intptr_t)ptr) + return; /* Value already in array */ + + if ((intptr_t)ptr < (intptr_t)((*array)[middle])) + right = middle; + else + left = middle + 1; + } + pos = left; + } + + if (*nb == *size) + { + *size += 64; + *array = xrealloc(*array, *size * sizeof(long)); + } + + if (*nb > pos) + memmove((*array) + pos + 1, (*array) + pos, sizeof(ptr) * (*nb - pos)); + + (*nb)++; + + (*array)[pos] = ptr; +} @@ -0,0 +1,64 @@ +#ifndef TST_H +#define TST_H + +/* *************************************** */ +/* Ternary Search Tree specific structures */ +/* *************************************** */ + +typedef struct tst_node_s tst_node_t; +typedef struct sub_tst_s sub_tst_t; + +#if 0 /* here for coherency but not used. */ +void tst_cleanup(tst_node_t * p); +#endif + +tst_node_t * +tst_insert(tst_node_t * p, wchar_t * w, void * data); + +void * +tst_prefix_search(tst_node_t * root, wchar_t * w, int (*callback)(void *)); + +void * +tst_search(tst_node_t * root, wchar_t * w); + +int +tst_traverse(tst_node_t * p, int (*callback)(void *), int first_call); + +int +tst_substring_traverse(tst_node_t * p, int (*callback)(void *), int first_call, + wchar_t w); +int +tst_fuzzy_traverse(tst_node_t * p, int (*callback)(void *), int first_call, + wchar_t w); + +sub_tst_t * +sub_tst_new(void); + +void +insert_sorted_index(long ** array, long * size, long * filled, long value); + +void +insert_sorted_ptr(tst_node_t *** array, unsigned long long * size, + unsigned long long * filled, tst_node_t * ptr); + +/* Ternary node structure */ +/* """""""""""""""""""""" */ +struct tst_node_s +{ + wchar_t splitchar; + + tst_node_t *lokid, *eqkid, *hikid; + void * data; +}; + +/* Structure to contain data and metadata attached to a fuzzy/substring. */ +/* search step. */ +/* """"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" */ +struct sub_tst_s +{ + tst_node_t ** array; + unsigned long long size; + unsigned long long count; +}; + +#endif diff --git a/ptrlist.c b/ptrlist.c new file mode 100644 index 0000000..9531a41 --- /dev/null +++ b/ptrlist.c @@ -0,0 +1,302 @@ +#include "config.h" +#include <stdio.h> +#include <stdlib.h> +#include <limits.h> +#include <string.h> +#include <errno.h> + +#include "xmalloc.h" +#include "ptrlist.h" + +/* ********************* */ +/* Linked List functions */ +/* ********************* */ + +/* ======================== */ +/* Create a new linked list */ +/* ======================== */ +ll_t * +ll_new(void) +{ + ll_t * ret = xmalloc(sizeof(ll_t)); + ll_init(ret); + + return ret; +} + +/* ======================== */ +/* Initialize a linked list */ +/* ======================== */ +void +ll_init(ll_t * list) +{ + list->head = NULL; + list->tail = NULL; + list->len = 0; +} + +/* ==================================================== */ +/* Allocate the space for a new node in the linked list */ +/* ==================================================== */ +ll_node_t * +ll_new_node(void) +{ + ll_node_t * ret = xmalloc(sizeof(ll_node_t)); + + if (ret == NULL) + errno = ENOMEM; + + return ret; +} + +/* ==================================================================== */ +/* Append a new node filled with its data at the end of the linked list */ +/* The user is responsible for the memory management of the data */ +/* ==================================================================== */ +int +ll_append(ll_t * const list, void * const data) +{ + int ret = 1; + ll_node_t * node; + + if (list) + { + node = ll_new_node(); + if (node) + { + node->data = data; + node->next = NULL; + + node->prev = list->tail; + if (list->tail) + list->tail->next = node; + else + list->head = node; + + list->tail = node; + + ++list->len; + ret = 0; + } + } + + return ret; +} + +#if 0 /* here for coherency but not used. */ +/* =================================================================== */ +/* Put a new node filled with its data at the beginning of the linked */ +/* list. The user is responsible for the memory management of the data */ +/* =================================================================== */ +int +ll_prepend(ll_t * const list, void *const data) +{ + int ret = 1; + ll_node_t *node; + + if (list) + { + node = ll_new_node(); + if (node) + { + node->data = data; + node->prev = NULL; + + node->next = list->head; + if (list->head) + list->head->prev = node; + else + list->tail = node; + + list->head = node; + + ++list->len; + ret = 0; + } + } + + return ret; +} + +/* ======================================================= */ +/* Insert a new node before the specified node in the list */ +/* TODO test it */ +/* ======================================================= */ +void +ll_insert_before(ll_t * const list, ll_node_t * node, void *const data) +{ + ll_node_t *new_node; + + if (list) + { + if (node->prev == NULL) + ll_prepend(list, data); + else + { + new_node = ll_new_node(); + if (new_node) + { + new_node->data = data; + new_node->next = node; + new_node->prev = node->prev; + node->prev->next = new_node; + + ++list->len; + } + } + } +} + +/* ====================================================== */ +/* Insert a new node after the specified node in the list */ +/* TODO test it */ +/* ====================================================== */ +void +ll_insert_after(ll_t * const list, ll_node_t * node, void *const data) +{ + ll_node_t *new_node; + + if (list) + { + if (node->next == NULL) + ll_append(list, data); + else + { + new_node = ll_new_node(); + if (new_node) + { + new_node->data = data; + new_node->prev = node; + new_node->next = node->next; + node->next->prev = new_node; + + ++list->len; + } + } + } +} +#endif + +/* ====================================================== */ +/* Partition code for the quicksort function */ +/* Based on code found here: */ +/* http://www.geeksforgeeks.org/quicksort-for-linked-list */ +/* ====================================================== */ +ll_node_t * +ll_partition(ll_node_t * l, ll_node_t * h, int (*comp)(void *, void *), + void (*swap)(void *, void *)) +{ + /* Considers last element as pivot, places the pivot element at its */ + /* correct position in sorted array, and places all smaller (smaller than */ + /* pivot) to left of pivot and all greater elements to right of pivot */ + /* """""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" */ + + /* Set pivot as h element */ + /* """""""""""""""""""""" */ + void * x = h->data; + + ll_node_t * i = l->prev; + ll_node_t * j; + + for (j = l; j != h; j = j->next) + { + if (comp(j->data, x) < 1) + { + i = (i == NULL) ? l : i->next; + + swap(i->data, j->data); + } + } + + i = (i == NULL) ? l : i->next; + swap(i->data, h->data); + + return i; +} + +/* ======================================================= */ +/* A recursive implementation of quicksort for linked list */ +/* ======================================================= */ +void +ll_quicksort(ll_node_t * l, ll_node_t * h, int (*comp)(void *, void *), + void (*swap)(void * a, void *)) +{ + if (h != NULL && l != h && l != h->next) + { + ll_node_t * p = ll_partition(l, h, comp, swap); + ll_quicksort(l, p->prev, comp, swap); + ll_quicksort(p->next, h, comp, swap); + } +} + +/* =========================== */ +/* A linked list sort function */ +/* =========================== */ +void +ll_sort(ll_t * list, int (*comp)(void *, void *), + void (*swap)(void * a, void *)) +{ + /* Call the recursive ll_quicksort function */ + /* """""""""""""""""""""""""""""""""""""""" */ + ll_quicksort(list->head, list->tail, comp, swap); +} + +/* ================================ */ +/* Remove a node from a linked list */ +/* ================================ */ +int +ll_delete(ll_t * const list, ll_node_t * node) +{ + if (list->head == list->tail) + { + if (list->head != NULL) + list->head = list->tail = NULL; + else + return 0; + } + else if (node->prev == NULL) + { + list->head = node->next; + list->head->prev = NULL; + } + else if (node->next == NULL) + { + list->tail = node->prev; + list->tail->next = NULL; + } + else + { + node->next->prev = node->prev; + node->prev->next = node->next; + } + + free(node); + + --list->len; + + return 1; +} + +/* =========================================================================*/ +/* Find a node in the list containing data. Return the node pointer or NULL */ +/* if not found. */ +/* A comparison function must be provided to compare a and b (strcmp like). */ +/* =========================================================================*/ +ll_node_t * +ll_find(ll_t * const list, void * const data, + int (*cmpfunc)(const void * a, const void * b)) +{ + ll_node_t * node; + + if (NULL == (node = list->head)) + return NULL; + + do + { + if (0 == cmpfunc(node->data, data)) + return node; + } while (NULL != (node = node->next)); + + return NULL; +} + diff --git a/ptrlist.h b/ptrlist.h new file mode 100644 index 0000000..d71479f --- /dev/null +++ b/ptrlist.h @@ -0,0 +1,69 @@ +#ifndef LIST_H +#define LIST_H + +typedef struct ll_node_s ll_node_t; +typedef struct ll_s ll_t; + +/* ******************************* */ +/* Linked list specific structures */ +/* ******************************* */ + +/* Linked list node structure */ +/* """""""""""""""""""""""""" */ +struct ll_node_s +{ + void * data; + struct ll_node_s * next; + struct ll_node_s * prev; +}; + +/* Linked List structure */ +/* """"""""""""""""""""" */ +struct ll_s +{ + ll_node_t * head; + ll_node_t * tail; + long len; +}; + +int +ll_append(ll_t * const list, void * const data); + +#if 0 /* here for coherency but not used. */ +int ll_prepend(ll_t * const list, void *const data); + +void +ll_insert_before(ll_t * const list, ll_node_t * node, void *const data); + +void +ll_insert_after(ll_t * const list, ll_node_t * node, void *const data); +#endif + +ll_node_t * +ll_partition(ll_node_t * l, ll_node_t * h, int (*comp)(void *, void *), + void (*swap)(void *, void *)); + +void +ll_quicksort(ll_node_t * l, ll_node_t * h, int (*comp)(void *, void *), + void (*swap)(void * a, void *)); + +void +ll_sort(ll_t * list, int (*comp)(void *, void *), + void (*swap)(void * a, void *)); + +int +ll_delete(ll_t * const list, ll_node_t * node); + +ll_node_t * +ll_find(ll_t * const, void * const, int (*)(const void *, const void *)); + +void +ll_init(ll_t * list); + +ll_node_t * +ll_new_node(void); + +ll_t * +ll_new(void); + +#endif @@ -47,6 +47,10 @@ #include <sys/param.h> #include <wchar.h> +#include "xmalloc.h" +#include "ptrlist.h" +#include "index.h" + /* Used for timers management */ /* """""""""""""""""""""""""" */ #define SECOND 1000000 @@ -69,10 +73,7 @@ typedef struct charsetinfo_s charsetinfo_t; typedef struct langinfo_s langinfo_t; -typedef struct ll_node_s ll_node_t; -typedef struct ll_s ll_t; typedef struct term_s term_t; -typedef struct tst_node_s tst_node_t; typedef struct toggle_s toggle_t; typedef struct win_s win_t; typedef struct word_s word_t; @@ -86,7 +87,6 @@ typedef struct timeout_s timeout_t; typedef struct output_s output_t; typedef struct daccess_s daccess_t; typedef struct search_data_s search_data_t; -typedef struct sub_tst_s sub_tst_t; typedef enum filter_types filters_t; typedef enum daccess_modes da_mode_t; @@ -108,21 +108,6 @@ short_usage(void); static void usage(void); -static void * -xmalloc(size_t size); - -static void * -xcalloc(size_t num, size_t size); - -static void * -xrealloc(void * ptr, size_t size); - -static char * -xstrdup(const char * p); - -static char * -xstrndup(const char * str, size_t len); - static char * concat(const char * s1, ...); @@ -141,46 +126,6 @@ tag_comp(void * a, void * b); static void tag_swap(void * a, void * b); -static int -ll_append(ll_t * const list, void * const data); - -#if 0 /* here for coherency but not used. */ -static int ll_prepend(ll_t * const list, void *const data); - -static void -ll_insert_before(ll_t * const list, ll_node_t * node, void *const data); - -static void -ll_insert_after(ll_t * const list, ll_node_t * node, void *const data); -#endif - -static ll_node_t * -ll_partition(ll_node_t * l, ll_node_t * h, int (*comp)(void *, void *), - void (*swap)(void *, void *)); - -static void -ll_quicksort(ll_node_t * l, ll_node_t * h, int (*comp)(void *, void *), - void (*swap)(void * a, void *)); - -static void -ll_sort(ll_t * list, int (*comp)(void *, void *), - void (*swap)(void * a, void *)); - -static int -ll_delete(ll_t * const list, ll_node_t * node); - -static ll_node_t * -ll_find(ll_t * const, void * const, int (*)(const void *, const void *)); - -static void -ll_init(ll_t * list); - -static ll_node_t * -ll_new_node(void); - -static ll_t * -ll_new(void); - static void ltrim(char * str, const char * trim); @@ -196,9 +141,6 @@ my_strcasecmp(const char * str1, const char * str2); static char * my_strcpy(char * dst, char * src); -static sub_tst_t * -sub_tst_new(void); - static int isprint7(int i); @@ -269,39 +211,9 @@ tst_cb(void * elem); static int tst_cb_cli(void * elem); -#if 0 /* here for coherency but not used. */ -static void tst_cleanup(tst_node_t * p); -#endif - -static tst_node_t * -tst_insert(tst_node_t * p, wchar_t * w, void * data); - -static void * -tst_prefix_search(tst_node_t * root, wchar_t * w, int (*callback)(void *)); - -static void * -tst_search(tst_node_t * root, wchar_t * w); - -static int -tst_traverse(tst_node_t * p, int (*callback)(void *), int first_call); - -static int -tst_substring_traverse(tst_node_t * p, int (*callback)(void *), int first_call, - wchar_t w); -static int -tst_fuzzy_traverse(tst_node_t * p, int (*callback)(void *), int first_call, - wchar_t w); - void mb_strtolower(char * dst, char * src); -void -insert_sorted_index(long ** array, long * size, long * filled, long value); - -void -insert_sorted_ptr(tst_node_t *** array, unsigned long long * size, - unsigned long long * filled, tst_node_t * ptr); - static int ini_load(const char * filename, win_t * win, term_t * term, limits_t * limits, timers_t * timers, misc_t * misc, @@ -777,15 +689,11 @@ struct search_data_s int only_starting; /* Same with the pattern at the beginning */ }; -/* Structure to contain data and metadata attached to a fuzzy/substring. */ -/* search step. */ -/* """"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" */ -struct sub_tst_s -{ - tst_node_t ** array; - unsigned long long size; - unsigned long long count; -}; +/* **************** */ +/* Extern variables */ +/* **************** */ + +extern ll_t * tst_search_list; /* **************** */ /* Global variables */ @@ -834,7 +742,6 @@ int daccess_stack_head; /* Variables used for fuzzy and substring searching */ /* """""""""""""""""""""""""""""""""""""""""""""""" */ -ll_t * tst_search_list = NULL; long * matching_words_a; long matching_words_a_size; long matches_count; @@ -895,42 +802,6 @@ my_ungetc(int c) getc_buffer[next_buffer_pos++] = c; } -/* *************************************** */ -/* Ternary Search Tree specific structures */ -/* *************************************** */ - -/* Ternary node structure */ -/* """""""""""""""""""""" */ -struct tst_node_s -{ - wchar_t splitchar; - - tst_node_t *lokid, *eqkid, *hikid; - void * data; -}; - -/* ******************************* */ -/* Linked list specific structures */ -/* ******************************* */ - -/* Linked list node structure */ -/* """""""""""""""""""""""""" */ -struct ll_node_s -{ - void * data; - struct ll_node_s * next; - struct ll_node_s * prev; -}; - -/* Linked List structure */ -/* """"""""""""""""""""" */ -struct ll_s -{ - ll_node_t * head; - ll_node_t * tail; - long len; -}; - /* ************** */ /* Help functions */ /* ************** */ @@ -1233,108 +1104,6 @@ help(win_t * win, term_t * term, long last_line, toggle_t * toggle) /* employed by anyone for any purpose without restriction. */ /* """"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" */ -/* ================= */ -/* Customized malloc */ -/* ================= */ -static void * -xmalloc(size_t size) -{ - void * allocated; - size_t real_size; - - real_size = (size > 0) ? size : 1; - allocated = malloc(real_size); - if (allocated == NULL) - { - fprintf(stderr, - "Error: Insufficient memory (attempt to malloc %lu bytes)\n", - (unsigned long int)size); - - exit(EXIT_FAILURE); - } - - return allocated; -} - -/* ================= */ -/* Customized calloc */ -/* ================= */ -static void * -xcalloc(size_t n, size_t size) -{ - void * allocated; - - n = (n > 0) ? n : 1; - size = (size > 0) ? size : 1; - allocated = calloc(n, size); - if (allocated == NULL) - { - fprintf(stderr, - "Error: Insufficient memory (attempt to calloc %lu bytes)\n", - (unsigned long int)size); - - exit(EXIT_FAILURE); - } - - return allocated; -} - -/* ================== */ -/* Customized realloc */ -/* ================== */ -static void * -xrealloc(void * p, size_t size) -{ - void * allocated; - - allocated = realloc(p, size); - if (allocated == NULL && size > 0) - { - fprintf(stderr, - "Error: Insufficient memory (attempt to xrealloc %lu bytes)\n", - (unsigned long int)size); - - exit(EXIT_FAILURE); - } - - return allocated; -} - -/* =================================== */ -/* strdup implementation using xmalloc */ -/* =================================== */ -static char * -xstrdup(const char * p) -{ - char * allocated; - - allocated = xmalloc(strlen(p) + 1); - strcpy(allocated, p); - - return allocated; -} - -/* ================================================== */ -/* strndup implementation using xmalloc */ -/* This version guarantees that there is a final '\0' */ -/* ================================================== */ -static char * -xstrndup(const char * str, size_t len) -{ - char * p; - - p = memchr(str, '\0', len); - - if (p) - len = p - str; - - p = xmalloc(len + 1); - memcpy(p, str, len); - p[len] = '\0'; - - return p; -} - /* ********************************** */ /* Attributes string parsing function */ /* ********************************** */ @@ -1939,298 +1708,6 @@ tag_swap(void * a, void * b) ob->order = tmp_order; } -/* ********************* */ -/* Linked List functions */ -/* ********************* */ - -/* ======================== */ -/* Create a new linked list */ -/* ======================== */ -static ll_t * -ll_new(void) -{ - ll_t * ret = xmalloc(sizeof(ll_t)); - ll_init(ret); - - return ret; -} - -/* ======================== */ -/* Initialize a linked list */ -/* ======================== */ -static void -ll_init(ll_t * list) -{ - list->head = NULL; - list->tail = NULL; - list->len = 0; -} - -/* ==================================================== */ -/* Allocate the space for |