home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume18 / vtree / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-04-19  |  4.4 KB  |  150 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. static struct htable *tables[TABLES];
  22. extern char *malloc();        /* added 6/17/88 */
  23. extern char *realloc();        /* added 6/17/88 */
  24. extern char *calloc();        /* added 6/17/88 */
  25.  
  26. /* These are for statistical use later on. */
  27. static int      hs_tables = 0,    /* number of tables allocated */
  28.                 hs_duplicates = 0,    /* number of OLD's returned */
  29.                 hs_buckets = 0,    /* number of buckets allocated */
  30.                 hs_extensions = 0,    /* number of bucket extensions */
  31.                 hs_searches = 0,/* number of searches */
  32.                 hs_compares = 0,/* total key comparisons */
  33.                 hs_longsearch = 0;    /* longest search */
  34.  
  35.  
  36.  /*
  37.   * This routine takes in a device/inode, and tells whether it's been
  38.   * entered in the table before.  If it hasn't, then the inode is added
  39.   * to the table.  A separate table is maintained for each major device
  40.   * number, so separate file systems each have their own table. 
  41.   */
  42.  
  43. h_enter(dev, ino)
  44.     dev_t           dev;
  45.     ino_t           ino;
  46. {
  47.     static struct htable *tablep = (struct htable *) 0;
  48.     register struct hbucket *bucketp;
  49.     register ino_t *keyp;
  50.     int             i;
  51.  
  52.     hs_searches++;        /* stat, total number of calls */
  53.  
  54.     /*
  55.      * Find the hash table for this device. We keep the table pointer
  56.      * around between calls to h_enter, so that we don't have to locate
  57.      * the correct hash table every time we're called.  I don't expect
  58.      * to jump from device to device very often. 
  59.      */
  60.     if (!tablep || tablep->device != dev) {
  61.     for (i = 0; tables[i] && tables[i]->device != dev;)
  62.         i++;
  63.     if (!tables[i]) {
  64.         tables[i] = (struct htable *)  malloc(sizeof(struct htable));
  65.         if (tables[i] == NULL) {
  66.         perror("can't malloc hash table");
  67.         return NEW;
  68.         };
  69. #ifdef BSD
  70.         bzero(tables[i], sizeof(struct htable)); 
  71. #else
  72.         memset((char *) tables[i], '\0', sizeof (struct htable));
  73. #endif
  74.         tables[i]->device = dev;
  75.         hs_tables++;    /* stat, new table allocated */
  76.     };
  77.     tablep = tables[i];
  78.     };
  79.  
  80.     /* Which bucket is this inode assigned to? */
  81.     bucketp = &tablep->buckets[ino % BUCKETS];
  82.  
  83.     /*
  84.      * Now check the key list for that bucket.  Just a simple linear
  85.      * search. 
  86.      */
  87.     keyp = bucketp->keys;
  88.     for (i = 0; i < bucketp->filled && *keyp != ino;)
  89.     i++, keyp++;
  90.  
  91.     hs_compares += i + 1;    /* stat, total key comparisons */
  92.  
  93.     if (i && *keyp == ino) {
  94.     hs_duplicates++;    /* stat, duplicate inodes */
  95.     return OLD;
  96.     };
  97.  
  98.     /* Longest search.  Only new entries could be the longest. */
  99.     if (bucketp->filled >= hs_longsearch)
  100.     hs_longsearch = bucketp->filled + 1;
  101.  
  102.     /* Make room at the end of the bucket's key list. */
  103.     if (bucketp->filled == bucketp->length) {
  104.     /* No room, extend the key list. */
  105.     if (!bucketp->length) {
  106.         bucketp->keys = (ino_t *) calloc(EXTEND, sizeof(ino_t));
  107.         if (bucketp->keys == NULL) {
  108.         perror("can't malloc hash bucket");
  109.         return NEW;
  110.         };
  111.         hs_buckets++;
  112.     } else {
  113.         bucketp->keys = (ino_t *)
  114.         realloc(bucketp->keys,
  115.             (EXTEND + bucketp->length) * sizeof(ino_t));
  116.         if (bucketp->keys == NULL) {
  117.         perror("can't extend hash bucket");
  118.         return NEW;
  119.         };
  120.         hs_extensions++;
  121.     };
  122.     bucketp->length += EXTEND;
  123.     };
  124.  
  125.     bucketp->keys[++(bucketp->filled)] = ino;
  126.     return NEW;
  127. }
  128.  
  129.  
  130.  /* Buffer statistics functions.  Print 'em out. */
  131.  
  132. #ifdef HSTATS
  133. void
  134. h_stats()
  135. {
  136.     fprintf(stderr, "\nHash table management statistics:\n");
  137.     fprintf(stderr, "  Tables allocated: %d\n", hs_tables);
  138.     fprintf(stderr, "  Buckets used: %d\n", hs_buckets);
  139.     fprintf(stderr, "  Bucket extensions: %d\n\n", hs_extensions);
  140.     fprintf(stderr, "  Total searches: %d\n", hs_searches);
  141.     fprintf(stderr, "  Duplicate keys found: %d\n", hs_duplicates);
  142.     if (hs_searches)
  143.     fprintf(stderr, "  Average key search: %d\n",
  144.         hs_compares / hs_searches);
  145.     fprintf(stderr, "  Longest key search: %d\n", hs_longsearch);
  146.     fflush(stderr);
  147. }
  148.  
  149. #endif
  150.