cde/lib/DtSearch/isduprec.c

   1 /*
   2  *   COMPONENT_NAME: austext
   3  *
   4  *   FUNCTIONS: dump_hashtab
   5  *              is_duprec
   6  *              main
   7  *
   8  *   ORIGINS: 27
   9  *
  10  *
  11  *   (C) COPYRIGHT International Business Machines Corp. 1993,1995
  12  *   All Rights Reserved
  13  *   Licensed Materials - Property of IBM
  14  *   US Government Users Restricted Rights - Use, duplication or
  15  *   disclosure restricted by GSA ADP Schedule Contract with IBM Corp.
  16  */
  17 /******************* ISDUPREC.C *******************
  18  * $XConsortium: isduprec.c /main/5 1996/05/07 13:37:35 drk $
  19  * June 1993.
  20  * Is_duprec() returns 0 (FALSE) for every record id it is passed
  21  * unless one is passed that duplicates a previous one,
  22  * in which case it returns 1 (TRUE).
  23  * It ensures that duplicate record ids in an .fzk file
  24  * are not processed by either ravel or borodin.
  25  * It does it by storing each recid into a hash table and
  26  * searching the table before storing a new recid.
  27  * Returns 2 on errors (malloc out of space, etc);
  28  *
  29  * Global 'duprec_hashsize' can be changed to any rational value
  30  * for a hash table size (say 1000 to 30,000) prior to the first call
  31  * of is_duprec().  It should be roughly => to the total number of
  32  * different record ids expected to be passed to is_duprec().
  33  * If initialized to 0 before the first call, that will disable
  34  * duplicate checking, i.e. is_duprec() will allocate no memory
  35  * and always return 0.
  36  *
  37  * $Log$
  38  * Revision 2.2  1995/10/25  17:22:48  miker
  39  * Added prolog.
  40  *
  41  * Revision 2.1  1995/09/22  20:56:44  miker
  42  * Freeze DtSearch 0.1, AusText 2.1.8
  43  *
  44  * Revision 1.3  1995/09/05  18:11:45  miker
  45  * Minor changes so ansi c compilers won't whine.
  46  */
  47 #include <stdlib.h>
  48 #include <string.h>
  49
  50 #ifdef TEST
  51 #include <stdio.h>
  52 #include <errno.h>
  53 #endif
  54
  55 #define PROGNAME        "ISDUPREC"
  56 #define HASHSIZE        3000L
  57 #define NOT_A_DUP       0
  58 #define IS_A_DUP        1
  59 #define OUT_OF_MEM      2
  60
  61 unsigned long   duprec_hashsize = HASHSIZE;
  62
  63 /************************************************/
  64 /*                                              */
  65 /*                  HASHNODE                    */
  66 /*                                              */
  67 /************************************************/
  68 /* The hash table is a HASHSIZE array of pointers to these structures.
  69  * Each pointer is initialized to NULL.
  70  * Additions are handled by filling in a HASHNODE pointed to
  71  * by the table pointer.  The 'recid' is NOT a char array of length
  72  * 1, but a string whose length varies depending on the actual
  73  * length of the passed record id.  Each hashnode is malloced
  74  * for exactly the right length.  Collisions are handled by linking
  75  * additional nodes off of the original one.
  76  */
  77 typedef struct hash_tag {
  78     struct hash_tag *link;
  79     char            recid[2];   /* actual array size varies */
  80 }               HASHNODE;
  81
  82
  83 #ifdef TEST
  84 /************************************************/
  85 /*                                              */
  86 /*                dump_hashtab()                */
  87 /*                                              */
  88 /************************************************/
  89 /* For debugging, prints out all recids in hashtab, skipping empty bkts */
  90 static void     dump_hashtab (HASHNODE ** hashtab)
  91 {
  92     HASHNODE       *hp, **hpp;
  93     int             i;
  94     printf (PROGNAME "67 dump_hashtab(%p):\n", hashtab);
  95     for (i = 0, hpp = hashtab; i < duprec_hashsize; i++, hpp++) {
  96         if (*hpp) {
  97             printf ("  %4d:", i);
  98             fflush (stdout);
  99             for (hp = *hpp; hp != NULL; hp = hp->link)
 100                 printf (" '%s'", hp->recid);
 101             putchar ('\n');
 102             fflush (stdout);
 103         }
 104     }
 105     return;
 106 }  /* dump_hashtab() */
 107
 108 #endif  /* TEST */
 109
 110
 111 /************************************************/
 112 /*                                              */
 113 /*                 is_duprec()                  */
 114 /*                                              */
 115 /************************************************/
 116 /* Normal return is 0 indicating that passed record id is unique.
 117  * Also immediately returns 0 if duplicate checking has been
 118  * turned off by setting global 'duprec_hashsize' to zero.
 119  * Returns 1 if record id is a duplicate.
 120  * Returns 2 if out of memory.
 121  * First call uses 'duprec_hashsize' to create hash table.
 122  */
 123 int             is_duprec (char *recid)
 124 {
 125     static HASHNODE **hashtab = NULL;
 126     static unsigned long primes[10] =
 127     {1013, 1511, 2203, 3511, 5003, 10007, 15013, 20011, 25013, 30001};
 128
 129     unsigned long   i;
 130     char           *cp;
 131     unsigned long   sum;
 132     HASHNODE       *hp, **hpp;
 133
 134     if (duprec_hashsize == 0UL)
 135         return NOT_A_DUP;
 136
 137 /* Generate hash table at first call only */
 138     if (hashtab == NULL) {
 139         /*
 140          * adjust table size upward to nearest preordained prime
 141          * number
 142          */
 143         for (i = 0; i < 9 && primes[i] < duprec_hashsize; i++);
 144         duprec_hashsize = primes[i];
 145 #ifdef TEST
 146         printf (PROGNAME "117 Create hash table, duprec_hashsize set = %ld.\n",
 147             duprec_hashsize);
 148 #endif
 149
 150         hashtab = malloc ((duprec_hashsize + 2L) * sizeof (HASHNODE **));
 151         if (hashtab == NULL)
 152             return OUT_OF_MEM;
 153
 154         /* init table to all NULL pointers. */
 155         hpp = hashtab;
 156         for (i = duprec_hashsize + 2L; i > 0L; i--)
 157             *hpp++ = NULL;
 158     }
 159
 160     /*****dump_hashtab(hashtab);******/
 161
 162     /* HASH FUNCTION:  H(recid) = (SUM(i*recid[i])) mod M,
 163      * where M is table size (prime), and SUM is calculated
 164      * for i=1 to end of recid.  Multiplying the position by the character
 165      * value at that position minimizes the influence of identical
 166      * characters at the beginnings and ends of recids,
 167      * and also usually yields a number larger than M.
 168      * Not skipping over the first position (the keytype char) helps
 169      * efficiently catch recids that are blank after the keytype.
 170      */
 171     sum = 0UL;
 172     i = 1;
 173     cp = recid;
 174     while (*cp != 0)
 175         sum += i++ * (*cp++);
 176     hpp = &(hashtab[sum % duprec_hashsize]);    /* hpp = head of linked
 177                                                  * list */
 178
 179 #ifdef TEST
 180     printf (PROGNAME "150 is_duprec('%s')=hashtab[%lu]=%p: ",
 181         recid, sum % duprec_hashsize, *hpp);
 182     fflush (stdout);
 183     i = 0;
 184 #endif
 185
 186     /* Search linked list (if any) for hashnode containing recid */
 187     for (hp = *hpp; hp != NULL; hp = hp->link) {
 188 #ifdef TEST
 189         i++;
 190 #endif
 191
 192         if (strcmp (hp->recid, recid) == 0) {
 193 #ifdef TEST
 194             printf ("DUP!@listpos=%d\n", i);
 195 #endif
 196             return IS_A_DUP;
 197         }
 198         hpp = &hp->link;        /* now hpp = tail of linked list */
 199     }
 200 #ifdef TEST
 201     printf ("miss@listlen=%d\n", i);
 202 #endif
 203
 204     /* Not a duplicate.  Add current recid to hash table. */
 205     if ((hp = malloc (sizeof (HASHNODE) + strlen (recid) + 2)) == NULL)
 206         return OUT_OF_MEM;
 207     strcpy (hp->recid, recid);
 208     hp->link = NULL;
 209     /*****hp->link = *hpp;******/
 210     *hpp = hp;
 211     return NOT_A_DUP;
 212 }  /* is_duprec() */
 213
 214
 215 #ifdef MAIN
 216 /************************************************/
 217 /*                                              */
 218 /*                   main()                     */
 219 /*                                              */
 220 /************************************************/
 221 main (int argc, char *argv[])
 222 {
 223     int             i;
 224     FILE           *f;
 225     char            buf[2048];
 226
 227     if (argc < 2) {
 228         printf ("USAGE: %s <file> [n]\n"
 229             "where file contains list of char strings\n"
 230             "and optional n changes hash table size.\n",
 231             argv[0]);
 232         return;
 233     }
 234     if ((f = fopen (argv[1], "r")) == NULL) {
 235         printf ("Can't open %s: %s\n", argv[1], strerror (errno));
 236         return;
 237     }
 238     if (argc >= 3)
 239         duprec_hashsize = atol (argv[2]);
 240
 241     while (fgets (buf, sizeof (buf), f) != NULL) {
 242         buf[sizeof (buf) - 1] = 0;
 243         i = is_duprec (buf);
 244         printf ("%s", buf);     /* each buf should end in \n */
 245         if (i > 1)
 246             break;
 247     }
 248     return;
 249 }
 250
 251 #endif
 252 /******************* ISDUPREC.C *******************/