FreeCalypso > hg > ueda-linux

annotate ueda/libueda/hashmcl.c @ 0:cd92449fdb51

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
initial import of ueda and ifctf-part-lib from ifctfvax CVS
author Space Falcon <falcon@ivan.Harhan.ORG>
date Mon, 20 Jul 2015 00:24:37 +0000
parents
children c91e7a30fab3
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
1 /*
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
2 * MCL hash table logic
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
3 *
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
4 * This module implements construction and use of a hash table indexing
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
5 * the MCL components by refdes. It facilitates checking the MCL for
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
6 * duplicate refdes errors and fast component lookups.
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
7 */
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
8
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
9 #include <sys/types.h>
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
10 #include <stdio.h>
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
11 #include <strings.h>
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
12 #include "mcl.h"
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
13
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
14 extern struct component components[];
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
15 extern int ncomponents;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
16
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
17 #define HASH_SIZE 1103
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
18
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
19 static struct component *mclhashtab[HASH_SIZE];
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
20
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
21 static int
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
22 hash_refdes(str)
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
23 char *str;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
24 {
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
25 register u_long accum;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
26 register char *cp;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
27 register int c;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
28
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
29 for (cp = str, accum = 0; c = *cp; cp++) {
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
30 accum <<= 4;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
31 accum |= c & 0x0F;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
32 }
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
33 return(accum % HASH_SIZE);
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
34 }
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
35
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
36 hash_MCL()
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
37 {
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
38 register struct component *comp, *hc, **hcp;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
39 int i;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
40 int errflag = 0, errstat = 0;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
41
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
42 for (comp = components, i = 0; i < ncomponents; comp++, i++) {
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
43 hcp = mclhashtab + hash_refdes(comp->name);
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
44 for (; hc = *hcp; hcp = &hc->nextinhash)
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
45 if (!strcmp(comp->name, hc->name)) {
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
46 fprintf(stderr,
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
47 "%s: duplicate refdes in the MCL\n",
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
48 comp->name);
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
49 errflag = 1;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
50 break;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
51 }
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
52 if (errflag) {
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
53 errflag = 0;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
54 errstat = -1;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
55 } else
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
56 *hcp = comp;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
57 }
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
58 if (errstat)
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
59 exit(1);
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
60 }
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
61
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
62 report_mclhash_quality()
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
63 {
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
64 int maxchain;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
65 register int hb, curchain;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
66 register struct component *comp;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
67
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
68 for (hb = 0, maxchain = 0; hb < HASH_SIZE; hb++) {
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
69 for (comp = mclhashtab[hb], curchain = 0; comp;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
70 comp = comp->nextinhash)
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
71 curchain++;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
72 if (curchain > maxchain)
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
73 maxchain = curchain;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
74 }
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
75 printf("Total components: %d\n", ncomponents);
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
76 printf("Longest hash chain: %d\n", maxchain);
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
77 }
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
78
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
79 struct component *
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
80 find_comp_by_refdes(refdes)
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
81 register char *refdes;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
82 {
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
83 register struct component *comp;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
84
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
85 for (comp = mclhashtab[hash_refdes(refdes)]; comp;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
86 comp = comp->nextinhash)
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
87 if (!strcmp(comp->name, refdes))
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
88 return(comp);
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
89 return(NULL);
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
90 }