home *** CD-ROM | disk | FTP | other *** search
/ Amiga MA Magazine 1998 #6 / amigamamagazinepolishissue1998.iso / cdrom / mkisofs.105 / source / hash.c < prev    next >
C/C++ Source or Header  |  1977-12-31  |  5KB  |  179 lines
  1. #include "amigadef.h"
  2. /*
  3.  * File hash.c - generate hash tables for iso9660 filesystem.
  4.  
  5.    Written by Eric Youngdale (1993).
  6.  
  7.    Copyright 1993 Yggdrasil Computing, Incorporated
  8.  
  9.    This program is free software; you can redistribute it and/or modify
  10.    it under the terms of the GNU General Public License as published by
  11.    the Free Software Foundation; either version 2, or (at your option)
  12.    any later version.
  13.  
  14.    This program is distributed in the hope that it will be useful,
  15.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  16.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17.    GNU General Public License for more details.
  18.  
  19.    You should have received a copy of the GNU General Public License
  20.    along with this program; if not, write to the Free Software
  21.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  22.  
  23. #include <stdlib.h>
  24. #include "mkisofs.h"
  25.  
  26. #define NR_HASH 1024
  27.  
  28. #define HASH_FN(DEV, INO) ((DEV + INO + (INO >> 2) + (INO << 8)) % NR_HASH)
  29.  
  30. static struct file_hash * hash_table[NR_HASH] = {0,};
  31.  
  32. void FDECL1(add_hash, struct directory_entry *, spnt){
  33.   struct file_hash * s_hash;
  34.   unsigned int hash_number;
  35.  
  36.   if(spnt->size == 0 || spnt->starting_block == 0) 
  37.     if(spnt->size != 0 || spnt->starting_block != 0) {
  38.       fprintf(stderr,"Non zero-length file assigned zero extent.\n");
  39.       exit(1);
  40.     };
  41.  
  42.   if (spnt->dev == (dev_t) UNCACHED_DEVICE || spnt->inode == UNCACHED_INODE) return;
  43.   hash_number = HASH_FN((unsigned int) spnt->dev, (unsigned int) spnt->inode);
  44.  
  45. #if 0
  46.   if (verbose) fprintf(stderr,"%s ",spnt->name);
  47. #endif
  48.   s_hash = (struct file_hash *) e_malloc(sizeof(struct file_hash));
  49.   s_hash->next = hash_table[hash_number];
  50.   s_hash->inode = spnt->inode;
  51.   s_hash->dev = spnt->dev;
  52.   s_hash->starting_block = spnt->starting_block;
  53.   s_hash->size = spnt->size;
  54.   hash_table[hash_number] = s_hash;
  55. }
  56.  
  57. struct file_hash * FDECL2(find_hash, dev_t, dev, ino_t, inode){
  58.   unsigned int hash_number;
  59.   struct file_hash * spnt;
  60.   hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
  61.   if (dev == (dev_t) UNCACHED_DEVICE || inode == UNCACHED_INODE) return NULL;
  62.  
  63.   spnt = hash_table[hash_number];
  64.   while(spnt){
  65.     if(spnt->inode == inode && spnt->dev == dev) return spnt;
  66.     spnt = spnt->next;
  67.   };
  68.   return NULL;
  69. }
  70.  
  71.  
  72. static struct file_hash * directory_hash_table[NR_HASH] = {0,};
  73.  
  74. void FDECL2(add_directory_hash, dev_t, dev, ino_t, inode){
  75.   struct file_hash * s_hash;
  76.   unsigned int hash_number;
  77.  
  78.   if (dev == (dev_t) UNCACHED_DEVICE || inode == UNCACHED_INODE) return;
  79.   hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
  80.  
  81.   s_hash = (struct file_hash *) e_malloc(sizeof(struct file_hash));
  82.   s_hash->next = directory_hash_table[hash_number];
  83.   s_hash->inode = inode;
  84.   s_hash->dev = dev;
  85.   directory_hash_table[hash_number] = s_hash;
  86. }
  87.  
  88. struct file_hash * FDECL2(find_directory_hash, dev_t, dev, ino_t, inode){
  89.   unsigned int hash_number;
  90.   struct file_hash * spnt;
  91.   hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
  92.   if (dev == (dev_t) UNCACHED_DEVICE || inode == UNCACHED_INODE) return NULL;
  93.  
  94.   spnt = directory_hash_table[hash_number];
  95.   while(spnt){
  96.     if(spnt->inode == inode && spnt->dev == dev) return spnt;
  97.     spnt = spnt->next;
  98.   };
  99.   return NULL;
  100. }
  101.  
  102. struct  name_hash{
  103.     struct name_hash * next;
  104.     struct directory_entry * de;
  105. };
  106.  
  107. #define NR_NAME_HASH 128
  108.  
  109. static struct name_hash * name_hash_table[NR_NAME_HASH] = {0,};
  110.  
  111. static  unsigned int FDECL1(name_hash, const char *, name){
  112.     unsigned int hash = 0;
  113.     const char * p;
  114.  
  115.     p = name;
  116.  
  117.     while (*p) hash = (hash << 15) + (hash << 3) + (hash >> 3) + *p++;
  118.     return hash % NR_NAME_HASH;
  119.  
  120. }
  121.  
  122.  
  123. void FDECL1(add_file_hash, struct directory_entry *, de){
  124.     struct name_hash  * new;
  125.     int hash;
  126.  
  127.     new = (struct  name_hash *) e_malloc(sizeof(struct name_hash));
  128.     new->de = de;
  129.     new->next = NULL;
  130.     hash = name_hash(de->isorec.name);
  131.  
  132.     /* Now insert into the hash table */
  133.     new->next = name_hash_table[hash];
  134.     name_hash_table[hash] = new;
  135. }
  136.  
  137. struct directory_entry * FDECL1(find_file_hash, char *, name){
  138.     struct name_hash  * nh;
  139.  
  140.     for(nh = name_hash_table[name_hash(name)]; nh; nh = nh->next)
  141.         if(strcmp(nh->de->isorec.name, name) == 0) return nh->de;
  142.     return NULL;
  143. }
  144.  
  145. int FDECL1(delete_file_hash, struct directory_entry *, de){
  146.     struct name_hash  * nh, *prev;
  147.     int hash;
  148.  
  149.     prev = NULL;
  150.     hash = name_hash(de->isorec.name);
  151.     for(nh = name_hash_table[hash]; nh; nh = nh->next) {
  152.         if(nh->de == de) break;
  153.         prev = nh;
  154.     };
  155.     if(!nh) return 1;
  156.     if(!prev)
  157.         name_hash_table[hash] = nh->next;
  158.     else
  159.         prev->next = nh->next;
  160.     free(nh);
  161.     return 0;
  162. }
  163.  
  164. void flush_file_hash(){
  165.     struct name_hash  * nh, *nh1;
  166.     int i;
  167.  
  168.     for(i=0; i<NR_NAME_HASH; i++) {
  169.         nh = name_hash_table[i];
  170.         while(nh) {
  171.             nh1 =  nh->next;
  172.             free(nh);
  173.             nh = nh1;
  174.         };
  175.         name_hash_table[i] =  NULL;
  176.         
  177.     };
  178. }
  179.