1// SPDX-License-Identifier: GPL-2.0-only
2/* Manage a cache of file names' existence */
3#include <stdlib.h>
4#include <unistd.h>
5#include <string.h>
6#include <linux/list.h>
7#include "fncache.h"
8
9struct fncache {
10	struct hlist_node nd;
11	bool res;
12	char name[];
13};
14
15#define FNHSIZE 61
16
17static struct hlist_head fncache_hash[FNHSIZE];
18
19unsigned shash(const unsigned char *s)
20{
21	unsigned h = 0;
22	while (*s)
23		h = 65599 * h + *s++;
24	return h ^ (h >> 16);
25}
26
27static bool lookup_fncache(const char *name, bool *res)
28{
29	int h = shash((const unsigned char *)name) % FNHSIZE;
30	struct fncache *n;
31
32	hlist_for_each_entry(n, &fncache_hash[h], nd) {
33		if (!strcmp(n->name, name)) {
34			*res = n->res;
35			return true;
36		}
37	}
38	return false;
39}
40
41static void update_fncache(const char *name, bool res)
42{
43	struct fncache *n = malloc(sizeof(struct fncache) + strlen(name) + 1);
44	int h = shash((const unsigned char *)name) % FNHSIZE;
45
46	if (!n)
47		return;
48	strcpy(n->name, name);
49	n->res = res;
50	hlist_add_head(&n->nd, &fncache_hash[h]);
51}
52
53/* No LRU, only use when bounded in some other way. */
54bool file_available(const char *name)
55{
56	bool res;
57
58	if (lookup_fncache(name, &res))
59		return res;
60	res = access(name, R_OK) == 0;
61	update_fncache(name, res);
62	return res;
63}
64