diff options
Diffstat (limited to 'history.c')
| -rw-r--r-- | history.c | 161 |
1 files changed, 140 insertions, 21 deletions
@@ -1,6 +1,6 @@ /* history.c -- standalone history library */ -/* Copyright (C) 1989-2021 Free Software Foundation, Inc. +/* Copyright (C) 1989-2024 Free Software Foundation, Inc. This file contains the GNU History Library (History), a set of routines for managing the text of previously typed lines. @@ -42,6 +42,7 @@ # endif # include <unistd.h> #endif +#include "posixtime.h" #include <errno.h> @@ -60,24 +61,39 @@ extern int errno; #define MAX_HISTORY_INITIAL_SIZE 8192 /* The number of slots to increase the_history by. */ -#define DEFAULT_HISTORY_GROW_SIZE 50 +#define DEFAULT_HISTORY_GROW_SIZE 256 static char *hist_inittime (void); +static int history_list_grow_size (void); +static void history_list_resize (int); /* XXX - size_t? */ +static void advance_history (void); + /* **************************************************************** */ /* */ /* History Functions */ /* */ /* **************************************************************** */ -/* An array of HIST_ENTRY. This is where we store the history. */ +/* An array of HIST_ENTRY. This is where we store the history. the_history is + a roving pointer somewhere into this, so the user-visible history list is + a window into real_history starting at the_history and extending + history_length entries. */ +static HIST_ENTRY **real_history = (HIST_ENTRY **)NULL; + +/* The current number of slots allocated to the input_history. */ +static int real_history_size = 0; + +/* A pointer to somewhere in real_history, where the user-visible history + starts. */ static HIST_ENTRY **the_history = (HIST_ENTRY **)NULL; /* Non-zero means that we have enforced a limit on the amount of history that we save. */ static int history_stifled; -/* The current number of slots allocated to the input_history. */ +/* The number of history entries available for user use, starting at the_history. + real_history_size - history_size == the_history - real_history */ static int history_size; /* If HISTORY_STIFLED is non-zero, then this is the maximum number of @@ -89,12 +105,59 @@ int max_input_history; /* backwards compatibility */ life easier for outside callers. */ int history_offset; -/* The number of strings currently stored in the history list. */ +/* The number of strings currently stored in the history list. This is + always <= real_history_length */ int history_length; /* The logical `base' of the history array. It defaults to 1. */ int history_base = 1; +/* Compute the number of bits required to store a given nonnegative integer. + + NOTE: _bit_length(0) == 0 */ +static inline unsigned +_bit_length(unsigned n) +{ + /* This implementation is for simplicity, not for performance, but it is + fast enough for our purposes here. */ + unsigned count = 0; + while (n) + { + n >>= 1; + count++; + } + return count; +} + +/* Compute a grow size that adjusts to the size of the history. + + We aim to grow by roughly sqrt(history_size) in order to amortize the cost of + realloc() and memmove(). This reduces the total cost of the memmoves from + O(N^2) to O(N*sqrt(N)). */ +static int +history_list_grow_size (void) +{ + int width, r; + /* Handle small positive values and guard against history_length accidentally + being negative. */ + const int MIN_BITS = 10; + if (history_length < (1 << MIN_BITS)) + return DEFAULT_HISTORY_GROW_SIZE; + + /* For other values, we just want something easy to compute that grows roughly + as sqrt(N), where N=history_length. We use approximately 2^((k+1)/2), + where k is the bit length of N. This bounds the value between sqrt(2N) and + 2*sqrt(N). */ + width = MIN_BITS + _bit_length(history_length >> MIN_BITS); + + /* If width is odd then this is 2^((width+1)/2). An even width gives a value + of 3*2^((width-2)/2) ~ 1.06*2^((width+1)/2). */ + r = (1 << (width / 2)) + (1 << ((width - 1) / 2)); + + /* Make sure we always expand the list by at least DEFAULT_HISTORY_GROW_SIZE */ + return ((r < DEFAULT_HISTORY_GROW_SIZE) ? DEFAULT_HISTORY_GROW_SIZE : r); +} + /* Return the current HISTORY_STATE of the history. */ HISTORY_STATE * history_get_history_state (void) @@ -261,7 +324,7 @@ hist_inittime (void) time_t t; char ts[64], *ret; - t = (time_t) time ((time_t *)0); + t = getnow (); #if defined (HAVE_VSNPRINTF) /* assume snprintf if vsnprintf exists */ snprintf (ts, sizeof (ts) - 1, "X%lu", (unsigned long) t); #else @@ -273,6 +336,48 @@ hist_inittime (void) return ret; } +/* Ensure space for new history entries by resetting the start pointer + (the_history) and resizing real_history if necessary. */ +static void +history_list_resize (int new_size) +{ + /* Do nothing there is already enough user space. history_length is always <= + real_history_size */ + if (new_size < history_length) + return; + + /* If we need to, reset the_history to the start of real_history and + start over. */ + if (the_history != real_history) + memmove (real_history, the_history, history_length * sizeof (HIST_ENTRY *)); + + /* Don't bother if real_history_size is already big enough, since at this + point the_history == real_history and we will set history_size to + real_history_size. We don't shrink the history list. */ + if (new_size > real_history_size) + { + real_history = (HIST_ENTRY **) xrealloc (real_history, new_size * sizeof (HIST_ENTRY *)); + real_history_size = new_size; + } + the_history = real_history; + history_size = real_history_size; + + if (history_size > history_length) + memset (real_history + history_length, 0, (history_size - history_length) * sizeof (HIST_ENTRY *)); +} + +static void +advance_history (void) +{ + /* Advance 'the_history' pointer to simulate dropping the first entry. */ + the_history++; + history_size--; + + /* If full, move all the entries (and trailing NULL) to the beginning. */ + if (history_length == history_size) + history_list_resize (history_length + history_list_grow_size ()); +} + /* Place STRING at the end of the history list. The data field is set to NULL. */ void @@ -283,8 +388,6 @@ add_history (const char *string) if (history_stifled && (history_length == history_max_entries)) { - register int i; - /* If the history is stifled, and history_length is zero, and it equals history_max_entries, we don't save items. */ if (history_length == 0) @@ -294,9 +397,8 @@ add_history (const char *string) if (the_history[0]) (void) free_history_entry (the_history[0]); - /* Copy the rest of the entries, moving down one slot. Copy includes - trailing NULL. */ - memmove (the_history, the_history + 1, history_length * sizeof (HIST_ENTRY *)); + /* Advance the pointer into real_history, resizing if necessary. */ + advance_history (); new_length = history_length; history_base++; @@ -305,23 +407,20 @@ add_history (const char *string) { if (history_size == 0) { + int initial_size; if (history_stifled && history_max_entries > 0) - history_size = (history_max_entries > MAX_HISTORY_INITIAL_SIZE) + initial_size = (history_max_entries > MAX_HISTORY_INITIAL_SIZE) ? MAX_HISTORY_INITIAL_SIZE : history_max_entries + 2; else - history_size = DEFAULT_HISTORY_INITIAL_SIZE; - the_history = (HIST_ENTRY **)xmalloc (history_size * sizeof (HIST_ENTRY *)); + initial_size = DEFAULT_HISTORY_INITIAL_SIZE; + history_list_resize (initial_size); new_length = 1; } else { if (history_length == (history_size - 1)) - { - history_size += DEFAULT_HISTORY_GROW_SIZE; - the_history = (HIST_ENTRY **) - xrealloc (the_history, history_size * sizeof (HIST_ENTRY *)); - } + history_list_resize (real_history_size + history_list_grow_size ()); new_length = history_length + 1; } } @@ -460,7 +559,7 @@ _hs_replace_history_data (int which, histdata_t *old, histdata_t *new) } last = -1; - for (i = 0; i < history_length; i++) + for (i = history_length - 1; i >= 0; i--) { entry = the_history[i]; if (entry == 0) @@ -477,7 +576,27 @@ _hs_replace_history_data (int which, histdata_t *old, histdata_t *new) entry = the_history[last]; entry->data = new; /* XXX - we don't check entry->old */ } -} +} + +int +_hs_search_history_data (histdata_t *needle) +{ + register int i; + HIST_ENTRY *entry; + + if (history_length == 0 || the_history == 0) + return -1; + + for (i = history_length - 1; i >= 0; i--) + { + entry = the_history[i]; + if (entry == 0) + continue; + if (entry->data == needle) + return i; + } + return -1; +} /* Remove history element WHICH from the history. The removed element is returned to you so you can free the line, data, |