diff options
Diffstat (limited to 'libtecla/history.c')
| -rw-r--r-- | libtecla/history.c | 2842 |
1 files changed, 2842 insertions, 0 deletions
diff --git a/libtecla/history.c b/libtecla/history.c new file mode 100644 index 0000000..f798ff8 --- /dev/null +++ b/libtecla/history.c @@ -0,0 +1,2842 @@ +/* + * Copyright (c) 2000, 2001, 2002, 2003, 2004, 2012 by Martin C. Shepherd. + * + * All rights reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, and/or sell copies of the Software, and to permit persons + * to whom the Software is furnished to do so, provided that the above + * copyright notice(s) and this permission notice appear in all copies of + * the Software and that both the above copyright notice(s) and this + * permission notice appear in supporting documentation. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT + * OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR + * HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL + * INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING + * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, + * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION + * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + * Except as contained in this notice, the name of a copyright holder + * shall not be used in advertising or otherwise to promote the sale, use + * or other dealings in this Software without prior written authorization + * of the copyright holder. + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <ctype.h> +#include <time.h> +#include <errno.h> + +#include "ioutil.h" +#include "history.h" +#include "freelist.h" +#include "errmsg.h" + +/* + * History lines are split into sub-strings of GLH_SEG_SIZE + * characters. To avoid wasting space in the GlhLineSeg structure, + * this should be a multiple of the size of a pointer. + */ +#define GLH_SEG_SIZE 16 + +/* + * GlhLineSeg structures contain fixed sized segments of a larger + * string. These are linked into lists to record strings, with all but + * the last segment having GLH_SEG_SIZE characters. The last segment + * of a string is terminated within the GLH_SEG_SIZE characters with a + * '\0'. + */ +typedef struct GlhLineSeg GlhLineSeg; +struct GlhLineSeg { + GlhLineSeg *next; /* The next sub-string of the history line */ + char s[GLH_SEG_SIZE]; /* The sub-string. Beware that only the final */ + /* substring of a line, as indicated by 'next' */ + /* being NULL, is '\0' terminated. */ +}; + +/* + * History lines are recorded in a hash table, such that repeated + * lines are stored just once. + * + * Start by defining the size of the hash table. This should be a + * prime number. + */ +#define GLH_HASH_SIZE 113 + +typedef struct GlhHashBucket GlhHashBucket; + +/* + * Each history line will be represented in the hash table by a + * structure of the following type. + */ +typedef struct GlhHashNode GlhHashNode; +struct GlhHashNode { + GlhHashBucket *bucket; /* The parent hash-table bucket of this node */ + GlhHashNode *next; /* The next in the list of nodes within the */ + /* parent hash-table bucket. */ + GlhLineSeg *head; /* The list of sub-strings which make up a line */ + int len; /* The length of the line, excluding any '\0' */ + int used; /* The number of times this string is pointed to by */ + /* the time-ordered list of history lines. */ + int reported; /* A flag that is used when searching to ensure that */ + /* a line isn't reported redundantly. */ +}; + +/* + * How many new GlhHashNode elements should be allocated at a time? + */ +#define GLH_HASH_INCR 50 + +static int _glh_is_line(GlhHashNode *hash, const char *line, size_t n); +static int _glh_line_matches_prefix(GlhHashNode *line, GlhHashNode *prefix); +static void _glh_return_line(GlhHashNode *hash, char *line, size_t dim); + +/* + * All history lines which hash to a given bucket in the hash table, are + * recorded in a structure of the following type. + */ +struct GlhHashBucket { + GlhHashNode *lines; /* The list of history lines which fall in this bucket */ +}; + +static GlhHashBucket *glh_find_bucket(GlHistory *glh, const char *line, + size_t n); +static GlhHashNode *glh_find_hash_node(GlhHashBucket *bucket, const char *line, + size_t n); + +typedef struct { + FreeList *node_mem; /* A free-list of GlhHashNode structures */ + GlhHashBucket bucket[GLH_HASH_SIZE]; /* The buckets of the hash table */ +} GlhLineHash; + +/* + * GlhLineNode's are used to record history lines in time order. + */ +typedef struct GlhLineNode GlhLineNode; +struct GlhLineNode { + long id; /* The unique identifier of this history line */ + time_t timestamp; /* The time at which the line was archived */ + unsigned group; /* The identifier of the history group to which the */ + /* the line belongs. */ + GlhLineNode *next; /* The next youngest line in the list */ + GlhLineNode *prev; /* The next oldest line in the list */ + GlhHashNode *line; /* The hash-table entry of the history line */ +}; + +/* + * The number of GlhLineNode elements per freelist block. + */ +#define GLH_LINE_INCR 100 + +/* + * Encapsulate the time-ordered list of historical lines. + */ +typedef struct { + FreeList *node_mem; /* A freelist of GlhLineNode objects */ + GlhLineNode *head; /* The oldest line in the list */ + GlhLineNode *tail; /* The newest line in the list */ +} GlhLineList; + +/* + * The _glh_lookup_history() returns copies of history lines in a + * dynamically allocated array. This array is initially allocated + * GLH_LOOKUP_SIZE bytes. If subsequently this size turns out to be + * too small, realloc() is used to increase its size to the required + * size plus GLH_LOOKUP_MARGIN. The idea of the later parameter is to + * reduce the number of realloc() operations needed. + */ +#define GLH_LBUF_SIZE 300 +#define GLH_LBUF_MARGIN 100 + +/* + * Encapsulate all of the resources needed to store historical input lines. + */ +struct GlHistory { + ErrMsg *err; /* The error-reporting buffer */ + GlhLineSeg *buffer; /* An array of sub-line nodes to be partitioned */ + /* into lists of sub-strings recording input lines. */ + int nbuff; /* The allocated dimension of buffer[] */ + GlhLineSeg *unused; /* The list of free nodes in buffer[] */ + GlhLineList list; /* A time ordered list of history lines */ + GlhLineNode *recall; /* The last line recalled, or NULL if no recall */ + /* session is currently active. */ + GlhLineNode *id_node;/* The node at which the last ID search terminated */ + GlhLineHash hash; /* A hash-table of reference-counted history lines */ + GlhHashNode *prefix; /* A pointer to a line containing the prefix that */ + /* is being searched for. Note that if prefix==NULL */ + /* and prefix_len>0, this means that no line in */ + /* the buffer starts with the requested prefix. */ + int prefix_len; /* The length of the prefix being searched for. */ + char *lbuf; /* The array in which _glh_lookup_history() returns */ + /* history lines */ + int lbuf_dim; /* The allocated size of lbuf[] */ + int nbusy; /* The number of line segments in buffer[] that are */ + /* currently being used to record sub-lines */ + int nfree; /* The number of line segments in buffer that are */ + /* not currently being used to record sub-lines */ + unsigned long seq; /* The next ID to assign to a line node */ + unsigned group; /* The identifier of the current history group */ + int nline; /* The number of lines currently in the history list */ + int max_lines; /* Either -1 or a ceiling on the number of lines */ + int enable; /* If false, ignore history additions and lookups */ +}; + +#ifndef WITHOUT_FILE_SYSTEM +static int _glh_cant_load_history(GlHistory *glh, const char *filename, + int lineno, const char *message, FILE *fp); +static int _glh_cant_save_history(GlHistory *glh, const char *message, + const char *filename, FILE *fp); +static int _glh_write_timestamp(FILE *fp, time_t timestamp); +static int _glh_decode_timestamp(char *string, char **endp, time_t *timestamp); +#endif +static void _glh_discard_line(GlHistory *glh, GlhLineNode *node); +static GlhLineNode *_glh_find_id(GlHistory *glh, GlhLineID id); +static GlhHashNode *_glh_acquire_copy(GlHistory *glh, const char *line, + size_t n); +static GlhHashNode *_glh_discard_copy(GlHistory *glh, GlhHashNode *hnode); +static int _glh_prepare_for_recall(GlHistory *glh, char *line); + +/* + * The following structure and functions are used to iterate through + * the characters of a segmented history line. + */ +typedef struct { + GlhLineSeg *seg; /* The line segment that the next character will */ + /* be returned from. */ + int posn; /* The index in the above line segment, containing */ + /* the next unread character. */ + char c; /* The current character in the input line */ +} GlhLineStream; +static void glh_init_stream(GlhLineStream *str, GlhHashNode *line); +static void glh_step_stream(GlhLineStream *str); + +/* + * See if search prefix contains any globbing characters. + */ +static int glh_contains_glob(GlhHashNode *prefix); +/* + * Match a line against a search pattern. + */ +static int glh_line_matches_glob(GlhLineStream *lstr, GlhLineStream *pstr); +static int glh_matches_range(char c, GlhLineStream *pstr); + +/*....................................................................... + * Create a line history maintenance object. + * + * Input: + * buflen size_t The number of bytes to allocate to the + * buffer that is used to record all of the + * most recent lines of user input that will fit. + * If buflen==0, no buffer will be allocated. + * Output: + * return GlHistory * The new object, or NULL on error. + */ +GlHistory *_new_GlHistory(size_t buflen) +{ + GlHistory *glh; /* The object to be returned */ + int i; +/* + * Allocate the container. + */ + glh = (GlHistory *) malloc(sizeof(GlHistory)); + if(!glh) { + errno = ENOMEM; + return NULL; + }; +/* + * Before attempting any operation that might fail, initialize the + * container at least up to the point at which it can safely be passed + * to _del_GlHistory(). + */ + glh->err = NULL; + glh->buffer = NULL; + glh->nbuff = (buflen+GLH_SEG_SIZE-1) / GLH_SEG_SIZE; + glh->unused = NULL; + glh->list.node_mem = NULL; + glh->list.head = glh->list.tail = NULL; + glh->recall = NULL; + glh->id_node = NULL; + glh->hash.node_mem = NULL; + for(i=0; i<GLH_HASH_SIZE; i++) + glh->hash.bucket[i].lines = NULL; + glh->prefix = NULL; + glh->lbuf = NULL; + glh->lbuf_dim = 0; + glh->nbusy = 0; + glh->nfree = glh->nbuff; + glh->seq = 0; + glh->group = 0; + glh->nline = 0; + glh->max_lines = -1; + glh->enable = 1; +/* + * Allocate a place to record error messages. + */ + glh->err = _new_ErrMsg(); + if(!glh->err) + return _del_GlHistory(glh); +/* + * Allocate the buffer, if required. + */ + if(glh->nbuff > 0) { + glh->nbuff = glh->nfree; + glh->buffer = (GlhLineSeg *) malloc(sizeof(GlhLineSeg) * glh->nbuff); + if(!glh->buffer) { + errno = ENOMEM; + return _del_GlHistory(glh); + }; +/* + * All nodes of the buffer are currently unused, so link them all into + * a list and make glh->unused point to the head of this list. + */ + glh->unused = glh->buffer; + for(i=0; i<glh->nbuff-1; i++) { + GlhLineSeg *seg = glh->unused + i; + seg->next = seg + 1; + }; + glh->unused[i].next = NULL; + }; +/* + * Allocate the GlhLineNode freelist. + */ + glh->list.node_mem = _new_FreeList(sizeof(GlhLineNode), GLH_LINE_INCR); + if(!glh->list.node_mem) + return _del_GlHistory(glh); +/* + * Allocate the GlhHashNode freelist. + */ + glh->hash.node_mem = _new_FreeList(sizeof(GlhLineNode), GLH_HASH_INCR); + if(!glh->hash.node_mem) + return _del_GlHistory(glh); +/* + * Allocate the array that _glh_lookup_history() uses to return a + * copy of a given history line. This will be resized when necessary. + */ + glh->lbuf_dim = GLH_LBUF_SIZE; + glh->lbuf = (char *) malloc(glh->lbuf_dim); + if(!glh->lbuf) { + errno = ENOMEM; + return _del_GlHistory(glh); + }; + return glh; +} + +/*....................................................................... + * Delete a GlHistory object. + * + * Input: + * glh GlHistory * The object to be deleted. + * Output: + * return GlHistory * The deleted object (always NULL). + */ +GlHistory *_del_GlHistory(GlHistory *glh) +{ + if(glh) { +/* + * Delete the error-message buffer. + */ + glh->err = _del_ErrMsg(glh->err); +/* + * Delete the buffer. + */ + if(glh->buffer) { + free(glh->buffer); + glh->buffer = NULL; + glh->unused = NULL; + }; +/* + * Delete the freelist of GlhLineNode's. + */ + glh->list.node_mem = _del_FreeList(glh->list.node_mem, 1); +/* + * The contents of the list were deleted by deleting the freelist. + */ + glh->list.head = NULL; + glh->list.tail = NULL; +/* + * Delete the freelist of GlhHashNode's. + */ + glh->hash.node_mem = _del_FreeList(glh->hash.node_mem, 1); +/* + * Delete the lookup buffer. + */ + if(glh->lbuf) + free(glh->lbuf); +/* + * Delete the container. + */ + free(glh); + }; + return NULL; +} + +/*....................................................................... + * Append a new line to the history list, deleting old lines to make + * room, if needed. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * line char * The line to be archived. + * force int Unless this flag is non-zero, empty lines aren't + * archived. This flag requests that the line be + * archived regardless. + * Output: + * return int 0 - OK. + * 1 - Error. + */ +int _glh_add_history(GlHistory *glh, const char *line, int force) +{ + int slen; /* The length of the line to be recorded (minus the '\0') */ + int empty; /* True if the string is empty */ + const char *nlptr; /* A pointer to a newline character in line[] */ + GlhHashNode *hnode; /* The hash-table node of the line */ + GlhLineNode *lnode; /* A node in the time-ordered list of lines */ + int i; +/* + * Check the arguments. + */ + if(!glh || !line) { + errno = EINVAL; + return 1; + }; +/* + * Is history enabled? + */ + if(!glh->enable || !glh->buffer || glh->max_lines == 0) + return 0; +/* + * Cancel any ongoing search. + */ + if(_glh_cancel_search(glh)) + return 1; +/* + * How long is the string to be recorded, being careful not to include + * any terminating '\n' character. + */ + nlptr = strchr(line, '\n'); + if(nlptr) + slen = (nlptr - line); + else + slen = strlen(line); +/* + * Is the line empty? + */ + empty = 1; + for(i=0; i<slen && empty; i++) + empty = isspace((int)(unsigned char) line[i]); +/* + * If the line is empty, don't add it to the buffer unless explicitly + * told to. + */ + if(empty && !force) + return 0; +/* + * Has an upper limit to the number of lines in the history list been + * specified? + */ + if(glh->max_lines >= 0) { +/* + * If necessary, remove old lines until there is room to add one new + * line without exceeding the specified line limit. + */ + while(glh->nline > 0 && glh->nline >= glh->max_lines) + _glh_discard_line(glh, glh->list.head); +/* + * We can't archive the line if the maximum number of lines allowed is + * zero. + */ + if(glh->max_lines == 0) + return 0; + }; +/* + * Unless already stored, store a copy of the line in the history buffer, + * then return a reference-counted hash-node pointer to this copy. + */ + hnode = _glh_acquire_copy(glh, line, slen); + if(!hnode) { + _err_record_msg(glh->err, "No room to store history line", END_ERR_MSG); + errno = ENOMEM; + return 1; + }; +/* + * Allocate a new node in the time-ordered list of lines. + */ + lnode = (GlhLineNode *) _new_FreeListNode(glh->list.node_mem); +/* + * If a new line-node couldn't be allocated, discard our copy of the + * stored line before reporting the error. + */ + if(!lnode) { + hnode = _glh_discard_copy(glh, hnode); + _err_record_msg(glh->err, "No room to store history line", END_ERR_MSG); + errno = ENOMEM; + return 1; + }; +/* + * Record a pointer to the hash-table record of the line in the new + * list node. + */ + lnode->id = glh->seq++; + lnode->timestamp = time(NULL); + lnode->group = glh->group; + lnode->line = hnode; +/* + * Append the new node to the end of the time-ordered list. + */ + if(glh->list.head) + glh->list.tail->next = lnode; + else + glh->list.head = lnode; + lnode->next = NULL; + lnode->prev = glh->list.tail; + glh->list.tail = lnode; +/* + * Record the addition of a line to the list. + */ + glh->nline++; + return 0; +} + +/*....................................................................... + * Recall the next oldest line that has the search prefix last recorded + * by _glh_search_prefix(). + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * line char * The input line buffer. On input this should contain + * the current input line, and on output, if anything + * was found, its contents will have been replaced + * with the matching line. + * dim size_t The allocated dimension of the line buffer. + * Output: + * return char * A pointer to line[0], or NULL if not found. + */ +char *_glh_find_backwards(GlHistory *glh, char *line, size_t dim) +{ + GlhLineNode *node; /* The line location node being checked */ + GlhHashNode *old_line; /* The previous recalled line */ +/* + * Check the arguments. + */ + if(!glh || !line) { + if(glh) + _err_record_msg(glh->err, "NULL argument(s)", END_ERR_MSG); + errno = EINVAL; + return NULL; + }; +/* + * Is history enabled? + */ + if(!glh->enable || !glh->buffer || glh->max_lines == 0) + return NULL; +/* + * Check the line dimensions. + */ + if(dim < strlen(line) + 1) { + _err_record_msg(glh->err, "'dim' argument inconsistent with strlen(line)", + END_ERR_MSG); + errno = EINVAL; + return NULL; + }; +/* + * Preserve the input line if needed. + */ + if(_glh_prepare_for_recall(glh, line)) + return NULL; +/* + * From where should we start the search? + */ + if(glh->recall) { + node = glh->recall->prev; + old_line = glh->recall->line; + } else { + node = glh->list.tail; + old_line = NULL; + }; +/* + * Search backwards through the list for the first match with the + * prefix string that differs from the last line that was recalled. + */ + while(node && (node->group != glh->group || node->line == old_line || + !_glh_line_matches_prefix(node->line, glh->prefix))) + node = node->prev; +/* + * Was a matching line found? + */ + if(node) { +/* + * Recall the found node as the starting point for subsequent + * searches. + */ + glh->recall = node; +/* + * Copy the matching line into the provided line buffer. + */ + _glh_return_line(node->line, line, dim); +/* + * Return it. + */ + return line; + }; +/* + * No match was found. + */ + return NULL; +} + +/*....................................................................... + * Recall the next newest line that has the search prefix last recorded + * by _glh_search_prefix(). + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * line char * The input line buffer. On input this should contain + * the current input line, and on output, if anything + * was found, its contents will have been replaced + * with the matching line. + * dim size_t The allocated dimensions of the line buffer. + * Output: + * return char * The line requested, or NULL if no matching line + * was found. + */ +char *_glh_find_forwards(GlHistory *glh, char *line, size_t dim) +{ + GlhLineNode *node; /* The line location node being checked */ + GlhHashNode *old_line; /* The previous recalled line */ +/* + * Check the arguments. + */ + if(!glh || !line) { + if(glh) + _err_record_msg(glh->err, "NULL argument(s)", END_ERR_MSG); + errno = EINVAL; + return NULL; + }; +/* + * Is history enabled? + */ + if(!glh->enable || !glh->buffer || glh->max_lines == 0) + return NULL; +/* + * Check the line dimensions. + */ + if(dim < strlen(line) + 1) { + _err_record_msg(glh->err, "'dim' argument inconsistent with strlen(line)", + END_ERR_MSG); + errno = EINVAL; + return NULL; + }; +/* + * From where should we start the search? + */ + if(glh->recall) { + node = glh->recall->next; + old_line = glh->recall->line; + } else { + return NULL; + }; +/* + * Search forwards through the list for the first match with the + * prefix string. + */ + while(node && (node->group != glh->group || node->line == old_line || + !_glh_line_matches_prefix(node->line, glh->prefix))) + node = node->next; +/* + * Was a matching line found? + */ + if(node) { +/* + * Copy the matching line into the provided line buffer. + */ + _glh_return_line(node->line, line, dim); +/* + * Record the starting point of the next search. + */ + glh->recall = node; +/* + * If we just returned the line that was being entered when the search + * session first started, cancel the search. + */ + if(node == glh->list.tail) + _glh_cancel_search(glh); +/* + * Return the matching line to the user. + */ + return line; + }; +/* + * No match was found. + */ + return NULL; +} + +/*....................................................................... + * If a search is in progress, cancel it. + * + * This involves discarding the line that was temporarily saved by + * _glh_find_backwards() when the search was originally started, + * and reseting the search iteration pointer to NULL. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * Output: + * return int 0 - OK. + * 1 - Error. + */ +int _glh_cancel_search(GlHistory *glh) +{ +/* + * Check the arguments. + */ + if(!glh) { + errno = EINVAL; + return 1; + }; +/* + * If there wasn't a search in progress, do nothing. + */ + if(!glh->recall) + return 0; +/* + * Reset the search pointers. Note that it is essential to set + * glh->recall to NULL before calling _glh_discard_line(), to avoid an + * infinite recursion. + */ + glh->recall = NULL; +/* + * Delete the node of the preserved line. + */ + _glh_discard_line(glh, glh->list.tail); + return 0; +} + +/*....................................................................... + * Set the prefix of subsequent history searches. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * line const char * The command line who's prefix is to be used. + * prefix_len int The length of the prefix. + * Output: + * return int 0 - OK. + * 1 - Error. + */ +int _glh_search_prefix(GlHistory *glh, const char *line, int prefix_len) +{ +/* + * Check the arguments. + */ + if(!glh) { + errno = EINVAL; + return 1; + }; +/* + * Is history enabled? + */ + if(!glh->enable || !glh->buffer || glh->max_lines == 0) + return 0; +/* + * Discard any existing prefix. + */ + glh->prefix = _glh_discard_copy(glh, glh->prefix); +/* + * Only store a copy of the prefix string if it isn't a zero-length string. + */ + if(prefix_len > 0) { +/* + * Get a reference-counted copy of the prefix from the history cache buffer. + */ + glh->prefix = _glh_acquire_copy(glh, line, prefix_len); +/* + * Was there insufficient buffer space? + */ + if(!glh->prefix) { + _err_record_msg(glh->err, "The search prefix is too long to store", + END_ERR_MSG); + errno = ENOMEM; + return 1; + }; + }; + return 0; +} + +/*....................................................................... + * Recall the oldest recorded line. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * line char * The input line buffer. On input this should contain + * the current input line, and on output, its contents + * will have been replaced with the oldest line. + * dim size_t The allocated dimensions of the line buffer. + * Output: + * return char * A pointer to line[0], or NULL if not found. + */ +char *_glh_oldest_line(GlHistory *glh, char *line, size_t dim) +{ + GlhLineNode *node; /* The line location node being checked */ +/* + * Check the arguments. + */ + if(!glh || !line) { + if(glh) + _err_record_msg(glh->err, "NULL argument(s)", END_ERR_MSG); + errno = EINVAL; + return NULL; + }; +/* + * Is history enabled? + */ + if(!glh->enable || !glh->buffer || glh->max_lines == 0) + return NULL; +/* + * Check the line dimensions. + */ + if(dim < strlen(line) + 1) { + _err_record_msg(glh->err, "'dim' argument inconsistent with strlen(line)", + END_ERR_MSG); + errno = EINVAL; + return NULL; + }; +/* + * Preserve the input line if needed. + */ + if(_glh_prepare_for_recall(glh, line)) + return NULL; +/* + * Locate the oldest line that belongs to the current group. + */ + for(node=glh->list.head; node && node->group != glh->group; + node = node->next) + ; +/* + * No line found? + */ + if(!node) + return NULL; +/* + * Record the above node as the starting point for subsequent + * searches. + */ + glh->recall = node; +/* + * Copy the recalled line into the provided line buffer. + */ + _glh_return_line(node->line, line, dim); +/* + * If we just returned the line that was being entered when the search + * session first started, cancel the search. + */ + if(node == glh->list.tail) + _glh_cancel_search(glh); + return line; +} + +/*....................................................................... + * Recall the line that was being entered when the search started. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * line char * The input line buffer. On input this should contain + * the current input line, and on output, its contents + * will have been replaced with the line that was + * being entered when the search was started. + * dim size_t The allocated dimensions of the line buffer. + * Output: + * return char * A pointer to line[0], or NULL if not found. + */ +char *_glh_current_line(GlHistory *glh, char *line, size_t dim) +{ +/* + * Check the arguments. + */ + if(!glh || !line) { + if(glh) + _err_record_msg(glh->err, "NULL argument(s)", END_ERR_MSG); + errno = EINVAL; + return NULL; + }; +/* + * If history isn't enabled, or no history search has yet been started, + * ignore the call. + */ + if(!glh->enable || !glh->buffer || glh->max_lines == 0 || !glh->recall) + return NULL; +/* + * Check the line dimensions. + */ + if(dim < strlen(line) + 1) { + _err_record_msg(glh->err, "'dim' argument inconsistent with strlen(line)", + END_ERR_MSG); + errno = EINVAL; + return NULL; + }; +/* + * Copy the recalled line into the provided line buffer. + */ + _glh_return_line(glh->list.tail->line, line, dim); +/* + * Since we have returned to the starting point of the search, cancel it. + */ + _glh_cancel_search(glh); + return line; +} + +/*....................................................................... + * Query the id of a history line offset by a given number of lines from + * the one that is currently being recalled. If a recall session isn't + * in progress, or the offset points outside the history list, 0 is + * returned. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * offset int The line offset (0 for the current line, < 0 + * for an older line, > 0 for a newer line. + * Output: + * return GlhLineID The identifier of the line that is currently + * being recalled, or 0 if no recall session is + * currently in progress. + */ +GlhLineID _glh_line_id(GlHistory *glh, int offset) +{ + GlhLineNode *node; /* The line location node being checked */ +/* + * Is history enabled? + */ + if(!glh->enable || !glh->buffer || glh->max_lines == 0) + return 0; +/* + * Search forward 'offset' lines to find the required line. + */ + if(offset >= 0) { + for(node=glh->recall; node && offset != 0; node=node->next) { + if(node->group == glh->group) + offset--; + }; + } else { + for(node=glh->recall; node && offset != 0; node=node->prev) { + if(node->group == glh->group) + offset++; + }; + }; + return node ? node->id : 0; +} + +/*....................................................................... + * Recall a line by its history buffer ID. If the line is no longer + * in the buffer, or the id is zero, NULL is returned. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * id GlhLineID The ID of the line to be returned. + * line char * The input line buffer. On input this should contain + * the current input line, and on output, its contents + * will have been replaced with the saved line. + * dim size_t The allocated dimensions of the line buffer. + * Output: + * return char * A pointer to line[0], or NULL if not found. + */ +char *_glh_recall_line(GlHistory *glh, GlhLineID id, char *line, size_t dim) +{ + GlhLineNode *node; /* The line location node being checked */ +/* + * Is history enabled? + */ + if(!glh->enable || !glh->buffer || glh->max_lines == 0) + return NULL; +/* + * Preserve the input line if needed. + */ + if(_glh_prepare_for_recall(glh, line)) + return NULL; +/* + * Search for the specified line. + */ + node = _glh_find_id(glh, id); +/* + * Not found? + */ + if(!node || node->group != glh->group) + return NULL; +/* + * Record the node of the matching line as the starting point + * for subsequent searches. + */ + glh->recall = node; +/* + * Copy the recalled line into the provided line buffer. + */ + _glh_return_line(node->line, line, dim); + return line; +} + +/*....................................................................... + * Save the current history in a specified file. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * filename const char * The name of the new file to record the + * history in. + * comment const char * Extra information such as timestamps will + * be recorded on a line started with this + * string, the idea being that the file can + * double as a command file. Specify "" if + * you don't care. + * max_lines int The maximum number of lines to save, or -1 + * to save all of the lines in the history + * list. + * Output: + * return int 0 - OK. + * 1 - Error. + */ +int _glh_save_history(GlHistory *glh, const char *filename, const char *comment, + int max_lines) +{ +#ifdef WITHOUT_FILE_SYSTEM + _err_record_msg(glh->err, "Can't save history without filesystem access", + END_ERR_MSG); + errno = EINVAL; + return 1; +#else + FILE *fp; /* The output file */ + GlhLineNode *node; /* The line being saved */ + GlhLineNode *head; /* The head of the list of lines to be saved */ + GlhLineSeg *seg; /* One segment of a line being saved */ +/* + * Check the arguments. + */ + if(!glh || !filename || !comment) { + if(glh) + _err_record_msg(glh->err, "NULL argument(s)", END_ERR_MSG); + errno = EINVAL; + return 1; + }; +/* + * Attempt to open the specified file. + */ + fp = fopen(filename, "w"); + if(!fp) + return _glh_cant_save_history(glh, "Can't open", filename, NULL); +/* + * If a ceiling on the number of lines to save was specified, count + * that number of lines backwards, to find the first line to be saved. + */ + head = NULL; + if(max_lines >= 0) { + for(head=glh->list.tail; head && --max_lines > 0; head=head->prev) + ; + }; + if(!head) + head = glh->list.head; +/* + * Write the contents of the history buffer to the history file, writing + * associated data such as timestamps, to a line starting with the + * specified comment string. + */ + for(node=head; node; node=node->next) { +/* + * Write peripheral information associated with the line, as a comment. + */ + if(fprintf(fp, "%s ", comment) < 0 || + _glh_write_timestamp(fp, node->timestamp) || + fprintf(fp, " %u\n", node->group) < 0) { + return _glh_cant_save_history(glh, "Error writing", filename, fp); + }; +/* + * Write the history line. + */ + for(seg=node->line->head; seg; seg=seg->next) { + size_t slen = seg->next ? GLH_SEG_SIZE : strlen(seg->s); + if(fwrite(seg->s, sizeof(char), slen, fp) != slen) + return _glh_cant_save_history(glh, "Error writing", filename, fp); + }; + fputc('\n', fp); + }; +/* + * Close the history file. + */ + if(fclose(fp) == EOF) + return _glh_cant_save_history(glh, "Error writing", filename, NULL); + return 0; +#endif +} + +#ifndef WITHOUT_FILE_SYSTEM +/*....................................................................... + * This is a private error return function of _glh_save_history(). It + * composes an error report in the error buffer, composed using + * sprintf("%s %s (%s)", message, filename, strerror(errno)). It then + * closes fp and returns the error return code of _glh_save_history(). + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * message const char * A message to be followed by the filename. + * filename const char * The name of the offending output file. + * fp FILE * The stream to be closed (send NULL if not + * open). + * Output: + * return int Always 1. + */ +static int _glh_cant_save_history(GlHistory *glh, const char *message, + const char *filename, FILE *fp) +{ + _err_record_msg(glh->err, message, filename, " (", + strerror(errno), ")", END_ERR_MSG); + if(fp) + (void) fclose(fp); + return 1; +} + +/*....................................................................... + * Write a timestamp to a given stdio stream, in the format + * yyyymmddhhmmss + * + * Input: + * fp FILE * The stream to write to. + * timestamp time_t The timestamp to be written. + * Output: + * return int 0 - OK. + * 1 - Error. + */ +static int _glh_write_timestamp(FILE *fp, time_t timestamp) +{ + struct tm *t; /* THe broken-down calendar time */ +/* + * Get the calendar components corresponding to the given timestamp. + */ + if(timestamp < 0 || (t = localtime(×tamp)) == NULL) { + if(fprintf(fp, "?") < 0) + return 1; + return 0; + }; +/* + * Write the calendar time as yyyymmddhhmmss. + */ + if(fprintf(fp, "%04d%02d%02d%02d%02d%02d", t->tm_year + 1900, t->tm_mon + 1, + t->tm_mday, t->tm_hour, t->tm_min, t->tm_sec) < 0) + return 1; + return 0; +} + +#endif + +/*....................................................................... + * Restore previous history lines from a given file. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * filename const char * The name of the file to read from. + * comment const char * The same comment string that was passed to + * _glh_save_history() when this file was + * written. + * line char * A buffer into which lines can be read. + * dim size_t The allocated dimension of line[]. + * Output: + * return int 0 - OK. + * 1 - Error. + */ +int _glh_load_history(GlHistory *glh, const char *filename, const char *comment, + char *line, size_t dim) +{ +#ifdef WITHOUT_FILE_SYSTEM + _err_record_msg(glh->err, "Can't load history without filesystem access", + END_ERR_MSG); + errno = EINVAL; + return 1; +#else + FILE *fp; /* The output file */ + size_t comment_len; /* The length of the comment string */ + time_t timestamp; /* The timestamp of the history line */ + unsigned group; /* The identifier of the history group to which */ + /* the line belongs. */ + int lineno; /* The line number being read */ +/* + * Check the arguments. + */ + if(!glh || !filename || !comment || !line) { + if(glh) + _err_record_msg(glh->err, "NULL argument(s)", END_ERR_MSG); + errno = EINVAL; + return 1; + }; +/* + * Measure the length of the comment string. + */ + comment_len = strlen(comment); +/* + * Clear the history list. + */ + _glh_clear_history(glh, 1); +/* + * Attempt to open the specified file. Don't treat it as an error + * if the file doesn't exist. + */ + fp = fopen(filename, "r"); + if(!fp) + return 0; +/* + * Attempt to read each line and preceding peripheral info, and add these + * to the history list. + */ + for(lineno=1; fgets(line, dim, fp) != NULL; lineno++) { + char *lptr; /* A pointer into the input line */ +/* + * Check that the line starts with the comment string. + */ + if(strncmp(line, comment, comment_len) != 0) { + return _glh_cant_load_history(glh, filename, lineno, + "Corrupt history parameter line", fp); + }; +/* + * Skip spaces and tabs after the comment. + */ + for(lptr=line+comment_len; *lptr && (*lptr==' ' || *lptr=='\t'); lptr++) + ; +/* + * The next word must be a timestamp. + */ + if(_glh_decode_timestamp(lptr, &lptr, ×tamp)) { + return _glh_cant_load_history(glh, filename, lineno, + "Corrupt timestamp", fp); + }; +/* + * Skip spaces and tabs. + */ + while(*lptr==' ' || *lptr=='\t') + lptr++; +/* + * The next word must be an unsigned integer group number. + */ + group = (int) strtoul(lptr, &lptr, 10); + if(*lptr != ' ' && *lptr != '\n') { + return _glh_cant_load_history(glh, filename, lineno, + "Corrupt group id", fp); + }; +/* + * Skip spaces and tabs. + */ + while(*lptr==' ' || *lptr=='\t') + lptr++; +/* + * There shouldn't be anything left on the line. + */ + if(*lptr != '\n') { + return _glh_cant_load_history(glh, filename, lineno, + "Corrupt parameter line", fp); + }; +/* + * Now read the history line itself. + */ + lineno++; + if(fgets(line, dim, fp) == NULL) + return _glh_cant_load_history(glh, filename, lineno, "Read error", fp); +/* + * Append the line to the history buffer. + */ + if(_glh_add_history(glh, line, 1)) { + return _glh_cant_load_history(glh, filename, lineno, + "Insufficient memory to record line", fp); + }; +/* + * Record the group and timestamp information along with the line. + */ + if(glh->list.tail) { + glh->list.tail->timestamp = timestamp; + glh->list.tail->group = group; + }; + }; +/* + * Close the file. + */ + (void) fclose(fp); + return 0; +#endif +} + +#ifndef WITHOUT_FILE_SYSTEM +/*....................................................................... + * This is a private error return function of _glh_load_history(). + */ +static int _glh_cant_load_history(GlHistory *glh, const char *filename, + int lineno, const char *message, FILE *fp) +{ + char lnum[20]; +/* + * Convert the line number to a string. + */ + sprintf(lnum, "%d", lineno); +/* + * Render an error message. + */ + _err_record_msg(glh->err, filename, ":", lnum, ":", message, END_ERR_MSG); +/* + * Close the file. + */ + if(fp) + (void) fclose(fp); + return 1; +} + +/*....................................................................... + * Read a timestamp from a string. + * + * Input: + * string char * The string to read from. + * Input/Output: + * endp char ** On output *endp will point to the next unprocessed + * character in string[]. + * timestamp time_t * The timestamp will be assigned to *t. + * Output: + * return int 0 - OK. + * 1 - Error. + */ +static int _glh_decode_timestamp(char *string, char **endp, time_t *timestamp) +{ + unsigned year,month,day,hour,min,sec; /* Calendar time components */ + struct tm t; +/* + * There are 14 characters in the date format yyyymmddhhmmss. + */ + enum {TSLEN=14}; + char timestr[TSLEN+1]; /* The timestamp part of the string */ +/* + * If the time wasn't available at the time that the line was recorded + * it will have been written as "?". Check for this before trying + * to read the timestamp. + */ + if(string[0] == '\?') { + *endp = string+1; + *timestamp = -1; + return 0; + }; +/* + * The timestamp is expected to be written in the form yyyymmddhhmmss. + */ + if(strlen(string) < TSLEN) { + *endp = string; + return 1; + }; +/* + * Copy the timestamp out of the string. + */ + strncpy(timestr, string, TSLEN); + timestr[TSLEN] = '\0'; +/* + * Decode the timestamp. + */ + if(sscanf(timestr, "%4u%2u%2u%2u%2u%2u", &year, &month, &day, &hour, &min, + &sec) != 6) { + *endp = string; + return 1; + }; +/* + * Advance the string pointer over the successfully read timestamp. + */ + *endp = string + TSLEN; +/* + * Copy the read values into a struct tm. + */ + t.tm_sec = sec; + t.tm_min = min; + t.tm_hour = hour; + t.tm_mday = day; + t.tm_wday = 0; + t.tm_yday = 0; + t.tm_mon = month - 1; + t.tm_year = year - 1900; + t.tm_isdst = -1; +/* + * Convert the contents of the struct tm to a time_t. + */ + *timestamp = mktime(&t); + return 0; +} +#endif + +/*....................................................................... + * Switch history groups. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * group unsigned The new group identifier. This will be recorded + * with subsequent history lines, and subsequent + * history searches will only return lines with + * this group identifier. This allows multiple + * separate history lists to exist within + * a single GlHistory object. Note that the + * default group identifier is 0. + * Output: + * return int 0 - OK. + * 1 - Error. + */ +int _glh_set_group(GlHistory *glh, unsigned group) +{ +/* + * Check the arguments. + */ + if(!glh) { + if(glh) + _err_record_msg(glh->err, "NULL argument(s)", END_ERR_MSG); + errno = EINVAL; + return 1; + }; +/* + * Is the group being changed? + */ + if(group != glh->group) { +/* + * Cancel any ongoing search. + */ + if(_glh_cancel_search(glh)) + return 1; +/* + * Record the new group. + */ + glh->group = group; + }; + return 0; +} + +/*....................................................................... + * Query the current history group. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * Output: + * return unsigned The group identifier. + */ +int _glh_get_group(GlHistory *glh) +{ + return glh ? glh->group : 0; +} + +/*....................................................................... + * Display the contents of the history list. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * write_fn GlWriteFn * The function to call to write the line, or + * 0 to discard the output. + * data void * Anonymous data to pass to write_fn(). + * fmt const char * A format string. This can contain arbitrary + * characters, which are written verbatim, plus + * any of the following format directives: + * %D - The date, like 2001-11-20 + * %T - The time of day, like 23:59:59 + * %N - The sequential entry number of the + * line in the history buffer. + * %G - The history group number of the line. + * %% - A literal % character. + * %H - The history line. + * all_groups int If true, display history lines from all + * history groups. Otherwise only display + * those of the current history group. + * max_lines int If max_lines is < 0, all available lines + * are displayed. Otherwise only the most + * recent max_lines lines will be displayed. + * Output: + * return int 0 - OK. + * 1 - Error. + */ +int _glh_show_history(GlHistory *glh, GlWriteFn *write_fn, void *data, + const char *fmt, int all_groups, int max_lines) +{ + GlhLineNode *node; /* The line being displayed */ + GlhLineNode *oldest; /* The oldest line to display */ + GlhLineSeg *seg; /* One segment of a line being displayed */ + enum {TSMAX=32}; /* The maximum length of the date and time string */ + char buffer[TSMAX+1]; /* The buffer in which to write the date and time */ + int idlen; /* The length of displayed ID strings */ + unsigned grpmax; /* The maximum group number in the buffer */ + int grplen; /* The number of characters needed to print grpmax */ + int len; /* The length of a string to be written */ +/* + * Check the arguments. + */ + if(!glh || !write_fn || !fmt) { + if(glh) + _err_record_msg(glh->err, "NULL argument(s)", END_ERR_MSG); + errno = EINVAL; + return 1; + }; +/* + * Is history enabled? + */ + if(!glh->enable || !glh->list.head) + return 0; +/* + * Work out the length to display ID numbers, choosing the length of + * the biggest number in the buffer. Smaller numbers will be padded + * with leading zeroes if needed. + */ + sprintf(buffer, "%lu", (unsigned long) glh->list.tail->id); + idlen = strlen(buffer); +/* + * Find the largest group number. + */ + grpmax = 0; + for(node=glh->list.head; node; node=node->next) { + if(node->group > grpmax) + grpmax = node->group; + }; +/* + * Find out how many characters are needed to display the group number. + */ + sprintf(buffer, "%u", (unsigned) grpmax); + grplen = strlen(buffer); +/* + * Find the node that follows the oldest line to be displayed. + */ + if(max_lines < 0) { + oldest = glh->list.head; + } else if(max_lines==0) { + return 0; + } else { + for(oldest=glh->list.tail; oldest; oldest=oldest->prev) { + if((all_groups || oldest->group == glh->group) && --max_lines <= 0) + break; + }; +/* + * If the number of lines in the buffer doesn't exceed the specified + * maximum, start from the oldest line in the buffer. + */ + if(!oldest) + oldest = glh->list.head; + }; +/* + * List the history lines in increasing time order. + */ + for(node=oldest; node; node=node->next) { +/* + * Only display lines from the current history group, unless + * told otherwise. + */ + if(all_groups || node->group == glh->group) { + const char *fptr; /* A pointer into the format string */ + struct tm *t = NULL; /* The broken time version of the timestamp */ +/* + * Work out the calendar representation of the node timestamp. + */ + if(node->timestamp != (time_t) -1) + t = localtime(&node->timestamp); +/* + * Parse the format string. + */ + fptr = fmt; + while(*fptr) { +/* + * Search for the start of the next format directive or the end of the string. + */ + const char *start = fptr; + while(*fptr && *fptr != '%') + fptr++; +/* + * Display any literal characters that precede the located directive. + */ + if(fptr > start) { + len = (int) (fptr - start); + if(write_fn(data, start, len) != len) + return 1; + }; +/* + * Did we hit a new directive before the end of the line? + */ + if(*fptr) { +/* + * Obey the directive. Ignore unknown directives. + */ + switch(*++fptr) { + case 'D': /* Display the date */ + if(t && strftime(buffer, TSMAX, "%Y-%m-%d", t) != 0) { + len = strlen(buffer); + if(write_fn(data, buffer, len) != len) + return 1; + }; + break; + case 'T': /* Display the time of day */ + if(t && strftime(buffer, TSMAX, "%H:%M:%S", t) != 0) { + len = strlen(buffer); + if(write_fn(data, buffer, len) != len) + return 1; + }; + break; + case 'N': /* Display the sequential entry number */ + sprintf(buffer, "%*lu", idlen, (unsigned long) node->id); + len = strlen(buffer); + if(write_fn(data, buffer, len) != len) + return 1; + break; + case 'G': + sprintf(buffer, "%*u", grplen, (unsigned) node->group); + len = strlen(buffer); + if(write_fn(data, buffer, len) != len) + return 1; + break; + case 'H': /* Display the history line */ + for(seg=node->line->head; seg; seg=seg->next) { + len = seg->next ? GLH_SEG_SIZE : strlen(seg->s); + if(write_fn(data, seg->s, len) != len) + return 1; + }; + break; + case '%': /* A literal % symbol */ + if(write_fn(data, "%", 1) != 1) + return 1; + break; + }; +/* + * Skip the directive. + */ + if(*fptr) + fptr++; + }; + }; + }; + }; + return 0; +} + +/*....................................................................... + * Change the size of the history buffer. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * bufsize size_t The number of bytes in the history buffer, or 0 + * to delete the buffer completely. + * Output: + * return int 0 - OK. + * 1 - Insufficient memory (the previous buffer + * will have been retained). No error message + * will be displayed. + */ +int _glh_resize_history(GlHistory *glh, size_t bufsize) +{ + int nbuff; /* The number of segments in the new buffer */ + int i; +/* + * Check the arguments. + */ + if(!glh) { + errno = EINVAL; + return 1; + }; +/* + * How many buffer segments does the requested buffer size correspond + * to? + */ + nbuff = (bufsize+GLH_SEG_SIZE-1) / GLH_SEG_SIZE; +/* + * Has a different size than the current size been requested? + */ + if(glh->nbuff != nbuff) { +/* + * Cancel any ongoing search. + */ + (void) _glh_cancel_search(glh); +/* + * Create a wholly new buffer? + */ + if(glh->nbuff == 0 && nbuff>0) { + glh->buffer = (GlhLineSeg *) malloc(sizeof(GlhLineSeg) * nbuff); + if(!glh->buffer) + return 1; + glh->nbuff = nbuff; + glh->nfree = glh->nbuff; + glh->nbusy = 0; + glh->nline = 0; +/* + * Link the currently unused nodes of the buffer into a list. + */ + glh->unused = glh->buffer; + for(i=0; i<glh->nbuff-1; i++) { + GlhLineSeg *seg = glh->unused + i; + seg->next = seg + 1; + }; + glh->unused[i].next = NULL; +/* + * Delete an existing buffer? + */ + } else if(nbuff == 0) { + _glh_clear_history(glh, 1); + free(glh->buffer); + glh->buffer = NULL; + glh->unused = NULL; + glh->nbuff = 0; + glh->nfree = 0; + glh->nbusy = 0; + glh->nline = 0; +/* + * Change from one finite buffer size to another? + */ + } else { + GlhLineSeg *buffer; /* The resized buffer */ + int nbusy; /* The number of used line segments in the new buffer */ +/* + * Starting from the oldest line in the buffer, discard lines until + * the buffer contains at most 'nbuff' used line segments. + */ + while(glh->list.head && glh->nbusy > nbuff) + _glh_discard_line(glh, glh->list.head); +/* + * Attempt to allocate a new buffer. + */ + buffer = (GlhLineSeg *) malloc(nbuff * sizeof(GlhLineSeg)); + if(!buffer) { + errno = ENOMEM; + return 1; + }; +/* + * Copy the used segments of the old buffer to the start of the new buffer. + */ + nbusy = 0; + for(i=0; i<GLH_HASH_SIZE; i++) { + GlhHashBucket *b = glh->hash.bucket + i; + GlhHashNode *hnode; + for(hnode=b->lines; hnode; hnode=hnode->next) { + GlhLineSeg *seg = hnode->head; + hnode->head = buffer + nbusy; + for( ; seg; seg=seg->next) { + buffer[nbusy] = *seg; + buffer[nbusy].next = seg->next ? &buffer[nbusy+1] : NULL; + nbusy++; + }; + }; + }; +/* + * Make a list of the new buffer's unused segments. + */ + for(i=nbusy; i<nbuff-1; i++) + buffer[i].next = &buffer[i+1]; + if(i < nbuff) + buffer[i].next = NULL; +/* + * Discard the old buffer. + */ + free(glh->buffer); +/* + * Install the new buffer. + */ + glh->buffer = buffer; + glh->nbuff = nbuff; + glh->nbusy = nbusy; + glh->nfree = nbuff - nbusy; + glh->unused = glh->nfree > 0 ? (buffer + nbusy) : NULL; + }; + }; + return 0; +} + +/*....................................................................... + * Set an upper limit to the number of lines that can be recorded in the + * history list, or remove a previously specified limit. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * max_lines int The maximum number of lines to allow, or -1 to + * cancel a previous limit and allow as many lines + * as will fit in the current history buffer size. + */ +void _glh_limit_history(GlHistory *glh, int max_lines) +{ + if(!glh) + return; +/* + * Apply a new limit? + */ + if(max_lines >= 0 && max_lines != glh->max_lines) { +/* + * Count successively older lines until we reach the start of the + * list, or until we have seen max_lines lines (at which point 'node' + * will be line number max_lines+1). + */ + int nline = 0; + GlhLineNode *node; + for(node=glh->list.tail; node && ++nline <= max_lines; node=node->prev) + ; +/* + * Discard any lines that exceed the limit. + */ + if(node) { + GlhLineNode *oldest = node->next; /* The oldest line to be kept */ +/* + * Delete nodes from the head of the list until we reach the node that + * is to be kept. + */ + while(glh->list.head && glh->list.head != oldest) + _glh_discard_line(glh, glh->list.head); + }; + }; +/* + * Record the new limit. + */ + glh->max_lines = max_lines; + return; +} + +/*....................................................................... + * Discard either all history, or the history associated with the current + * history group. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * all_groups int If true, clear all of the history. If false, + * clear only the stored lines associated with the + * currently selected history group. + */ +void _glh_clear_history(GlHistory *glh, int all_groups) +{ + int i; +/* + * Check the arguments. + */ + if(!glh) + return; +/* + * Cancel any ongoing search. + */ + (void) _glh_cancel_search(glh); +/* + * Delete all history lines regardless of group? + */ + if(all_groups) { +/* + * Claer the time-ordered list of lines. + */ + _rst_FreeList(glh->list.node_mem); + glh->list.head = glh->list.tail = NULL; + glh->nline = 0; + glh->id_node = NULL; +/* + * Clear the hash table. + */ + for(i=0; i<GLH_HASH_SIZE; i++) + glh->hash.bucket[i].lines = NULL; + _rst_FreeList(glh->hash.node_mem); +/* + * Move all line segment nodes back onto the list of unused segments. + */ + if(glh->buffer) { + glh->unused = glh->buffer; + for(i=0; i<glh->nbuff-1; i++) { + GlhLineSeg *seg = glh->unused + i; + seg->next = seg + 1; + }; + glh->unused[i].next = NULL; + glh->nfree = glh->nbuff; + glh->nbusy = 0; + } else { + glh->unused = NULL; + glh->nbusy = glh->nfree = 0; + }; +/* + * Just delete lines of the current group? + */ + } else { + GlhLineNode *node; /* The line node being checked */ + GlhLineNode *next; /* The line node that follows 'node' */ +/* + * Search out and delete the line nodes of the current group. + */ + for(node=glh->list.head; node; node=next) { +/* + * Keep a record of the following node before we delete the current + * node. + */ + next = node->next; +/* + * Discard this node? + */ + if(node->group == glh->group) + _glh_discard_line(glh, node); + }; + }; + return; +} + +/*....................................................................... + * Temporarily enable or disable the history list. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * enable int If true, turn on the history mechanism. If + * false, disable it. + */ +void _glh_toggle_history(GlHistory *glh, int enable) +{ + if(glh) + glh->enable = enable; +} + +/*....................................................................... + * Discard a given archived input line. + * + * Input: + * glh GlHistory * The history container object. + * node GlhLineNode * The line to be discarded, specified via its + * entry in the time-ordered list of historical + * input lines. + */ +static void _glh_discard_line(GlHistory *glh, GlhLineNode *node) +{ +/* + * Remove the node from the linked list. + */ + if(node->prev) + node->prev->next = node->next; + else + glh->list.head = node->next; + if(node->next) + node->next->prev = node->prev; + else + glh->list.tail = node->prev; +/* + * If we are deleting the node that is marked as the start point of the + * last ID search, remove the cached starting point. + */ + if(node == glh->id_node) + glh->id_node = NULL; +/* + * If we are deleting the node that is marked as the start point of the + * next prefix search, cancel the search. + */ + if(node == glh->recall) + _glh_cancel_search(glh); +/* + * Delete our copy of the line. + */ + node->line = _glh_discard_copy(glh, node->line); +/* + * Return the node to the freelist. + */ + (void) _del_FreeListNode(glh->list.node_mem, node); +/* + * Record the removal of a line from the list. + */ + glh->nline--; + return; +} + +/*....................................................................... + * Lookup the details of a given history line, given its id. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * id GlLineID The sequential number of the line. + * Input/Output: + * line const char ** A pointer to a copy of the history line will be + * assigned to *line. Beware that this pointer may + * be invalidated by the next call to any public + * history function. + * group unsigned * The group membership of the line will be assigned + * to *group. + * timestamp time_t * The timestamp of the line will be assigned to + * *timestamp. + * Output: + * return int 0 - The requested line wasn't found. + * 1 - The line was found. + */ +int _glh_lookup_history(GlHistory *glh, GlhLineID id, const char **line, + unsigned *group, time_t *timestamp) +{ + GlhLineNode *node; /* The located line location node */ +/* + * Check the arguments. + */ + if(!glh) + return 0; +/* + * Search for the line that has the specified ID. + */ + node = _glh_find_id(glh, id); +/* + * Not found? + */ + if(!node) + return 0; +/* + * Has the history line been requested? + */ + if(line) { +/* + * If necessary, reallocate the lookup buffer to accomodate the size of + * a copy of the located line. + */ + if(node->line->len + 1 > glh->lbuf_dim) { + int lbuf_dim = node->line->len + 1; + char *lbuf = realloc(glh->lbuf, lbuf_dim); + if(!lbuf) { + errno = ENOMEM; + return 0; + }; + glh->lbuf_dim = lbuf_dim; + glh->lbuf = lbuf; + }; +/* + * Copy the history line into the lookup buffer. + */ + _glh_return_line(node->line, glh->lbuf, glh->lbuf_dim); +/* + * Assign the lookup buffer as the returned line pointer. + */ + *line = glh->lbuf; + }; +/* + * Does the caller want to know the group of the line? + */ + if(group) + *group = node->group; +/* + * Does the caller want to know the timestamp of the line? + */ + if(timestamp) + *timestamp = node->timestamp; + return 1; +} + +/*....................................................................... + * Lookup a node in the history list by its ID. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * id GlhLineID The ID of the line to be returned. + * Output: + * return GlhLIneNode * The located node, or NULL if not found. + */ +static GlhLineNode *_glh_find_id(GlHistory *glh, GlhLineID id) +{ + GlhLineNode *node; /* The node being checked */ +/* + * Is history enabled? + */ + if(!glh->enable || !glh->list.head) + return NULL; +/* + * If possible, start at the end point of the last ID search. + * Otherwise start from the head of the list. + */ + node = glh->id_node; + if(!node) + node = glh->list.head; +/* + * Search forwards from 'node'? + */ + if(node->id < id) { + while(node && node->id != id) + node = node->next; + glh->id_node = node ? node : glh->list.tail; +/* + * Search backwards from 'node'? + */ + } else { + while(node && node->id != id) + node = node->prev; + glh->id_node = node ? node : glh->list.head; + }; +/* + * Return the located node (this will be NULL if the ID wasn't found). + */ + return node; +} + +/*....................................................................... + * Query the state of the history list. Note that any of the input/output + * pointers can be specified as NULL. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * Input/Output: + * enabled int * If history is enabled, *enabled will be + * set to 1. Otherwise it will be assigned 0. + * group unsigned * The current history group ID will be assigned + * to *group. + * max_lines int * The currently requested limit on the number + * of history lines in the list, or -1 if + * unlimited. + */ +void _glh_state_of_history(GlHistory *glh, int *enabled, unsigned *group, + int *max_lines) +{ + if(glh) { + if(enabled) + *enabled = glh->enable; + if(group) + *group = glh->group; + if(max_lines) + *max_lines = glh->max_lines; + }; +} + +/*....................................................................... + * Get the range of lines in the history buffer. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * Input/Output: + * oldest unsigned long * The sequential entry number of the oldest + * line in the history list will be assigned + * to *oldest, unless there are no lines, in + * which case 0 will be assigned. + * newest unsigned long * The sequential entry number of the newest + * line in the history list will be assigned + * to *newest, unless there are no lines, in + * which case 0 will be assigned. + * nlines int * The number of lines currently in the history + * list. + */ +void _glh_range_of_history(GlHistory *glh, unsigned long *oldest, + unsigned long *newest, int *nlines) +{ + if(glh) { + if(oldest) + *oldest = glh->list.head ? glh->list.head->id : 0; + if(newest) + *newest = glh->list.tail ? glh->list.tail->id : 0; + if(nlines) + *nlines = glh->nline; + }; +} + +/*....................................................................... + * Return the size of the history buffer and the amount of the + * buffer that is currently in use. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * Input/Output: + * buff_size size_t * The size of the history buffer (bytes). + * buff_used size_t * The amount of the history buffer that + * is currently occupied (bytes). + */ +void _glh_size_of_history(GlHistory *glh, size_t *buff_size, size_t *buff_used) +{ + if(glh) { + if(buff_size) + *buff_size = (glh->nbusy + glh->nfree) * GLH_SEG_SIZE; +/* + * Determine the amount of buffer space that is currently occupied. + */ + if(buff_used) + *buff_used = glh->nbusy * GLH_SEG_SIZE; + }; +} + +/*....................................................................... + * Return extra information (ie. in addition to that provided by errno) + * about the last error to occur in any of the public functions of this + * module. + * + * Input: + * glh GlHistory * The container of the history list. + * Output: + * return const char * A pointer to the internal buffer in which + * the error message is temporarily stored. + */ +const char *_glh_last_error(GlHistory *glh) +{ + return glh ? _err_get_msg(glh->err) : "NULL GlHistory argument"; +} + +/*....................................................................... + * Unless already stored, store a copy of the line in the history buffer, + * then return a reference-counted hash-node pointer to this copy. + * + * Input: + * glh GlHistory * The history maintenance buffer. + * line const char * The history line to be recorded. + * n size_t The length of the string, excluding any '\0' + * terminator. + * Output: + * return GlhHashNode * The hash-node containing the stored line, or + * NULL on error. + */ +static GlhHashNode *_glh_acquire_copy(GlHistory *glh, const char *line, + size_t n) +{ + GlhHashBucket *bucket; /* The hash-table bucket of the line */ + GlhHashNode *hnode; /* The hash-table node of the line */ + int i; +/* + * In which bucket should the line be recorded? + */ + bucket = glh_find_bucket(glh, line, n); +/* + * Is the line already recorded there? + */ + hnode = glh_find_hash_node(bucket, line, n); +/* + * If the line isn't recorded in the buffer yet, make room for it. + */ + if(!hnode) { + GlhLineSeg *seg; /* A line segment */ + int offset; /* An offset into line[] */ +/* + * How many string segments will be needed to record the new line, + * including space for a '\0' terminator? + */ + int nseg = ((n+1) + GLH_SEG_SIZE-1) / GLH_SEG_SIZE; +/* + * Discard the oldest history lines in the buffer until at least + * 'nseg' segments have been freed up, or until we run out of buffer + * space. + */ + while(glh->nfree < nseg && glh->nbusy > 0) + _glh_discard_line(glh, glh->list.head); +/* + * If the buffer is smaller than the new line, don't attempt to truncate + * it to fit. Simply don't archive it. + */ + if(glh->nfree < nseg) + return NULL; +/* + * Record the line in the first 'nseg' segments of the list of unused segments. + */ + offset = 0; + for(i=0,seg=glh->unused; i<nseg-1; i++,seg=seg->next, offset+=GLH_SEG_SIZE) + memcpy(seg->s, line + offset, GLH_SEG_SIZE); + memcpy(seg->s, line + offset, n-offset); + seg->s[n-offset] = '\0'; +/* + * Create a new hash-node for the line. + */ + hnode = (GlhHashNode *) _new_FreeListNode(glh->hash.node_mem); + if(!hnode) + return NULL; +/* + * Move the copy of the line from the list of unused segments to + * the hash node. + */ + hnode->head = glh->unused; + glh->unused = seg->next; + seg->next = NULL; + glh->nbusy += nseg; + glh->nfree -= nseg; +/* + * Prepend the new hash node to the list within the associated bucket. + */ + hnode->next = bucket->lines; + bucket->lines = hnode; +/* + * Initialize the rest of the members of the hash node. + */ + hnode->len = n; + hnode->reported = 0; + hnode->used = 0; + hnode->bucket = bucket; + }; +/* + * Increment the reference count of the line. + */ + hnode->used++; + return hnode; +} + +/*....................................................................... + * Decrement the reference count of the history line of a given hash-node, + * and if the count reaches zero, delete both the hash-node and the + * buffered copy of the line. + * + * Input: + * glh GlHistory * The history container object. + * hnode GlhHashNode * The node to be removed. + * Output: + * return GlhHashNode * The deleted hash-node (ie. NULL). + */ +static GlhHashNode *_glh_discard_copy(GlHistory *glh, GlhHashNode *hnode) +{ + if(hnode) { + GlhHashBucket *bucket = hnode->bucket; +/* + * If decrementing the reference count of the hash-node doesn't reduce + * the reference count to zero, then the line is still in use in another + * object, so don't delete it yet. Return NULL to indicate that the caller's + * access to the hash-node copy has been deleted. + */ + if(--hnode->used >= 1) + return NULL; +/* + * Remove the hash-node from the list in its parent bucket. + */ + if(bucket->lines == hnode) { + bucket->lines = hnode->next; + } else { + GlhHashNode *prev; /* The node which precedes hnode in the bucket */ + for(prev=bucket->lines; prev && prev->next != hnode; prev=prev->next) + ; + if(prev) + prev->next = hnode->next; + }; + hnode->next = NULL; +/* + * Return the line segments of the hash-node to the list of unused segments. + */ + if(hnode->head) { + GlhLineSeg *tail; /* The last node in the list of line segments */ + int nseg; /* The number of segments being discarded */ +/* + * Get the last node of the list of line segments referenced in the hash-node, + * while counting the number of line segments used. + */ + for(nseg=1,tail=hnode->head; tail->next; nseg++,tail=tail->next) + ; +/* + * Prepend the list of line segments used by the hash node to the + * list of unused line segments. + */ + tail->next = glh->unused; + glh->unused = hnode->head; + glh->nbusy -= nseg; + glh->nfree += nseg; + }; +/* + * Return the container of the hash-node to the freelist. + */ + hnode = (GlhHashNode *) _del_FreeListNode(glh->hash.node_mem, hnode); + }; + return NULL; +} + +/*....................................................................... + * Private function to locate the hash bucket associated with a given + * history line. + * + * This uses a hash-function described in the dragon-book + * ("Compilers - Principles, Techniques and Tools", by Aho, Sethi and + * Ullman; pub. Adison Wesley) page 435. + * + * Input: + * glh GlHistory * The history container object. + * line const char * The historical line to look up. + * n size_t The length of the line in line[], excluding + * any '\0' terminator. + * Output: + * return GlhHashBucket * The located hash-bucket. + */ +static GlhHashBucket *glh_find_bucket(GlHistory *glh, const char *line, + size_t n) +{ + unsigned long h = 0L; + int i; + for(i=0; i<n; i++) { + unsigned char c = line[i]; + h = 65599UL * h + c; /* 65599 is a prime close to 2^16 */ + }; + return glh->hash.bucket + (h % GLH_HASH_SIZE); +} + +/*....................................................................... + * Find a given history line within a given hash-table bucket. + * + * Input: + * bucket GlhHashBucket * The hash-table bucket in which to search. + * line const char * The historical line to lookup. + * n size_t The length of the line in line[], excluding + * any '\0' terminator. + * Output: + * return GlhHashNode * The hash-table entry of the line, or NULL + * if not found. + */ +static GlhHashNode *glh_find_hash_node(GlhHashBucket *bucket, const char *line, + size_t n) +{ + GlhHashNode *node; /* A node in the list of lines in the bucket */ +/* + * Compare each of the lines in the list of lines, against 'line'. + */ + for(node=bucket->lines; node; node=node->next) { + if(_glh_is_line(node, line, n)) + return node; + }; + return NULL; +} + +/*....................................................................... + * Return non-zero if a given string is equal to a given segmented line + * node. + * + * Input: + * hash GlhHashNode * The hash-table entry of the line. + * line const char * The string to be compared to the segmented + * line. + * n size_t The length of the line in line[], excluding + * any '\0' terminator. + * Output: + * return int 0 - The lines differ. + * 1 - The lines are the same. + */ +static int _glh_is_line(GlhHashNode *hash, const char *line, size_t n) +{ + GlhLineSeg *seg; /* A node in the list of line segments */ + int i; +/* + * Do the two lines have the same length? + */ + if(n != hash->len) + return 0; +/* + * Compare the characters of the segmented and unsegmented versions + * of the line. + */ + for(seg=hash->head; n>0 && seg; seg=seg->next) { + const char *s = seg->s; + for(i=0; n>0 && i<GLH_SEG_SIZE; i++,n--) { + if(*line++ != *s++) + return 0; + }; + }; + return 1; +} + +/*....................................................................... + * Return non-zero if a given line has the specified segmented search + * prefix. + * + * Input: + * line GlhHashNode * The line to be compared against the prefix. + * prefix GlhHashNode * The search prefix, or NULL to match any string. + * Output: + * return int 0 - The line doesn't have the specified prefix. + * 1 - The line has the specified prefix. + */ +static int _glh_line_matches_prefix(GlhHashNode *line, GlhHashNode *prefix) +{ + GlhLineStream lstr; /* The stream that is used to traverse 'line' */ + GlhLineStream pstr; /* The stream that is used to traverse 'prefix' */ +/* + * When prefix==NULL, this means that the nul string + * is to be matched, and this matches all lines. + */ + if(!prefix) + return 1; +/* + * Wrap the two history lines that are to be compared in iterator + * stream objects. + */ + glh_init_stream(&lstr, line); + glh_init_stream(&pstr, prefix); +/* + * If the prefix contains a glob pattern, match the prefix as a glob + * pattern. + */ + if(glh_contains_glob(prefix)) + return glh_line_matches_glob(&lstr, &pstr); +/* + * Is the prefix longer than the line being compared against it? + */ + if(prefix->len > line->len) + return 0; +/* + * Compare the line to the prefix. + */ + while(pstr.c != '\0' && pstr.c == lstr.c) { + glh_step_stream(&lstr); + glh_step_stream(&pstr); + }; +/* + * Did we reach the end of the prefix string before finding + * any differences? + */ + return pstr.c == '\0'; +} + +/*....................................................................... + * Copy a given history line into a specified output string. + * + * Input: + * hash GlhHashNode The hash-table entry of the history line to + * be copied. + * line char * A copy of the history line. + * dim size_t The allocated dimension of the line buffer. + */ +static void _glh_return_line(GlhHashNode *hash, char *line, size_t dim) +{ + GlhLineSeg *seg; /* A node in the list of line segments */ + int i; + for(seg=hash->head; dim>0 && seg; seg=seg->next) { + const char *s = seg->s; + for(i=0; dim>0 && i<GLH_SEG_SIZE; i++,dim--) + *line++ = *s++; + }; +/* + * If the line wouldn't fit in the output buffer, replace the last character + * with a '\0' terminator. + */ + if(dim==0) + line[-1] = '\0'; +} + +/*....................................................................... + * This function should be called whenever a new line recall is + * attempted. It preserves a copy of the current input line in the + * history list while other lines in the history list are being + * returned. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * line char * The current contents of the input line buffer. + * Output: + * return int 0 - OK. + * 1 - Error. + */ +static int _glh_prepare_for_recall(GlHistory *glh, char *line) +{ +/* + * If a recall session has already been started, but we have returned + * to the preserved copy of the input line, if the user has changed + * this line, we should replace the preserved copy of the original + * input line with the new one. To do this simply cancel the session, + * so that a new session is started below. + */ + if(glh->recall && glh->recall == glh->list.tail && + !_glh_is_line(glh->recall->line, line, strlen(line))) { + _glh_cancel_search(glh); + }; +/* + * If this is the first line recall of a new recall session, save the + * current line for potential recall later, and mark it as the last + * line recalled. + */ + if(!glh->recall) { + if(_glh_add_history(glh, line, 1)) + return 1; + glh->recall = glh->list.tail; +/* + * The above call to _glh_add_history() will have incremented the line + * sequence number, after adding the line. Since we only want this to + * to be incremented for permanently entered lines, decrement it again. + */ + glh->seq--; + }; + return 0; +} + +/*....................................................................... + * Return non-zero if a history search session is currently in progress. + * + * Input: + * glh GlHistory * The input-line history maintenance object. + * Output: + * return int 0 - No search is currently in progress. + * 1 - A search is in progress. + */ +int _glh_search_active(GlHistory *glh) +{ + return glh && glh->recall; +} + +/*....................................................................... + * Initialize a character iterator object to point to the start of a + * given history line. The first character of the line will be placed + * in str->c, and subsequent characters can be placed there by calling + * glh_strep_stream(). + * + * Input: + * str GlhLineStream * The iterator object to be initialized. + * line GlhHashNode * The history line to be iterated over (a + * NULL value here, is interpretted as an + * empty string by glh_step_stream()). + */ +static void glh_init_stream(GlhLineStream *str, GlhHashNode *line) +{ + str->seg = line ? line->head : NULL; + str->posn = 0; + str->c = str->seg ? str->seg->s[0] : '\0'; +} + +/*....................................................................... + * Copy the next unread character in the line being iterated, in str->c. + * Once the end of the history line has been reached, all futher calls + * set str->c to '\0'. + * + * Input: + * str GlhLineStream * The history-line iterator to read from. + */ +static void glh_step_stream(GlhLineStream *str) +{ +/* + * Get the character from the current iterator position within the line. + */ + str->c = str->seg ? str->seg->s[str->posn] : '\0'; +/* + * Unless we have reached the end of the string, move the iterator + * to the position of the next character in the line. + */ + if(str->c != '\0' && ++str->posn >= GLH_SEG_SIZE) { + str->posn = 0; + str->seg = str->seg->next; + }; +} + +/*....................................................................... + * Return non-zero if the specified search prefix contains any glob + * wildcard characters. + * + * Input: + * prefix GlhHashNode * The search prefix. + * Output: + * return int 0 - The prefix doesn't contain any globbing + * characters. + * 1 - The prefix contains at least one + * globbing character. + */ +static int glh_contains_glob(GlhHashNode *prefix) +{ + GlhLineStream pstr; /* The stream that is used to traverse 'prefix' */ +/* + * Wrap a stream iterator around the prefix, so that we can traverse it + * without worrying about line-segmentation. + */ + glh_init_stream(&pstr, prefix); +/* + * Search for unescaped wildcard characters. + */ + while(pstr.c != '\0') { + switch(pstr.c) { + case '\\': /* Skip escaped characters */ + glh_step_stream(&pstr); + break; + case '*': case '?': case '[': /* A wildcard character? */ + return 1; + break; + }; + glh_step_stream(&pstr); + }; +/* + * No wildcard characters were found. + */ + return 0; +} + +/*....................................................................... + * Return non-zero if the history line matches a search prefix containing + * a glob pattern. + * + * Input: + * lstr GlhLineStream * The iterator stream being used to traverse + * the history line that is being matched. + * pstr GlhLineStream * The iterator stream being used to traverse + * the pattern. + * Output: + * return int 0 - Doesn't match. + * 1 - The line matches the pattern. + */ +static int glh_line_matches_glob(GlhLineStream *lstr, GlhLineStream *pstr) +{ +/* + * Match each character of the pattern until we reach the end of the + * pattern. + */ + while(pstr->c != '\0') { +/* + * Handle the next character of the pattern. + */ + switch(pstr->c) { +/* + * A match zero-or-more characters wildcard operator. + */ + case '*': +/* + * Skip the '*' character in the pattern. + */ + glh_step_stream(pstr); +/* + * If the pattern ends with the '*' wildcard, then the + * rest of the line matches this. + */ + if(pstr->c == '\0') + return 1; +/* + * Using the wildcard to match successively longer sections of + * the remaining characters of the line, attempt to match + * the tail of the line against the tail of the pattern. + */ + while(lstr->c) { + GlhLineStream old_lstr = *lstr; + GlhLineStream old_pstr = *pstr; + if(glh_line_matches_glob(lstr, pstr)) + return 1; +/* + * Restore the line and pattern iterators for a new try. + */ + *lstr = old_lstr; + *pstr = old_pstr; +/* + * Prepare to try again, one character further into the line. + */ + glh_step_stream(lstr); + }; + return 0; /* The pattern following the '*' didn't match */ + break; +/* + * A match-one-character wildcard operator. + */ + case '?': +/* + * If there is a character to be matched, skip it and advance the + * pattern pointer. + */ + if(lstr->c) { + glh_step_stream(lstr); + glh_step_stream(pstr); +/* + * If we hit the end of the line, there is no character + * matching the operator, so the pattern doesn't match. + */ + } else { + return 0; + }; + break; +/* + * A character range operator, with the character ranges enclosed + * in matching square brackets. + */ + case '[': + glh_step_stream(pstr); /* Skip the '[' character */ + if(!lstr->c || !glh_matches_range(lstr->c, pstr)) + return 0; + glh_step_stream(lstr); /* Skip the character that matched */ + break; +/* + * A backslash in the pattern prevents the following character as + * being seen as a special character. + */ + case '\\': + glh_step_stream(pstr); /* Skip the backslash */ + /* Note fallthrough to default */ +/* + * A normal character to be matched explicitly. + */ + default: + if(lstr->c == pstr->c) { + glh_step_stream(lstr); + glh_step_stream(pstr); + } else { + return 0; + }; + break; + }; + }; +/* + * To get here, pattern must have been exhausted. The line only + * matches the pattern if the line as also been exhausted. + */ + return pstr->c == '\0' && lstr->c == '\0'; +} + +/*....................................................................... + * Match a character range expression terminated by an unescaped close + * square bracket. + * + * Input: + * c char The character to be matched with the range + * pattern. + * pstr GlhLineStream * The iterator stream being used to traverse + * the pattern. + * Output: + * return int 0 - Doesn't match. + * 1 - The character matched. + */ +static int glh_matches_range(char c, GlhLineStream *pstr) +{ + int invert = 0; /* True to invert the sense of the match */ + int matched = 0; /* True if the character matched the pattern */ + char lastc = '\0'; /* The previous character in the pattern */ +/* + * If the first character is a caret, the sense of the match is + * inverted and only if the character isn't one of those in the + * range, do we say that it matches. + */ + if(pstr->c == '^') { + glh_step_stream(pstr); + invert = 1; + }; +/* + * The hyphen is only a special character when it follows the first + * character of the range (not including the caret). + */ + if(pstr->c == '-') { + glh_step_stream(pstr); + if(c == '-') + matched = 1; +/* + * Skip other leading '-' characters since they make no sense. + */ + while(pstr->c == '-') + glh_step_stream(pstr); + }; +/* + * The hyphen is only a special character when it follows the first + * character of the range (not including the caret or a hyphen). + */ + if(pstr->c == ']') { + glh_step_stream(pstr); + if(c == ']') + matched = 1; + }; +/* + * Having dealt with the characters that have special meanings at + * the beginning of a character range expression, see if the + * character matches any of the remaining characters of the range, + * up until a terminating ']' character is seen. + */ + while(!matched && pstr->c && pstr->c != ']') { +/* + * Is this a range of characters signaled by the two end characters + * separated by a hyphen? + */ + if(pstr->c == '-') { + glh_step_stream(pstr); /* Skip the hyphen */ + if(pstr->c != ']') { + if(c >= lastc && c <= pstr->c) + matched = 1; + }; +/* + * A normal character to be compared directly. + */ + } else if(pstr->c == c) { + matched = 1; + }; +/* + * Record and skip the character that we just processed. + */ + lastc = pstr->c; + if(pstr->c != ']') + glh_step_stream(pstr); + }; +/* + * Find the terminating ']'. + */ + while(pstr->c && pstr->c != ']') + glh_step_stream(pstr); +/* + * Did we find a terminating ']'? + */ + if(pstr->c == ']') { +/* + * Skip the terminating ']'. + */ + glh_step_stream(pstr); +/* + * If the pattern started with a caret, invert the sense of the match. + */ + if(invert) + matched = !matched; +/* + * If the pattern didn't end with a ']', then it doesn't match, + * regardless of the value of the required sense of the match. + */ + } else { + matched = 0; + }; + return matched; +} + |