FreeCalypso > hg > ueda-linux

annotate ueda/libueda/hashmcl.c @ 149:d1a507d34e77

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
netdiff: donl-netmatch2 factored out
author Mychaela Falconia <falcon@freecalypso.org>
date Sun, 15 Nov 2020 04:18:47 +0000
parents c91e7a30fab3
children
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>
2
c91e7a30fab3 ueda/libueda Linuxified
Space Falcon <falcon@ivan.Harhan.ORG>
parents: 0
diff changeset
11 #include <stdlib.h>
c91e7a30fab3 ueda/libueda Linuxified
Space Falcon <falcon@ivan.Harhan.ORG>
parents: 0
diff changeset
12 #include <string.h>
0
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
13 #include <strings.h>
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
14 #include "mcl.h"
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
15
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
16 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
17 extern int ncomponents;
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 #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
20
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
21 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
22
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
23 static int
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
24 hash_refdes(str)
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
25 char *str;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
26 {
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
27 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
28 register char *cp;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
29 register int c;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
30
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
31 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
32 accum <<= 4;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
33 accum |= c & 0x0F;
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 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
36 }
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 hash_MCL()
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
39 {
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
40 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
41 int i;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
42 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
43
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
44 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
45 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
46 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
47 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
48 fprintf(stderr,
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
49 "%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
50 comp->name);
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
51 errflag = 1;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
52 break;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
53 }
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
54 if (errflag) {
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
55 errflag = 0;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
56 errstat = -1;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
57 } else
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
58 *hcp = comp;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
59 }
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
60 if (errstat)
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
61 exit(1);
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
62 }
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 report_mclhash_quality()
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
65 {
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
66 int maxchain;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
67 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
68 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
69
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
70 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
71 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
72 comp = comp->nextinhash)
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
73 curchain++;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
74 if (curchain > maxchain)
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
75 maxchain = curchain;
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
76 }
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
77 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
78 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
79 }
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
80
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
81 struct component *
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
82 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
83 register char *refdes;
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 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
86
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
87 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
88 comp = comp->nextinhash)
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
89 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
90 return(comp);
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
91 return(NULL);
cd92449fdb51 initial import of ueda and ifctf-part-lib from ifctfvax CVS
Space Falcon <falcon@ivan.Harhan.ORG>
parents:
diff changeset
92 }