Hi there.
I rewrote dmenu_path in C. It's an order of magnitude faster than the
shell script on cache misses and around 2 times faster on cache hits.
I'm attaching the code to this mail. I'd be glad to see it included in
dmenu.
Elmo Todurov
/*
* dmenu_path
* This program dumps all executables in $PATH to stdout.
* It uses the file $HOME/.dmenu_cache as a cache.
*
* This program is released under the X11 license (sometimes known as the MIT
* license), which basically means that you can do whatever you want with it.
*
* Sorry for the hairy code. I didn't know how to make it simpler and still
* as generic. Valgrind claims it's correct and doesn't leak, but I'm sure you
* can find a couple of ways to make it crash.
*
* I'd appreciate, but I don't require, that you mail me any improvements or
* comments on the code.
*
* Elmo Todurov todurov+dm...@gmail.com
* 2010-05-19 09:55
*/
#include <sys/stat.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <malloc.h>
#include <unistd.h>
#include <dirent.h>
#include <assert.h>
static uid_t uid;
static gid_t gid;
static char* cache_path;
static int uptodate(char** paths)
{
struct stat dirstat;
time_t cache_time;
char** dirs;
if (stat(cache_path, &dirstat))
{
if (errno != ENOENT)
{
perror("stat");
}
return 0;
}
cache_time = dirstat.st_mtime;
dirs = paths;
while (*dirs != NULL)
{
if (stat(*dirs, &dirstat))
{
if (errno != ENOENT)
perror("stat");
return 0;
}
if (cache_time < dirstat.st_mtime)
return 0;
dirs++;
}
return 1;
}
static char* get_cache_path()
{
const char* home = getenv("HOME");
char* path = (char*)malloc(strlen(home) + strlen("/.dmenu_cache") + 1);
strcpy(path, home);
strcat(path, "/.dmenu_cache");
return path;
}
static char* get_PATH()
{
const char* path = getenv("PATH");
char* copy_path;
if (path == NULL)
{
perror("getenv");
exit(1);
}
copy_path = strdup(path);
return copy_path;
}
static void split_PATH(char* PATH, char*** dirs_in)
{
char** dirs;
const char* dir = strtok(PATH, ":");
size_t i = 0;
size_t allocated = 10;
dirs = (char**)malloc(sizeof(char*) * allocated);
while (dir != NULL)
{
dirs[i] = (char*)malloc(strlen(dir) + 1);
strcpy(dirs[i], dir);
dir = strtok(NULL, ":");
i++;
if (i == allocated)
{
allocated *= 2;
dirs = (char**)realloc(dirs, allocated * sizeof(char**));
}
}
dirs[i] = NULL;
*dirs_in = dirs;
}
static void free_charpp(char** in)
{
char** ptr = in;
while (*ptr != NULL)
{
free(*ptr);
ptr++;
}
free(in);
}
static void fprint_charpp(char** in, FILE* out)
{
char** ptr = in;
while (*ptr != NULL)
{
fputs(*ptr, out);
fputc('\n', out);
ptr++;
}
}
static size_t count_charpp(char** in)
{
char** ptr = in;
size_t count = 0;
while (*ptr != NULL)
{
count++;
ptr++;
}
return count;
}
static int isexecutable(const char* dir, const char* file)
{
char* fname;
struct stat st;
int ret;
int success;
gid_t* grouplist;
fname = (char*)malloc(strlen(dir) + strlen(file) + 2);
strcpy(fname, dir);
strcat(fname, "/");
strcat(fname, file);
ret = stat(fname, &st);
free(fname);
if (ret != 0)
return 0;
if (!S_ISREG(st.st_mode)) /* this catches regular files and symlinks as well */
return 0;
if ((st.st_uid == uid && (st.st_mode & S_IXUSR) != 0)
|| (st.st_uid != uid && st.st_gid != gid && (st.st_mode & S_IXOTH) != 0))
{
return 1;
}
/* check secondary groups */
if (st.st_mode & S_IXGRP)
{
success = 0;
ret = getgroups(0, 0);
grouplist = (gid_t*)malloc(sizeof(gid_t) * ret);
ret = getgroups(ret, grouplist);
while (ret != 0)
{
ret--;
if (st.st_uid != uid /* for group to match, user must not match. */
&& st.st_gid == grouplist[ret])
{
success = 1;
break;
}
}
free(grouplist);
return success;
}
return 0;
}
static void add(const char* prog, char*** progs)
{
static unsigned progs_allocated = 0;
static unsigned progs_used = 0;
if (progs_used == progs_allocated)
{
progs_allocated = progs_allocated == 0 ? 256 : progs_allocated * 2;
*progs = (char**)realloc(*progs, sizeof(char*) * progs_allocated);
}
if (prog != NULL)
{
(*progs)[progs_used] = (char*)malloc(strlen(prog) + 1);
strcpy((*progs)[progs_used], prog);
progs_used++;
}
else
{
(*progs)[progs_used] = NULL;
}
}
static void refresh_path(const char* path, char*** progs)
{
DIR* dirp = opendir(path);
struct dirent* dp;
if (dirp == NULL)
{
if (errno != ENOENT)
perror("opendir");
return;
}
dp = readdir(dirp);
while (dp != NULL)
{
if (isexecutable(path, dp->d_name))
add(dp->d_name, progs);
dp = readdir(dirp);
}
closedir(dirp);
}
static int compare(const void* a, const void* b)
{
return strcmp(*(const char**)a, *(const char**)b);
}
static void sort(char*** progs)
{
qsort(*progs, count_charpp(*progs), sizeof(*progs), compare);
}
static void uniq(char*** progs)
{
char** progs_new = (char**)malloc(sizeof(char*) * (count_charpp(*progs) + 1));
char** ptr_1 = *progs;
char** ptr_2 = ptr_1 + 1;
unsigned long i = 0;;
while (*ptr_1 != NULL)
{
while (*ptr_2 != NULL && strcmp(*ptr_1, *ptr_2) == 0)
{
free(*ptr_2);
ptr_2++;
}
progs_new[i] = *ptr_1;
i++;
ptr_1 = ptr_2;
ptr_2++;
}
progs_new[i] = NULL;
free(*progs);
*progs = progs_new;
}
static void refresh(char** paths)
{
char** progs = NULL;
FILE* out;
while (*paths != NULL)
{
refresh_path(*paths, &progs);
paths++;
}
add(NULL, &progs);
out = fopen(cache_path, "w");
if (out == NULL)
{
perror("fopen");
exit(1);
}
sort(&progs);
uniq(&progs);
fprint_charpp(progs, out);
fprint_charpp(progs, stdout);
free_charpp(progs);
fclose(out);
}
static void cat()
{
FILE* cache = fopen(cache_path, "r");
char buf[4096];
struct stat cachestat;
size_t still_unread;
size_t chunk;
if (cache == NULL)
{
perror("fopen cache");
exit(1);
}
if (stat(cache_path, &cachestat))
{
perror("stat");
exit(1);
}
still_unread = cachestat.st_size;
while (still_unread > 0)
{
chunk = fread(buf, 1, 4096, cache);
still_unread -= chunk;
fwrite(buf, 1, chunk, stdout);
}
fclose(cache);
}
int main(int argc, char *argv[])
{
char* PATH = get_PATH();
char** paths = NULL;
uid = getuid();
gid = getgid();
if (uid == 0 || gid == 0)
{
puts("I refuse to run as root!");
return 1;
}
cache_path = get_cache_path();
split_PATH(PATH, &paths);
free(PATH);
sort(&paths);
uniq(&paths);
if ((argc == 2 && strcmp(argv[1], "--force") == 0)
|| !uptodate(paths))
refresh(paths);
else
cat();
free_charpp(paths);
free(cache_path);
return 0;
}
