Hi Folks,
I love dmenu and have been using it for a while. I wanted to add support
for MRU type sorting of commands. I've created a patch which does this in
a separate executable for backwards compatibility. It's been a while since
I've written C, so please let me know if I need to fix anything. I would
love to see this become part of dmenu.
Cheers,
--
*Eyal Erez <**ones...@gmail.com* <ones...@gmail.com>*>*
There are 10 types of people, those who know binary and those who don't.
From 8cb3b81fb32b750eda5482ae3948525142ccd4ea Mon Sep 17 00:00:00 2001
From: Eyal Erez <e...@spotify.com>
Date: Wed, 20 Nov 2013 18:30:47 -0500
Subject: [PATCH] Adding MRU support
Change-Id: I1ddd0e89199807aac1ce33627d34b33e09f48b68
---
.gitignore | 6 ++
Makefile | 21 +++++--
config.mk | 2 +-
dmenu_do | 2 +
dmenu_mru.c | 187 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
mru.c | 131 ++++++++++++++++++++++++++++++++++++++++++
mru.h | 78 +++++++++++++++++++++++++
7 files changed, 421 insertions(+), 6 deletions(-)
create mode 100644 .gitignore
create mode 100755 dmenu_do
create mode 100644 dmenu_mru.c
create mode 100644 mru.c
create mode 100644 mru.h
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..5f0a940
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,6 @@
+config.h
+dmenu
+dmenu_mru
+stest
+*.o
+*.tar.gz
\ No newline at end of file
diff --git a/Makefile b/Makefile
index 0f7dfbd..3a4e1b5 100644
--- a/Makefile
+++ b/Makefile
@@ -3,10 +3,10 @@
include config.mk
-SRC = dmenu.c draw.c stest.c
+SRC = dmenu.c draw.c stest.c dmenu_mru.c mru.c
OBJ = ${SRC:.c=.o}
-all: options dmenu stest
+all: options dmenu stest dmenu_mru
options:
@echo dmenu build options:
@@ -14,6 +14,9 @@ options:
@echo "LDFLAGS = ${LDFLAGS}"
@echo "CC = ${CC}"
+debug: CFLAGS += -g
+debug: all
+
.c.o:
@echo CC -c $<
@${CC} -c $< ${CFLAGS}
@@ -32,14 +35,18 @@ stest: stest.o
@echo CC -o $@
@${CC} -o $@ stest.o ${LDFLAGS}
+dmenu_mru: dmenu_mru.o mru.o
+ @echo CC -o $@
+ @${CC} -o $@ dmenu_mru.o mru.o ${LDFLAGS}
+
clean:
@echo cleaning
- @rm -f dmenu stest ${OBJ} dmenu-${VERSION}.tar.gz
+ @rm -f dmenu stest dmenu_mru ${OBJ} dmenu-${VERSION}.tar.gz
dist: clean
@echo creating dist tarball
@mkdir -p dmenu-${VERSION}
- @cp LICENSE Makefile README config.mk dmenu.1 draw.h dmenu_path dmenu_run stest.1 ${SRC} dmenu-${VERSION}
+ @cp LICENSE Makefile README config.mk dmenu.1 draw.h mru.h dmenu_path dmenu_run dmenu_do stest.1 ${SRC} dmenu-${VERSION}
@tar -cf dmenu-${VERSION}.tar dmenu-${VERSION}
@gzip dmenu-${VERSION}.tar
@rm -rf dmenu-${VERSION}
@@ -47,10 +54,12 @@ dist: clean
install: all
@echo installing executables to ${DESTDIR}${PREFIX}/bin
@mkdir -p ${DESTDIR}${PREFIX}/bin
- @cp -f dmenu dmenu_path dmenu_run stest ${DESTDIR}${PREFIX}/bin
+ @cp -f dmenu dmenu_path dmenu_mru dmenu_run dmenu_do stest ${DESTDIR}${PREFIX}/bin
@chmod 755 ${DESTDIR}${PREFIX}/bin/dmenu
@chmod 755 ${DESTDIR}${PREFIX}/bin/dmenu_path
+ @chmod 755 ${DESTDIR}${PREFIX}/bin/dmenu_mru
@chmod 755 ${DESTDIR}${PREFIX}/bin/dmenu_run
+ @chmod 755 ${DESTDIR}${PREFIX}/bin/dmenu_do
@chmod 755 ${DESTDIR}${PREFIX}/bin/stest
@echo installing manual pages to ${DESTDIR}${MANPREFIX}/man1
@mkdir -p ${DESTDIR}${MANPREFIX}/man1
@@ -63,7 +72,9 @@ uninstall:
@echo removing executables from ${DESTDIR}${PREFIX}/bin
@rm -f ${DESTDIR}${PREFIX}/bin/dmenu
@rm -f ${DESTDIR}${PREFIX}/bin/dmenu_path
+ @rm -f ${DESTDIR}${PREFIX}/bin/dmenu_mru
@rm -f ${DESTDIR}${PREFIX}/bin/dmenu_run
+ @rm -f ${DESTDIR}${PREFIX}/bin/dmenu_do
@rm -f ${DESTDIR}${PREFIX}/bin/stest
@echo removing manual page from ${DESTDIR}${MANPREFIX}/man1
@rm -f ${DESTDIR}${MANPREFIX}/man1/dmenu.1
diff --git a/config.mk b/config.mk
index c0d466b..6d05765 100644
--- a/config.mk
+++ b/config.mk
@@ -19,7 +19,7 @@ LIBS = -L${X11LIB} -lX11 ${XINERAMALIBS}
# flags
CPPFLAGS = -D_BSD_SOURCE -D_POSIX_C_SOURCE=200809L -DVERSION=\"${VERSION}\" ${XINERAMAFLAGS}
CFLAGS = -ansi -pedantic -Wall -Os ${INCS} ${CPPFLAGS}
-LDFLAGS = -s ${LIBS}
+LDFLAGS = ${LIBS}
# compiler and linker
CC = cc
diff --git a/dmenu_do b/dmenu_do
new file mode 100755
index 0000000..6bba84b
--- /dev/null
+++ b/dmenu_do
@@ -0,0 +1,2 @@
+#!/bin/sh
+exe=`dmenu_path | dmenu_mru | dmenu ${1+"$@"}` && exec `dmenu_mru $exe`
diff --git a/dmenu_mru.c b/dmenu_mru.c
new file mode 100644
index 0000000..724186d
--- /dev/null
+++ b/dmenu_mru.c
@@ -0,0 +1,187 @@
+/* See LICENSE file for copyright and license details. */
+#include <dirent.h>
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <sys/stat.h>
+
+#include "mru.h"
+
+
+#define HISTORY ".dmenu_hist"
+#define MAX_HIST 1024
+#define MAX_COMMAND 1024
+
+static void die(const char *s) {
+ fprintf(stderr, "dmenu_mru: %s\n", s);
+ exit(EXIT_FAILURE);
+}
+
+
+/**
+ * Read commands from stdin and return a double linked list of commands.
+ */
+ListEntry* read_commands() {
+ ListEntry* commands = list_create();
+
+ char line[1024];
+ while (fgets(line, 1024, stdin) != NULL) { /* Read everything from stdin */
+ size_t len = strlen(line) - 1; /* Strip out newline character */
+ if (line[len] == '\n')
+ line[len] = '\0';
+ if (len > 0) { /* Build list of commands */
+ list_add(commands, line);
+ }
+ }
+ return commands;
+}
+
+/**
+ * Read command history from file.
+ */
+ListEntry* read_history() {
+ ListEntry* history = list_create();
+ FILE *hist;
+ char line [1024];
+
+ if(!(hist = fopen(HISTORY, "r"))) { /* Open file for reading */
+ return history; /* If history file is not there, just return an empty list */
+ }
+
+ while (fgets(line, sizeof line, hist) != NULL) { /* Read a line from file */
+ size_t len = strlen(line) - 1; /* Strip out newline character */
+ if (line[len] == '\n')
+ line[len] = '\0';
+ if (len > 0) { /* If it's non-empty, */
+ list_add(history, line); /* add to list */
+ }
+ }
+ fclose(hist);
+ return history;
+}
+
+/**
+ * Write commands to history file.
+ */
+void write_history(ListEntry* history) {
+ FILE *hist;
+ int i = 0;
+ ListEntry* e = NULL;
+ if(!(hist = fopen(HISTORY, "w"))) /* Open file for writing */
+ die("failed to write history");
+ /* Write out commands to file Note that we are only going to write out the first MAX_HIST
+ commands */
+ for(e = history->next; e != history && i < MAX_HIST; e = e->next, ++i) {
+ fprintf(hist, "%s\n", e->val);
+ }
+ fclose(hist);
+}
+
+/**
+ * Move command to the top of the history list.
+ */
+void touch_history(ListEntry* history, char* command) {
+ ListEntry* e = NULL;
+ for(e = history->next; e != history; e = e->next) {
+ if (strcmp(command, e->val) == 0) { /* Find the command in history */
+ list_remove(e);
+ break; /* History should be unique, no need to continue looking. */
+ }
+ }
+ list_insert(history, command); /* Add command at the front */
+}
+
+/**
+ * Move command to the top of the MRU history file.
+ */
+void touch_command(char* command) {
+ ListEntry* history = read_history(); /* Read command history from file */
+ touch_history(history, command); /* Move command to the top of history */
+ write_history(history); /* Write command history back to file */
+}
+
+/**
+ * Read commands from stdin and output them in MRU order.
+ */
+void process_commands() {
+ ListEntry* e = NULL;
+
+ ListEntry* history = read_history(); /* Read command history from file */
+ ListEntry* commands = read_commands(); /* Read commands from stdin */
+ HashEntry** commands_hash = hash_create(MAX_HIST, commands); /* Create hashmap for fast lookup */
+
+ /* First output history entries that are present in the commands hash */
+ for(e = history->next; e != history; e = e->next) {
+ HashEntry* he = hash_get(commands_hash, MAX_HIST, e->val);
+ if (he != NULL) {
+ printf("%s\n", he->key);
+ list_remove(he->val); /* Remove entry from the commands list to make sure we don't output it
+ again later */
+ }
+ }
+
+ /* Then output the rest of the commands list */
+ for(e = commands->next; e != commands; e = e->next) {
+ printf("%s\n", e->val);
+ }
+
+ /* Free memory associated with the lists and hash */
+ list_destroy(commands);
+ list_destroy(history);
+ hash_destroy(commands_hash, MAX_HIST);
+}
+
+/**
+ * Join all elements of a string array starting at index seperated by sep and place into s.
+ */
+void join(int argc, char* argv[], int start, char sep, char* s, int size) {
+ int i = 0;
+ int len = 0;
+ for(i = start; i < argc; ++i) {
+ len = strlen(argv[i]); /* Calculate the string length */
+ if (size < len + 1)
+ die("Command too long"); /* Make sure we don't overrun the buffer */
+ strncpy(s, argv[i], len); /* Copy string */
+ s[len] = sep; /* Replace end of string with sep */
+ s += len + 1; /* Move pointer by the amount we added */
+ size -= len + 1; /* Update size remaining */
+ }
+ if (argc - start > 0) {
+ s[-1] = '\0'; /* NULL terminate the string for good measure */
+ }
+}
+
+/**
+ * This application has to modes of operation:
+ *
+ * 1. If no command-line arguments are passed, it will take * a list of via stdin, and move the most
+ * recently used to the front of the list. This is useful when piping the output of dmenu_path
+ * to dmenu. Command history is storied in ~/.dmenu_hist.
+ * 2. If command-line arguments are passed, the application will update the history file
+ * (~/.dmenu_hist) and move or add the command to the front of the file.
+ *
+ * Together these can be used to make dmenu sort most used commands for easy access (see dmenu_do for an example).
+ */
+int main(int argc, char* argv[]) {
+ const char *home;
+ if(!(home = getenv("HOME"))) /* Get user's home dir */
+ die("no $HOME");
+ if(chdir(home) < 0) /* Change to user's home dir so cache files are created here */
+ die("chdir failed");
+
+ if (argc > 1) {
+ /* If a command is passed on the command line, then move this command to the top of the MRU
+ history */
+ char* command = malloc(MAX_COMMAND * sizeof(char));
+ join(argc, argv, 1, ' ', command, MAX_COMMAND); /* Join all parameters into a single string
+ (skip the first because it's the executable
+ name) */
+ touch_command(command); /* Move command to the top of the MRU history */
+ printf(command); /* Output command so it can be executed */
+ } else { /* Othewise, process stdin and sort commands in MRU order */
+ process_commands();
+ }
+ return EXIT_SUCCESS;
+}
diff --git a/mru.c b/mru.c
new file mode 100644
index 0000000..a122d7e
--- /dev/null
+++ b/mru.c
@@ -0,0 +1,131 @@
+/* See LICENSE file for copyright and license details. */
+#include <dirent.h>
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <sys/stat.h>
+#include "mru.h"
+
+/********/
+/* LIST */
+/********/
+
+/**
+ * Free memory for one list entry. Null entries will be silently ignored.
+ */
+void _list_entry_destroy(ListEntry* e) {
+ if (e != NULL) {
+ free(e->val); /* Remember to free the value */
+ free(e);
+ }
+}
+
+ListEntry *list_create() {
+ ListEntry *e = (ListEntry*) malloc(sizeof(ListEntry*)); /* Allocate new entry */
+ e->next = e; /* This is the root entry so next and previous are set to self */
+ e->previous = e;
+ e->val = NULL; /* No value in the root entry, it will remain null */
+ return e;
+}
+
+void list_add(ListEntry *root, char *val) {
+ ListEntry *n = (ListEntry*) malloc(sizeof(ListEntry*)); /* Allocate new entry */
+ n->val = strdup(val); /* Copy and set the value */
+ n->next = root; /* Insert before root which is the last item */
+ n->previous = root->previous;
+ root->previous->next = n;
+ root->previous = n;
+}
+
+ListEntry *list_insert(ListEntry *e, char *val) {
+ ListEntry *n = (ListEntry*) malloc(sizeof(ListEntry*)); /* Allocate new entry */
+ n->val = strdup(val); /* Copy and set the value */
+ n->previous = e;
+ n->next = e->next;
+ e->next = n;
+ return n;
+}
+
+void list_remove(ListEntry *e) {
+ ListEntry *p = e->previous; /* Get previous and next entries */
+ ListEntry *n = e->next;
+ p->next = e->next;
+ n->previous = e->previous;
+ _list_entry_destroy(e); /* Remember to free memory */
+}
+
+void list_destroy(ListEntry *root) {
+ ListEntry* p = NULL; /* Save previous value for each iteration, since we can't free
+ memory for the current entry before moving to the next */
+ ListEntry *e = NULL;
+ for(e = root->next; e != root; p = e, e = e->next) {
+ _list_entry_destroy(p);
+ }
+
+ _list_entry_destroy(p); /* Remember to free the last element */
+}
+
+/*************/
+/* HASHTABLE */
+/*************/
+
+/**
+ * Calculate hash value for the given string.
+ */
+unsigned _hash(char *s, unsigned size) {
+ unsigned hashval;
+ for (hashval = 0; *s != '\0'; ++s)
+ hashval = *s + 31 * hashval;
+ return hashval % size;
+}
+
+HashEntry **hash_create(unsigned size, ListEntry *root) {
+ HashEntry **hashtable = (HashEntry**) malloc(size * sizeof(HashEntry*));
+ ListEntry *e;
+ for(e = root->next; e != root; e = e->next) {
+ hash_put(hashtable, size, e->val, e);
+ }
+ return hashtable;
+}
+
+void hash_destroy(HashEntry **hashtable, unsigned size) {
+ int i;
+ for (i = 0; i < size; ++i) {
+ if (hashtable[i] != NULL) {
+ free(hashtable[i]->key);
+ free(hashtable[i]);
+ }
+ }
+ free(hashtable);
+}
+
+HashEntry *hash_get(HashEntry **hashtable, unsigned size, char *key) {
+ HashEntry *e = NULL;
+ for (e = hashtable[_hash(key, size)]; e != NULL; e = e->next) {
+ if (strcmp(key, e->key) == 0)
+ return e;
+ }
+ return NULL;
+}
+
+HashEntry *hash_put(HashEntry **hashtable, unsigned size, char *key, ListEntry *val) {
+ HashEntry *e = NULL;
+ unsigned h;
+ if (key == NULL) {
+ return NULL; /* Will not add empty keys */
+ }
+ e = hash_get(hashtable, size, key);
+ if (e != NULL) { /* Existing entry found. We'll just update it */
+ e->val = val;
+ } else { /* Entry not found. Need a new one */
+ e = (HashEntry*) malloc(sizeof(*e)); /* Allocate new Entry */
+ e->key = strdup(key); /* Update entry's key */
+ h = _hash(key, size); /* Calculate the hash value */
+ e->next = hashtable[h]; /* Push this entry to the top of the list */
+ e->val = val;
+ hashtable[h] = e; /* Add new entry */
+ }
+ return e;
+}
diff --git a/mru.h b/mru.h
new file mode 100644
index 0000000..fc2e895
--- /dev/null
+++ b/mru.h
@@ -0,0 +1,78 @@
+/* See LICENSE file for copyright and license details. */
+#ifndef MRU_H
+#define MRU_H
+
+/********/
+/* LIST */
+/********/
+
+/**
+ * Linked list entry
+ */
+typedef struct ListEntry {
+ struct ListEntry* next; /* Next entry in chain */
+ struct ListEntry* previous; /* Previous entry in chain */
+ char* val; /* Value */
+} ListEntry;
+
+/**
+ * Create empty list.
+ */
+ListEntry* list_create();
+
+/**
+ * Destroy list and release all memory.
+ */
+void list_destroy(ListEntry* root);
+
+/**
+ * Add entry to double linked list.
+ */
+void list_add(ListEntry* root, char* val);
+
+/**
+ * Insert entry in a double linked list. The entry will be inserted after e. The new entry is
+ * returned.
+ */
+ListEntry* list_insert(ListEntry* e, char* val);
+
+/**
+ * Remove entry from a double linked list. Note that "e"'s memory will be freed.
+ */
+void list_remove(ListEntry* root);
+
+/*************/
+/* HASHTABLE */
+/*************/
+
+/**
+ * Hashtable entry
+ */
+typedef struct HashEntry {
+ struct HashEntry* next; /* Next entry in chain */
+ char* key; /* key */
+ ListEntry* val; /* value */
+} HashEntry;
+
+/**
+ * Create hashtable and add all elements from the linked list.
+ */
+HashEntry** hash_create(unsigned size, ListEntry* head);
+
+/**
+ * Destroy hashtable.
+ */
+void hash_destroy(HashEntry** hashtable, unsigned size);
+
+/**
+ * Get entry.
+ */
+HashEntry* hash_get(HashEntry** hashtable, unsigned size, char* key);
+
+/**
+ * Add entry to hashmap.
+ */
+HashEntry* hash_put(HashEntry** hashtable, unsigned size, char* key, ListEntry* val);
+
+
+#endif
--
1.8.4.4
