1 /* vi: set sw=4 ts=4: */
2 /*
3  * Utility routines.
4  *
5  * Copyright (C) many different people.
6  * If you wrote this, please acknowledge your work.
7  *
8  * Licensed under GPLv2 or later, see file LICENSE in this source tree.
9  */
10 #include "libbb.h"
11 
12 typedef struct ino_dev_hash_bucket_struct {
13 	ino_t ino;
14 	dev_t dev;
15 	/*
16 	 * Above fields can be 64-bit, while pointer may be 32-bit.
17 	 * Putting "next" field here may reduce size of this struct:
18 	 */
19 	struct ino_dev_hash_bucket_struct *next;
20 	/*
21 	 * Reportedly, on cramfs a file and a dir can have same ino.
22 	 * Need to also remember "file/dir" bit:
23 	 */
24 	char isdir; /* bool */
25 	char name[1];
26 } ino_dev_hashtable_bucket_t;
27 
28 #define HASH_SIZE      311u   /* Should be prime */
29 #define hash_inode(i)  ((unsigned)(i) % HASH_SIZE)
30 
31 /* array of [HASH_SIZE] elements */
32 static ino_dev_hashtable_bucket_t **ino_dev_hashtable;
33 
34 /*
35  * Return name if statbuf->st_ino && statbuf->st_dev are recorded in
36  * ino_dev_hashtable, else return NULL
37  */
is_in_ino_dev_hashtable(const struct stat * statbuf)38 char* FAST_FUNC is_in_ino_dev_hashtable(const struct stat *statbuf)
39 {
40 	ino_dev_hashtable_bucket_t *bucket;
41 
42 	if (!ino_dev_hashtable)
43 		return NULL;
44 
45 	bucket = ino_dev_hashtable[hash_inode(statbuf->st_ino)];
46 	while (bucket != NULL) {
47 		if ((bucket->ino == statbuf->st_ino)
48 		 && (bucket->dev == statbuf->st_dev)
49 		 && (bucket->isdir == !!S_ISDIR(statbuf->st_mode))
50 		) {
51 			return bucket->name;
52 		}
53 		bucket = bucket->next;
54 	}
55 	return NULL;
56 }
57 
58 /* Add statbuf to statbuf hash table */
add_to_ino_dev_hashtable(const struct stat * statbuf,const char * name)59 void FAST_FUNC add_to_ino_dev_hashtable(const struct stat *statbuf, const char *name)
60 {
61 	int i;
62 	ino_dev_hashtable_bucket_t *bucket;
63 
64 	if (!name)
65 		name = "";
66 	bucket = xmalloc(sizeof(ino_dev_hashtable_bucket_t) + strlen(name));
67 	bucket->ino = statbuf->st_ino;
68 	bucket->dev = statbuf->st_dev;
69 	bucket->isdir = !!S_ISDIR(statbuf->st_mode);
70 	strcpy(bucket->name, name);
71 
72 	if (!ino_dev_hashtable)
73 		ino_dev_hashtable = xzalloc(HASH_SIZE * sizeof(*ino_dev_hashtable));
74 
75 	i = hash_inode(statbuf->st_ino);
76 	bucket->next = ino_dev_hashtable[i];
77 	ino_dev_hashtable[i] = bucket;
78 }
79 
80 #if ENABLE_FEATURE_CLEAN_UP
81 /* Clear statbuf hash table */
reset_ino_dev_hashtable(void)82 void FAST_FUNC reset_ino_dev_hashtable(void)
83 {
84 	int i;
85 	ino_dev_hashtable_bucket_t *bucket, *next;
86 
87 	if (!ino_dev_hashtable)
88 		return;
89 
90 	for (i = 0; i < HASH_SIZE; i++) {
91 		bucket = ino_dev_hashtable[i];
92 
93 		while (bucket != NULL) {
94 			next = bucket->next;
95 			free(bucket);
96 			bucket = next;
97 		}
98 	}
99 	free(ino_dev_hashtable);
100 	ino_dev_hashtable = NULL;
101 }
102 #endif
103