home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume15 / vtree / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-05-23  |  4.2 KB  |  145 lines
  1. /* hash.c
  2.   
  3.    SCCS ID    @(#)hash.c    1.6    7/9/87
  4.   
  5.  * Hash table routines for AGEF.  These routines keep the program from
  6.  * counting the same inode twice.  This can happen in the case of a
  7.  * file with multiple links, as in a news article posted to several
  8.  * groups.  The use of a hashing scheme was suggested by Anders
  9.  * Andersson of Uppsala University, Sweden.  (enea!kuling!andersa) 
  10.  */
  11.  
  12. /* hash.c change history:
  13.  28 March 1987        David S. Hayes (merlin@hqda-ai.UUCP)
  14.     Initial version.
  15. */
  16.  
  17. #include <stdio.h>
  18. #include <sys/types.h>
  19. #include "hash.h"
  20.  
  21.  
  22. static struct htable *tables[TABLES];
  23.  
  24. /* These are for statistical use later on. */
  25. static int      hs_tables = 0,    /* number of tables allocated */
  26.                 hs_duplicates = 0,    /* number of OLD's returned */
  27.                 hs_buckets = 0,    /* number of buckets allocated */
  28.                 hs_extensions = 0,    /* number of bucket extensions */
  29.                 hs_searches = 0,/* number of searches */
  30.                 hs_compares = 0,/* total key comparisons */
  31.                 hs_longsearch = 0;    /* longest search */
  32.  
  33.  
  34.  /*
  35.   * This routine takes in a device/inode, and tells whether it's been
  36.   * entered in the table before.  If it hasn't, then the inode is added
  37.   * to the table.  A separate table is maintained for each major device
  38.   * number, so separate file systems each have their own table. 
  39.   */
  40.  
  41. h_enter(dev, ino)
  42.     dev_t           dev;
  43.     ino_t           ino;
  44. {
  45.     static struct htable *tablep = (struct htable *) 0;
  46.     register struct hbucket *bucketp;
  47.     register ino_t *keyp;
  48.     int             i;
  49.  
  50.     hs_searches++;        /* stat, total number of calls */
  51.  
  52.     /*
  53.      * Find the hash table for this device. We keep the table pointer
  54.      * around between calls to h_enter, so that we don't have to locate
  55.      * the correct hash table every time we're called.  I don't expect
  56.      * to jump from device to device very often. 
  57.      */
  58.     if (!tablep || tablep->device != dev) {
  59.     for (i = 0; tables[i] && tables[i]->device != dev;)
  60.         i++;
  61.     if (!tables[i]) {
  62.         tables[i] = (struct htable *) malloc(sizeof(struct htable));
  63.         if (tables[i] == NULL) {
  64.         perror("can't malloc hash table");
  65.         return NEW;
  66.         };
  67. /*        bzero(tables[i], sizeof(struct htable)); */
  68.         memset((char *) tables[i], '\0', sizeof (struct htable));
  69.         tables[i]->device = dev;
  70.         hs_tables++;    /* stat, new table allocated */
  71.     };
  72.     tablep = tables[i];
  73.     };
  74.  
  75.     /* Which bucket is this inode assigned to? */
  76.     bucketp = &tablep->buckets[ino % BUCKETS];
  77.  
  78.     /*
  79.      * Now check the key list for that bucket.  Just a simple linear
  80.      * search. 
  81.      */
  82.     keyp = bucketp->keys;
  83.     for (i = 0; i < bucketp->filled && *keyp != ino;)
  84.     i++, keyp++;
  85.  
  86.     hs_compares += i + 1;    /* stat, total key comparisons */
  87.  
  88.     if (i && *keyp == ino) {
  89.     hs_duplicates++;    /* stat, duplicate inodes */
  90.     return OLD;
  91.     };
  92.  
  93.     /* Longest search.  Only new entries could be the longest. */
  94.     if (bucketp->filled >= hs_longsearch)
  95.     hs_longsearch = bucketp->filled + 1;
  96.  
  97.     /* Make room at the end of the bucket's key list. */
  98.     if (bucketp->filled == bucketp->length) {
  99.     /* No room, extend the key list. */
  100.     if (!bucketp->length) {
  101.         bucketp->keys = (ino_t *) calloc(EXTEND, sizeof(ino_t));
  102.         if (bucketp->keys == NULL) {
  103.         perror("can't malloc hash bucket");
  104.         return NEW;
  105.         };
  106.         hs_buckets++;
  107.     } else {
  108.         bucketp->keys = (ino_t *)
  109.         realloc(bucketp->keys,
  110.             (EXTEND + bucketp->length) * sizeof(ino_t));
  111.         if (bucketp->keys == NULL) {
  112.         perror("can't extend hash bucket");
  113.         return NEW;
  114.         };
  115.         hs_extensions++;
  116.     };
  117.     bucketp->length += EXTEND;
  118.     };
  119.  
  120.     bucketp->keys[++(bucketp->filled)] = ino;
  121.     return NEW;
  122. }
  123.  
  124.  
  125.  /* Buffer statistics functions.  Print 'em out. */
  126.  
  127. #ifdef HSTATS
  128. void
  129. h_stats()
  130. {
  131.     fprintf(stderr, "\nHash table management statistics:\n");
  132.     fprintf(stderr, "  Tables allocated: %d\n", hs_tables);
  133.     fprintf(stderr, "  Buckets used: %d\n", hs_buckets);
  134.     fprintf(stderr, "  Bucket extensions: %d\n\n", hs_extensions);
  135.     fprintf(stderr, "  Total searches: %d\n", hs_searches);
  136.     fprintf(stderr, "  Duplicate keys found: %d\n", hs_duplicates);
  137.     if (hs_searches)
  138.     fprintf(stderr, "  Average key search: %d\n",
  139.         hs_compares / hs_searches);
  140.     fprintf(stderr, "  Longest key search: %d\n", hs_longsearch);
  141.     fflush(stderr);
  142. }
  143.  
  144. #endif
  145.