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