/* * Copyright (c) 2000, 2001 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 "history.h"#include "freelist.h"/* * GlLineNode's record the location and length of historical lines in * a buffer array. */typedef struct GlLineNode GlLineNode;struct GlLineNode {  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. */  GlLineNode *next;    /* The next youngest line in the list */  GlLineNode *prev;    /* The next oldest line in the list */  int start;           /* The start index of the line in the buffer */  int nchar;           /* The total length of the line, including the '\0' */};/* * The number of GlLineNode elements per freelist block. */#define LINE_NODE_BLK 100/* * Lines are organised in the buffer from oldest to newest. The * positions of the lines are recorded in a doubly linked list * of GlLineNode objects. */typedef struct {  FreeList *node_mem;    /* A freelist of GlLineNode objects */   GlLineNode *head;      /* The head of the list of lines */  GlLineNode *tail;      /* The tail of the list of lines */} GlLineList;/* * All elements of the history mechanism are recorded in an object of * the following type. */struct GlHistory {  char *buffer;       /* A circular buffer used to record historical input */                      /*  lines. */  size_t buflen;      /* The length of the buffer array */  GlLineList list;    /* A list of the start of lines in buffer[] */  GlLineNode *recall; /* The last line recalled, or NULL if no recall */                      /*  session is currently active. */  GlLineNode *id_node;/* The node at which the last ID search terminated */  const char *prefix; /* A pointer to the line containing the prefix that */                      /*  is being searched for. */  int prefix_len;     /* The length of the prefix */  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 */};static char *_glh_restore_line(GlHistory *glh, char *line, size_t dim);static int _glh_cant_load_history(GlHistory *glh, const char *filename,				  int lineno, const char *message, FILE *fp);static int _glh_write_timestamp(FILE *fp, time_t timestamp);static int _glh_decode_timestamp(char *string, char **endp, time_t *t);static void _glh_discard_node(GlHistory *glh, GlLineNode *node);static GlLineNode *_glh_find_id(GlHistory *glh, GlhLineID id);/*....................................................................... * Create a line history maintenance object. * * Input: *  buflen     size_t    The number of bytes to allocate to the circular *                       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 *//* * Allocate the container. */  glh = (GlHistory *) malloc(sizeof(GlHistory));  if(!glh) {    fprintf(stderr, "_new_GlHistory: Insufficient memory.\n");    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->buffer = NULL;  glh->buflen = buflen;  glh->list.node_mem = NULL;  glh->list.head = NULL;  glh->list.tail = NULL;  glh->recall = NULL;  glh->id_node = NULL;  glh->prefix = NULL;  glh->prefix_len = 0;  glh->seq = 0;  glh->group = 0;  glh->nline = 0;  glh->max_lines = -1;  glh->enable = 1;/* * Allocate the buffer, if required. */  if(buflen > 0) {    glh->buffer = (char *) malloc(sizeof(char) * buflen);    if(!glh->buffer) {      fprintf(stderr, "_new_GlHistory: Insufficient memory.\n");      return _del_GlHistory(glh);    };  };/* * Allocate the GlLineNode freelist. */  glh->list.node_mem = _new_FreeList("_new_GlHistory", sizeof(GlLineNode),				     LINE_NODE_BLK);  if(!glh->list.node_mem)    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 buffer. */    if(glh->buffer) {      free(glh->buffer);      glh->buffer = NULL;    };/* * Delete the freelist of GlLineNode's. */    glh->list.node_mem = _del_FreeList("_del_GlHistory", 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 container. */    free(glh);  };  return NULL;}/*....................................................................... * Add a new line to the end of the history buffer, wrapping round to the * start of the buffer 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 and *                    lines which match the previous line in the history *                    buffer, 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){  GlLineList *list; /* The line location list */  int nchar;        /* The number of characters needed to record the line */  GlLineNode *node; /* The new line location list node */  int empty;        /* True if the string is empty */  const char *nlptr;/* A pointer to a newline character in line[] */  int i;/* * Check the arguments. */  if(!glh || !line)    return 1;/* * Is history enabled? */  if(!glh->enable || !glh->buffer || glh->max_lines == 0)    return 0;/* * Get the line location list. */  list = &glh->list;/* * Cancel any ongoing search. */  if(_glh_cancel_search(glh))    return 1;/* * See how much buffer space will be needed to record the line? * * If the string contains a terminating newline character, arrange to * have the archived line NUL terminated at this point. */  nlptr = strchr(line, '\n');  if(nlptr)    nchar = (nlptr - line) + 1;  else    nchar = strlen(line) + 1;/* * If the line is too big to fit in the buffer, truncate it. */  if(nchar > glh->buflen)    nchar = glh->buflen;/* * Is the line empty? */  empty = 1;  for(i=0; i<nchar-1 && 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;/* * If the new line is the same as the most recently added line, * don't add it again, unless explicitly told to. */  if(!force &&     list->tail && strlen(glh->buffer + list->tail->start) == nchar-1 &&     strncmp(line, glh->buffer + list->tail->start, nchar-1)==0)    return 0;/* * Allocate the list node that will record the line location. */  node = (GlLineNode *) _new_FreeListNode(list->node_mem);  if(!node)    return 1;/* * Is the buffer empty? */  if(!list->head) {/* * Place the line at the beginning of the buffer. */    strncpy(glh->buffer, line, nchar);    glh->buffer[nchar-1] = '\0';/* * Record the location of the line. */    node->start = 0;/* * The buffer has one or more lines in it. */  } else {/* * Place the start of the new line just after the most recently * added line. */    int start = list->tail->start + list->tail->nchar;/* * If there is insufficient room between the end of the most * recently added line and the end of the buffer, we place the * line at the beginning of the buffer. To make as much space * as possible for this line, we first delete any old lines * at the end of the buffer, then shift the remaining contents * of the buffer to the end of the buffer. */    if(start + nchar >= glh->buflen) {      GlLineNode *last; /* The last line in the buffer */      GlLineNode *ln;   /* A member of the list of line locations */      int shift;        /* The shift needed to move the contents of the */                        /*  buffer to its end. *//* * Delete any old lines between the most recent line and the end of the * buffer. */      while(list->head && list->head->start > list->tail->start)	_glh_discard_node(glh, list->head);/* * Find the line that is nearest the end of the buffer. */      last = NULL;      for(ln=list->head; ln; ln=ln->next) {	if(!last || ln->start > last->start)	  last = ln;      };/* * How big a shift is needed to move the existing contents of the * buffer to the end of the buffer? */      shift = last ? (glh->buflen - (last->start + last->nchar)) : 0;/* * Is any shift needed? */      if(shift > 0) {/* * Move the buffer contents to the end of the buffer. */	memmove(glh->buffer + shift, glh->buffer, glh->buflen - shift);/* * Update the listed locations to reflect the shift. */	for(ln=list->head; ln; ln=ln->next)	  ln->start += shift;      };/* * The new line should now be located at the start of the buffer. */      start = 0;    };/* * Make space for the new line at the beginning of the buffer by * deleting the oldest lines. This just involves removing them * from the list of used locations. Also enforce the current * maximum number of lines. */    while(list->head &&	  ((list->head->start >= start && list->head->start - start < nchar) ||	   (glh->max_lines >= 0 && glh->nline>=glh->max_lines))) {      _glh_discard_node(glh, list->head);    };/* * Copy the new line into the buffer. */    memcpy(glh->buffer + start, line, nchar);    glh->buffer[start + nchar - 1] = '\0';/* * Record its location. */    node->start = start;  };/* * Append the line location node to the end of the list. */  node->id = glh->seq++;  node->timestamp = time(NULL);  node->group = glh->group;  node->nchar = nchar;  node->next = NULL;  node->prev = list->tail;  if(list->tail)    list->tail->next = node;  else    list->head = node;  list->tail = node;  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 dimensions 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){  GlLineNode *node; /* The line location node being checked */  int first;        /* True if this is the start of a new search *//* * Check the arguments. */  if(!glh || !line) {    fprintf(stderr, "_glh_find_backwards: NULL argument(s).\n");    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) {    fprintf(stderr,       "_glh_find_backwards: 'dim' inconsistent with strlen(line) contents.\n");    return NULL;  };/* * Is this the start of a new search? */  first = glh->recall==NULL;/* * If this is the first search backwards, save the current line * for potential recall later, and mark it as the last line * recalled. */  if(first) {    if(_glh_add_history(glh, line, 1))      return NULL;    glh->recall = glh->list.tail;  };/* * If there is no search prefix, the prefix last set by glh_search_prefix() * doesn't exist in the history buffer. */  if(!glh->prefix)    return NULL;/* * From where should we start the search? */  if(glh->recall)    node = glh->recall->prev;  else    node = glh->list.tail;/* * Search backwards through the list for the first match with the * prefix string. */  for( ; node &&      (node->group != glh->group ||       strncmp(glh->buffer + node->start, glh->prefix, glh->prefix_len) != 0);      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. */    strncpy(line, glh->buffer + node->start, dim);    line[dim-1] = '\0';    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.