history.c

xorp源码hg

/*
 * 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.