/* history.c -- standalone history library */
-/* Copyright (C) 1989-2023 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.
#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
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)
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
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++;
{
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;
}
}
projects / thirdparty / bash.git / blobdiff