release/src/router/busybox/libbb/inode_hash.c

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