busybox/libbb/inode_hash.c

/* vi: set sw=4 ts=4: */
/*
 * Utility routines.
 *
 * Copyright (C) many different people.
 * If you wrote this, please acknowledge your work.
 *
 * Licensed under GPLv2 or later, see file LICENSE in this tarball for details.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "libbb.h"

#define HASH_SIZE	311		/* Should be prime */
#define hash_inode(i)	((i) % HASH_SIZE)

typedef struct ino_dev_hash_bucket_struct {
  struct ino_dev_hash_bucket_struct *next;
  ino_t ino;
  dev_t dev;
  char name[1];
} ino_dev_hashtable_bucket_t;

static ino_dev_hashtable_bucket_t *ino_dev_hashtable[HASH_SIZE];

/*
 * Return 1 if statbuf->st_ino && statbuf->st_dev are recorded in
 * `ino_dev_hashtable', else return 0
 *
 * If NAME is a non-NULL pointer to a character pointer, and there is
 * a match, then set *NAME to the value of the name slot in that
 * bucket.
 */
int is_in_ino_dev_hashtable(const struct stat *statbuf, char **name)
{
	ino_dev_hashtable_bucket_t *bucket;

	bucket = ino_dev_hashtable[hash_inode(statbuf->st_ino)];
	while (bucket != NULL) {
	  if ((bucket->ino == statbuf->st_ino) &&
		  (bucket->dev == statbuf->st_dev))
	  {
		if (name) *name = bucket->name;
		return 1;
	  }
	  bucket = bucket->next;
	}
	return 0;
}

/* Add statbuf to statbuf hash table */
void add_to_ino_dev_hashtable(const struct stat *statbuf, const char *name)
{
	int i;
	size_t s;
	ino_dev_hashtable_bucket_t *bucket;

	i = hash_inode(statbuf->st_ino);
	s = name ? strlen(name) : 0;
	bucket = xmalloc(sizeof(ino_dev_hashtable_bucket_t) + s);
	bucket->ino = statbuf->st_ino;
	bucket->dev = statbuf->st_dev;
	if (name)
		strcpy(bucket->name, name);
	else
		bucket->name[0] = '\0';
	bucket->next = ino_dev_hashtable[i];
	ino_dev_hashtable[i] = bucket;
}

#ifdef CONFIG_FEATURE_CLEAN_UP
/* Clear statbuf hash table */
void reset_ino_dev_hashtable(void)
{
	int i;
	ino_dev_hashtable_bucket_t *bucket;

	for (i = 0; i < HASH_SIZE; i++) {
		while (ino_dev_hashtable[i] != NULL) {
			bucket = ino_dev_hashtable[i]->next;
			free(ino_dev_hashtable[i]);
			ino_dev_hashtable[i] = bucket;
		}
	}
}
#endif
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 tarball for details.
9	*/
10
11	#include <stdio.h>
12	#include <stdlib.h>
13	#include <string.h>
14	#include "libbb.h"
15
16	#define HASH_SIZE 311 /* Should be prime */
17	#define hash_inode(i) ((i) % HASH_SIZE)
18
19	typedef struct ino_dev_hash_bucket_struct {
20	struct ino_dev_hash_bucket_struct *next;
21	ino_t ino;
22	dev_t dev;
23	char name[1];
24	} ino_dev_hashtable_bucket_t;
25
26	static ino_dev_hashtable_bucket_t *ino_dev_hashtable[HASH_SIZE];
27
28	/*
29	* Return 1 if statbuf->st_ino && statbuf->st_dev are recorded in
30	* `ino_dev_hashtable', else return 0
31	*
32	* If NAME is a non-NULL pointer to a character pointer, and there is
33	* a match, then set *NAME to the value of the name slot in that
34	* bucket.
35	*/
36	int is_in_ino_dev_hashtable(const struct stat statbuf, char *name)
37	{
38	ino_dev_hashtable_bucket_t *bucket;
39
40	bucket = ino_dev_hashtable[hash_inode(statbuf->st_ino)];
41	while (bucket != NULL) {
42	if ((bucket->ino == statbuf->st_ino) &&
43	(bucket->dev == statbuf->st_dev))
44	{
45	if (name) *name = bucket->name;
46	return 1;
47	}
48	bucket = bucket->next;
49	}
50	return 0;
51	}
52
53	/* Add statbuf to statbuf hash table */
54	void add_to_ino_dev_hashtable(const struct stat statbuf, const char name)
55	{
56	int i;
57	size_t s;
58	ino_dev_hashtable_bucket_t *bucket;
59
60	i = hash_inode(statbuf->st_ino);
61	s = name ? strlen(name) : 0;
62	bucket = xmalloc(sizeof(ino_dev_hashtable_bucket_t) + s);
63	bucket->ino = statbuf->st_ino;
64	bucket->dev = statbuf->st_dev;
65	if (name)
66	strcpy(bucket->name, name);
67	else
68	bucket->name[0] = '\0';
69	bucket->next = ino_dev_hashtable[i];
70	ino_dev_hashtable[i] = bucket;
71	}
72
73	#ifdef CONFIG_FEATURE_CLEAN_UP
74	/* Clear statbuf hash table */
75	void reset_ino_dev_hashtable(void)
76	{
77	int i;
78	ino_dev_hashtable_bucket_t *bucket;
79
80	for (i = 0; i < HASH_SIZE; i++) {
81	while (ino_dev_hashtable[i] != NULL) {
82	bucket = ino_dev_hashtable[i]->next;
83	free(ino_dev_hashtable[i]);
84	ino_dev_hashtable[i] = bucket;
85	}
86	}
87	}
88	#endif