Commits

Armin Rigo committed 99fba7e

A diff to fix quadratic complexity of loading the .bash_history file.

  • Participants
  • Parent commits 67105c7

Comments (0)

Files changed (1)

File hack/misc/bash-4.3-histfile.diff

+Only in lib/readline/: bind.o
+Only in lib/readline/: callback.o
+Only in lib/readline/: colors.o
+Only in lib/readline/: compat.o
+Only in lib/readline/: complete.o
+Only in lib/readline/: display.o
+Common subdirectories: ../bash-4.3/lib/readline/doc and lib/readline/doc
+Common subdirectories: ../bash-4.3/lib/readline/examples and lib/readline/examples
+Only in lib/readline/: funmap.o
+Only in lib/readline/: histexpand.o
+Only in lib/readline/: histfile.o
+diff -u ../bash-4.3/lib/readline/history.c lib/readline/history.c
+--- ../bash-4.3/lib/readline/history.c	2013-07-08 16:40:32.000000000 +0200
++++ lib/readline/history.c	2014-07-19 13:01:22.970475432 +0200
+@@ -61,6 +61,7 @@
+ 
+ /* An array of HIST_ENTRY.  This is where we store the history. */
+ static HIST_ENTRY **the_history = (HIST_ENTRY **)NULL;
++static HIST_ENTRY **the_history_base = (HIST_ENTRY **)NULL;   /* --AR-- */
+ 
+ /* Non-zero means that we have enforced a limit on the amount of
+    history that we save. */
+@@ -91,7 +92,7 @@
+   HISTORY_STATE *state;
+ 
+   state = (HISTORY_STATE *)xmalloc (sizeof (HISTORY_STATE));
+-  state->entries = the_history;
++  state->entries = the_history; abort();  // --AR--
+   state->offset = history_offset;
+   state->length = history_length;
+   state->size = history_size;
+@@ -107,7 +108,7 @@
+ history_set_history_state (state)
+      HISTORY_STATE *state;
+ {
+-  the_history = state->entries;
++  the_history = state->entries; abort();  // --AR--
+   history_offset = state->offset;
+   history_length = state->length;
+   history_size = state->size;
+@@ -268,7 +269,7 @@
+ 
+   if (history_stifled && (history_length == history_max_entries))
+     {
+-      register int i;
++      //register int i;
+ 
+       /* If the history is stifled, and history_length is zero,
+ 	 and it equals history_max_entries, we don't save items. */
+@@ -280,29 +281,33 @@
+ 	(void) free_history_entry (the_history[0]);
+ 
+       /* Copy the rest of the entries, moving down one slot. */
+-      for (i = 0; i < history_length; i++)
+-	the_history[i] = the_history[i + 1];
++      //for (i = 0; i < history_length; i++)
++      //  the_history[i] = the_history[i + 1];
++      // --AR-- changed to:
++      the_history++;
++      history_size--;
+ 
+       history_base++;
+     }
+   else
+     {
+-      if (history_size == 0)
+-	{
+-	  history_size = DEFAULT_HISTORY_GROW_SIZE;
+-	  the_history = (HIST_ENTRY **)xmalloc (history_size * sizeof (HIST_ENTRY *));
+-	  history_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_length++;
+ 	}
++  //
++  // --AR--:
++  if (history_length >= history_size)
++    {
++      HIST_ENTRY **p;
++      history_size = history_length;
++      history_size += (history_size >> 2);  // --AR-- avoid quadratic time
++      history_size += DEFAULT_HISTORY_GROW_SIZE;
++      p = (HIST_ENTRY **)xmalloc(history_size * sizeof (HIST_ENTRY *));
++      if (the_history_base != NULL) {
++        memcpy(p, the_history, (history_length - 1) * sizeof (HIST_ENTRY *));
++        xfree(the_history_base);
++      }
++      the_history = p;
++      the_history_base = p;
+     }
+ 
+   temp = alloc_history_entry (string, hist_inittime ());
+Only in lib/readline/: history.o
+Only in lib/readline/: histsearch.o
+Only in lib/readline/: input.o
+Only in lib/readline/: isearch.o
+Only in lib/readline/: keymaps.o
+Only in lib/readline/: kill.o
+Only in lib/readline/: libhistory.a
+Only in lib/readline/: libreadline.a
+Only in lib/readline/: macro.o
+Only in lib/readline/: Makefile
+Only in lib/readline/: mbutil.o
+Only in lib/readline/: misc.o
+Only in lib/readline/: nls.o
+Only in lib/readline/: parens.o
+Only in lib/readline/: parse-colors.o
+Only in lib/readline/: readline.o
+Only in lib/readline/: rltty.o
+Only in lib/readline/: savestring.o
+Only in lib/readline/: search.o
+Only in lib/readline/: shell.o
+Only in lib/readline/: signals.o
+Only in lib/readline/: terminal.o
+Only in lib/readline/: text.o
+Only in lib/readline/: tilde.o
+Only in lib/readline/: undo.o
+Only in lib/readline/: util.o
+Only in lib/readline/: vi_mode.o
+Only in lib/readline/: xfree.o
+Only in lib/readline/: xmalloc.o