Return to Answer

More "<" & ">" fixups.

edited Jul 27, 2014 at 3:18

 #include <stdlib.h> #include <stdio.h> #include <ctype.h> // Throw caution, and error checking, to the winds. // #include <assert.h> #define RANGEMIN (1) #define RANGEMAX (50*1000*1000) #define SEARCHBOUNDARY (100) typedef struct { int A; int B; int T; } tuple_t; typedef struct bin { tuple_t slot; struct bin *next; // NULL=>0NULL=>0 items, self=>1self=>1 item, other=>overflowother=>overflow } bin_t; #define LISTSIZE (RANGEMAX) tuple_t list[LISTSIZE]; #define HASH(x) (x-1) #define LOOKUPSIZE (LISTSIZE) bin_t lookup[LOOKUPSIZE]; bin_t overflow[LISTSIZE]; int overflowNext = 0; // based on strtol() static inline int s2i(char *s, char **r) { char c; int l = 0; do { c = *s++; } while (!isdigit(c)); do { l = l * 10 + (c - '0'); c = *s++; } while (isdigit(c)); *r = s - 1; return l; } static inline void lookupInsert(tuple_t x) { bin_t *p = lookup + HASH(x.B); if (p->next>next) { overflow[overflowNext].slot = x; overflow[overflowNext].next = (p->next>next == p) ? p : p->next;>next; p->next>next = overflow + overflowNext; overflowNext++; } else { p->slot>slot = x; p->next>next = p; } } static void printOverflow(bin_t * head, bin_t * tail) { if (head->next>next != tail) { printOverflow(head->next>next, tail); } printf("%d %d %d\n", head->slot>slot.A, head->slot>slot.B, head->slot>slot.T); } static inline void dumpLookupSortedOnB() { bin_t *p; for (p = lookup; p next< (lookup + LOOKUPSIZE); p++) { if (p->next) {  printf("%d %d %d\n", p->slot>slot.A, p->slot>slot.B, p->slot>slot.T); if (p != p->next>next) { printOverflow(p->next>next, p); } } } } static inline void printIfMatch(tuple_t abt, tuple_t cdu) { int A, B, T; int C, D, U; A = abt.A; D = cdu.B; if (D == A) { T = abt.T; U = cdu.T; if ((0 ≤<= (T - U)) && ((T - U) < SEARCHBOUNDARY)) { B = abt.B; C = cdu.A; printf("%d %d %d\n", A, B, T); printf("%d %d %d\n", C, D, U); } } } static inline void printMatches(int n) { tuple_t *p; for (p = list; p < (list + n); p++) { bin_t *b = lookup + HASH(p->A); if (b->next) { bin_t *q; printIfMatch(*p, b->slot); for (q = b->next; q != b; q = q->next) { printIfMatch(*p, q->slot); } } } } static inline void overflowTattle(int n) { fprintf(stderr, "%d/%d items in overflow\n", overflowNext, n); } int main(int argc, char *argv[]) { int n; // initialize lookup[] { bin_t *p = lookup; for (n = 0; n < LOOKUPSIZE; n++) { p->next = NULL; p++; } } // read all tuples into list[] and insert into lookup[] & overflow[] { char line[64]; char *lp; tuple_t *p = list; for (n = 0; fgets(line, sizeof(line), stdin); n++) { p->A = s2i(line, &lp); p->B = s2i(lp, &lp); p->T = s2i(lp, &lp); lookupInsert(*p); p++; } } printMatches(n); exit(0); }

 #include <stdlib.h> #include <stdio.h> #include <ctype.h> // Throw caution, and error checking, to the winds. // #include #define RANGEMIN (1) #define RANGEMAX (50*1000*1000) #define SEARCHBOUNDARY (100) typedef struct { int A; int B; int T; } tuple_t; typedef struct bin { tuple_t slot; struct bin *next; // NULL=>0 items, self=>1 item, other=>overflow } bin_t; #define LISTSIZE (RANGEMAX) tuple_t list[LISTSIZE]; #define HASH(x) (x-1) #define LOOKUPSIZE (LISTSIZE) bin_t lookup[LOOKUPSIZE]; bin_t overflow[LISTSIZE]; int overflowNext = 0; // based on strtol() static inline int s2i(char *s, char **r) { char c; int l = 0; do { c = *s++; } while (!isdigit(c)); do { l = l * 10 + (c - '0'); c = *s++; } while (isdigit(c)); *r = s - 1; return l; } static inline void lookupInsert(tuple_t x) { bin_t *p = lookup + HASH(x.B); if (p->next) { overflow[overflowNext].slot = x; overflow[overflowNext].next = (p->next == p) ? p : p->next; p->next = overflow + overflowNext; overflowNext++; } else { p->slot = x; p->next = p; } } static void printOverflow(bin_t * head, bin_t * tail) { if (head->next != tail) { printOverflow(head->next, tail); } printf("%d %d %d\n", head->slot.A, head->slot.B, head->slot.T); } static inline void dumpLookupSortedOnB() { bin_t *p; for (p = lookup; p next) { printf("%d %d %d\n", p->slot.A, p->slot.B, p->slot.T); if (p != p->next) { printOverflow(p->next, p); } } } } static inline void printIfMatch(tuple_t abt, tuple_t cdu) { int A, B, T; int C, D, U; A = abt.A; D = cdu.B; if (D == A) { T = abt.T; U = cdu.T; if ((0 ≤ (T - U)) && ((T - U) < SEARCHBOUNDARY)) { B = abt.B; C = cdu.A; printf("%d %d %d\n", A, B, T); printf("%d %d %d\n", C, D, U); } } } static inline void printMatches(int n) { tuple_t *p; for (p = list; p < (list + n); p++) { bin_t *b = lookup + HASH(p->A); if (b->next) { bin_t *q; printIfMatch(*p, b->slot); for (q = b->next; q != b; q = q->next) { printIfMatch(*p, q->slot); } } } } static inline void overflowTattle(int n) { fprintf(stderr, "%d/%d items in overflow\n", overflowNext, n); } int main(int argc, char *argv[]) { int n; // initialize lookup[] { bin_t *p = lookup; for (n = 0; n < LOOKUPSIZE; n++) { p->next = NULL; p++; } } // read all tuples into list[] and insert into lookup[] & overflow[] { char line[64]; char *lp; tuple_t *p = list; for (n = 0; fgets(line, sizeof(line), stdin); n++) { p->A = s2i(line, &lp); p->B = s2i(lp, &lp); p->T = s2i(lp, &lp); lookupInsert(*p); p++; } } printMatches(n); exit(0); }

 #include <stdlib.h> #include <stdio.h> #include <ctype.h> // Throw caution, and error checking, to the winds. // #include <assert.h> #define RANGEMIN (1) #define RANGEMAX (50*1000*1000) #define SEARCHBOUNDARY (100) typedef struct { int A; int B; int T; } tuple_t; typedef struct bin { tuple_t slot; struct bin *next; // NULL=>0 items, self=>1 item, other=>overflow } bin_t; #define LISTSIZE (RANGEMAX) tuple_t list[LISTSIZE]; #define HASH(x) (x-1) #define LOOKUPSIZE (LISTSIZE) bin_t lookup[LOOKUPSIZE]; bin_t overflow[LISTSIZE]; int overflowNext = 0; // based on strtol() static inline int s2i(char *s, char **r) { char c; int l = 0; do { c = *s++; } while (!isdigit(c)); do { l = l * 10 + (c - '0'); c = *s++; } while (isdigit(c)); *r = s - 1; return l; } static inline void lookupInsert(tuple_t x) { bin_t *p = lookup + HASH(x.B); if (p->next) { overflow[overflowNext].slot = x; overflow[overflowNext].next = (p->next == p) ? p : p->next; p->next = overflow + overflowNext; overflowNext++; } else { p->slot = x; p->next = p; } } static void printOverflow(bin_t * head, bin_t * tail) { if (head->next != tail) { printOverflow(head->next, tail); } printf("%d %d %d\n", head->slot.A, head->slot.B, head->slot.T); } static inline void dumpLookupSortedOnB() { bin_t *p; for (p = lookup; p < (lookup + LOOKUPSIZE); p++) { if (p->next) {  printf("%d %d %d\n", p->slot.A, p->slot.B, p->slot.T); if (p != p->next) { printOverflow(p->next, p); } } } } static inline void printIfMatch(tuple_t abt, tuple_t cdu) { int A, B, T; int C, D, U; A = abt.A; D = cdu.B; if (D == A) { T = abt.T; U = cdu.T; if ((0 <= (T - U)) && ((T - U) < SEARCHBOUNDARY)) { B = abt.B; C = cdu.A; printf("%d %d %d\n", A, B, T); printf("%d %d %d\n", C, D, U); } } } static inline void printMatches(int n) { tuple_t *p; for (p = list; p < (list + n); p++) { bin_t *b = lookup + HASH(p->A); if (b->next) { bin_t *q; printIfMatch(*p, b->slot); for (q = b->next; q != b; q = q->next) { printIfMatch(*p, q->slot); } } } } static inline void overflowTattle(int n) { fprintf(stderr, "%d/%d items in overflow\n", overflowNext, n); } int main(int argc, char *argv[]) { int n; // initialize lookup[] { bin_t *p = lookup; for (n = 0; n < LOOKUPSIZE; n++) { p->next = NULL; p++; } } // read all tuples into list[] and insert into lookup[] & overflow[] { char line[64]; char *lp; tuple_t *p = list; for (n = 0; fgets(line, sizeof(line), stdin); n++) { p->A = s2i(line, &lp); p->B = s2i(lp, &lp); p->T = s2i(lp, &lp); lookupInsert(*p); p++; } } printMatches(n); exit(0); }

Fix missing "<" & ">", eaten as HTML.

Source Link

edited Jul 27, 2014 at 3:06

Scott Leadley

 #include <stdlib.h> #include <stdio.h> #include <ctype.h> // Throw caution, and error checking, to the winds. // #include #define RANGEMIN (1) #define RANGEMAX (50*1000*1000) #define SEARCHBOUNDARY (100) typedef struct { int A; int B; int T; } tuple_t; typedef struct bin { tuple_t slot; struct bin *next; // NULL=>0 items, self=>1 item, other=>overflow } bin_t; #define LISTSIZE (RANGEMAX) tuple_t list[LISTSIZE]; #define HASH(x) (x-1) #define LOOKUPSIZE (LISTSIZE) bin_t lookup[LOOKUPSIZE]; bin_t overflow[LISTSIZE]; int overflowNext = 0; // based on strtol() static inline int s2i(char *s, char **r) { char c; int l = 0; do { c = *s++; } while (!isdigit(c)); do { l = l * 10 + (c - '0'); c = *s++; } while (isdigit(c)); *r = s - 1; return l; } static inline void lookupInsert(tuple_t x) { bin_t *p = lookup + HASH(x.B); if (p->next) { overflow[overflowNext].slot = x; overflow[overflowNext].next = (p->next == p) ? p : p->next; p->next = overflow + overflowNext; overflowNext++; } else { p->slot = x; p->next = p; } } static void printOverflow(bin_t * head, bin_t * tail) { if (head->next != tail) { printOverflow(head->next, tail); } printf("%d %d %d\n", head->slot.A, head->slot.B, head->slot.T); } static inline void dumpLookupSortedOnB() { bin_t *p; for (p = lookup; p next) { printf("%d %d %d\n", p->slot.A, p->slot.B, p->slot.T); if (p != p->next) { printOverflow(p->next, p); } } } } static inline void printIfMatch(tuple_t abt, tuple_t cdu) { int A, B, T; int C, D, U; A = abt.A; D = cdu.B; if (D == A) { T = abt.T; U = cdu.T; if ((0 ≤ (T - U)) && ((T - U) < SEARCHBOUNDARY)) { B = abt.B; C = cdu.A; printf("%d %d %d\n", A, B, T); printf("%d %d %d\n", C, D, U); } } } static inline void printMatches(int n) { tuple_t *p; for (p = list; p < (list + n); p++) {  bin_t *b = lookup + HASH(p->A);  if (b->next>next) { bin_t *q; printIfMatch(*p, b->slot>slot); for (q = b->next;>next; q != b; q = q->next>next) { printIfMatch(*p, q->slot>slot); } } } } static inline void overflowTattle(int n) { fprintf(stderr, "%d/%d items in overflow\n", overflowNext, n); } int main(int argc, char *argv[]) { int n; // initialize lookup[] { bin_t *p = lookup; for (n = 0; n next< LOOKUPSIZE; n++) {  p->next = NULL; p++; } } // read all tuples into list[] and insert into lookup[] & overflow[] { char line[64]; char *lp; tuple_t *p = list; for (n = 0; fgets(line, sizeof(line), stdin); n++) { p->A>A = s2i(line, &lp); p->B>B = s2i(lp, &lp); p->T>T = s2i(lp, &lp); lookupInsert(*p); p++; } } printMatches(n); exit(0); }

Compile with <"gcc"gcc -O3 -std=c99 -Wall -m64".

 #include #include #include // Throw caution, and error checking, to the winds. // #include #define RANGEMIN (1) #define RANGEMAX (50*1000*1000) #define SEARCHBOUNDARY (100) typedef struct { int A; int B; int T; } tuple_t; typedef struct bin { tuple_t slot; struct bin *next; // NULL=>0 items, self=>1 item, other=>overflow } bin_t; #define LISTSIZE (RANGEMAX) tuple_t list[LISTSIZE]; #define HASH(x) (x-1) #define LOOKUPSIZE (LISTSIZE) bin_t lookup[LOOKUPSIZE]; bin_t overflow[LISTSIZE]; int overflowNext = 0; // based on strtol() static inline int s2i(char *s, char **r) { char c; int l = 0; do { c = *s++; } while (!isdigit(c)); do { l = l * 10 + (c - '0'); c = *s++; } while (isdigit(c)); *r = s - 1; return l; } static inline void lookupInsert(tuple_t x) { bin_t *p = lookup + HASH(x.B); if (p->next) { overflow[overflowNext].slot = x; overflow[overflowNext].next = (p->next == p) ? p : p->next; p->next = overflow + overflowNext; overflowNext++; } else { p->slot = x; p->next = p; } } static void printOverflow(bin_t * head, bin_t * tail) { if (head->next != tail) { printOverflow(head->next, tail); } printf("%d %d %d\n", head->slot.A, head->slot.B, head->slot.T); } static inline void dumpLookupSortedOnB() { bin_t *p; for (p = lookup; p next) { printf("%d %d %d\n", p->slot.A, p->slot.B, p->slot.T); if (p != p->next) { printOverflow(p->next, p); } } } } static inline void printIfMatch(tuple_t abt, tuple_t cdu) { int A, B, T; int C, D, U; A = abt.A; D = cdu.B; if (D == A) { T = abt.T; U = cdu.T; if ((0 A); if (b->next) { bin_t *q; printIfMatch(*p, b->slot); for (q = b->next; q != b; q = q->next) { printIfMatch(*p, q->slot); } } } } static inline void overflowTattle(int n) { fprintf(stderr, "%d/%d items in overflow\n", overflowNext, n); } int main(int argc, char *argv[]) { int n; // initialize lookup[] { bin_t *p = lookup; for (n = 0; n next = NULL; p++; } } // read all tuples into list[] and insert into lookup[] & overflow[] { char line[64]; char *lp; tuple_t *p = list; for (n = 0; fgets(line, sizeof(line), stdin); n++) { p->A = s2i(line, &lp); p->B = s2i(lp, &lp); p->T = s2i(lp, &lp); lookupInsert(*p); p++; } } printMatches(n); exit(0); }

Compile with <"gcc -O3 -std=c99 -Wall -m64".

 #include <stdlib.h> #include <stdio.h> #include <ctype.h> // Throw caution, and error checking, to the winds. // #include #define RANGEMIN (1) #define RANGEMAX (50*1000*1000) #define SEARCHBOUNDARY (100) typedef struct { int A; int B; int T; } tuple_t; typedef struct bin { tuple_t slot; struct bin *next; // NULL=>0 items, self=>1 item, other=>overflow } bin_t; #define LISTSIZE (RANGEMAX) tuple_t list[LISTSIZE]; #define HASH(x) (x-1) #define LOOKUPSIZE (LISTSIZE) bin_t lookup[LOOKUPSIZE]; bin_t overflow[LISTSIZE]; int overflowNext = 0; // based on strtol() static inline int s2i(char *s, char **r) { char c; int l = 0; do { c = *s++; } while (!isdigit(c)); do { l = l * 10 + (c - '0'); c = *s++; } while (isdigit(c)); *r = s - 1; return l; } static inline void lookupInsert(tuple_t x) { bin_t *p = lookup + HASH(x.B); if (p->next) { overflow[overflowNext].slot = x; overflow[overflowNext].next = (p->next == p) ? p : p->next; p->next = overflow + overflowNext; overflowNext++; } else { p->slot = x; p->next = p; } } static void printOverflow(bin_t * head, bin_t * tail) { if (head->next != tail) { printOverflow(head->next, tail); } printf("%d %d %d\n", head->slot.A, head->slot.B, head->slot.T); } static inline void dumpLookupSortedOnB() { bin_t *p; for (p = lookup; p next) { printf("%d %d %d\n", p->slot.A, p->slot.B, p->slot.T); if (p != p->next) { printOverflow(p->next, p); } } } } static inline void printIfMatch(tuple_t abt, tuple_t cdu) { int A, B, T; int C, D, U; A = abt.A; D = cdu.B; if (D == A) { T = abt.T; U = cdu.T; if ((0 ≤ (T - U)) && ((T - U) < SEARCHBOUNDARY)) { B = abt.B; C = cdu.A; printf("%d %d %d\n", A, B, T); printf("%d %d %d\n", C, D, U); } } } static inline void printMatches(int n) { tuple_t *p; for (p = list; p < (list + n); p++) {  bin_t *b = lookup + HASH(p->A);  if (b->next) { bin_t *q; printIfMatch(*p, b->slot); for (q = b->next; q != b; q = q->next) { printIfMatch(*p, q->slot); } } } } static inline void overflowTattle(int n) { fprintf(stderr, "%d/%d items in overflow\n", overflowNext, n); } int main(int argc, char *argv[]) { int n; // initialize lookup[] { bin_t *p = lookup; for (n = 0; n < LOOKUPSIZE; n++) {  p->next = NULL; p++; } } // read all tuples into list[] and insert into lookup[] & overflow[] { char line[64]; char *lp; tuple_t *p = list; for (n = 0; fgets(line, sizeof(line), stdin); n++) { p->A = s2i(line, &lp); p->B = s2i(lp, &lp); p->T = s2i(lp, &lp); lookupInsert(*p); p++; } } printMatches(n); exit(0); }

Compile with "gcc -O3 -std=c99 -Wall -m64".

Source Link

answered Jul 27, 2014 at 2:52

Scott Leadley

I finally got a chance to build a physical Ubuntu 14.04 system similar to Lembik's and do a post-mortem on my solution to this puzzle. In my choice of importance:

The true master is James_pic, because he didn't optimize prematurely.

he had a plan
he executed the plan at a high level of abstraction (Scala) and refined it there
he refined it further in C
he didn't over-refine it (see next point)

File system I/O time is probably the lower-bound on elapsed time for the target system.

Lembik alludes to this, i.e. "The winners ... both are almost as fast as wc!"

Some of the reasons my original solution ~~sucked~~ was non-performant:

Locality of reference is the dominant factor on the target system.
Sorting on A or B is a good idea when doing a hash sort. Sorting on T adds complexity (and cache-hostile indirection) to the hash sort, at least the way I did it.
Scanf() is a pig.
Massive bandwidth (disk->memory->cache) changes where the bottlenecks are. The target system doesn't have massive bandwidth. (see next point)

Rapid development works best if done in the target environment.

Duh! But, I was stuck with Solaris/SPARC originally and couldn't play otherwise.
It's difficult to eliminate caching effects in a virtualized and SAN environment.
Linux VMs typically have the same issues.

A little bit of math helps.

Fetching one tuple directly from the hash table cuts the probability of indirect references to ~37% (~1/e).
Fetching two tuples directly from the hash table would have cut references to the overflow table to ~10%. It wasn't necessary.

The 32-bit memory model (gcc -m32) is a distraction.

Sometimes a small win for unthreaded programs, sometimes a small loss.
Sometimes a significant loss for threaded programs.
If 32-bit is a significant win (and the target isn't an embedded controller), it's probably cheaper to refresh the hardware.
Take the extra registers and larger address space and don't look back.

Scanf() is a pig, but using stdio is not hopeless.

Most of scanf()'s overhead appears to be in the format-driven parsing and string to integer conversion.

Replacing sscanf() with:

strtok() + atoi() is ~2x faster (see table below)
strtol() is ~3x faster
a custom, local strtol() is ~6.5x faster
replacing strtol() with a local solution puts it on par with "wc"
a FSM using getc_unlocked() is almost as fast as Keith Randall's minimalist mmap() solution

the results of my experiments while re-implementing in C [in CSV, since Stack Exchange apparently doesn't do tables]:

 "solution (64-bit unless noted)","disposition of input","user","system","elapsed" "dd if=? of=/dev/null bs=1024k","","0.010","1.107","26.47" "wc {LANG=C}","","4.921","0.752","26.38" "","","","","" "fscanf()","discard","13.130","0.490","26.43" "fgets(), no integer conversion","discard","1.636","0.468","26.42" "fgets() + sscanf()","discard","16.173","0.498","26.48" "fgets() + strtok(), no integer conversion","discard","4.659","0.481","26.48" "fgets() + strtok() + atoi()","discard","8.929","0.490","26.49" "fgets() + strtol()","discard","6.009","0.483","26.50" "fgets() + custom-strtol()","discard","3.842","0.474","26.43" "fgets() + custom-strtol()","sort (load hash) while reading","7.118","1.207","26.70" "fgets() + custom-strtol()","sort, match & print","10.096","1.357","28.40" "fgets() + custom-strtol(), 32-bit","sort, match & print","10.065","1.159","28.38" "","","","","" "james_pic's solution","sort, match & print","9.764","1.113","28.21"

Rather than boring you with yet another FSM parser, the solution below uses fgets() and a local strtol() replacement [look for s2i()].

A reference implementation in Ruby:

#!/usr/bin/ruby2.0 # only tested against ruby v1.9 & v2.0 =begin Filter a file based on these rules: Input: - each line is a set of three integers - each line is formatted as <number> <w> <number> <w> <number> - <w> is whitespace (a single blank in the challenge) - <number> is an integer in the range 1..50_000_000 Output a given tuple ( A B T ) if: - there exists a tuple ( C D U ) 0 <= T - U < 100 and D == A OR - there exists a tuple ( C D U ) 0 <= U - T < 100 and B == C Typical use: filter.rb test.input | sort | uniq > test.output =end list = Array.new lookupB = Hash.new { |hash, key| hash[key] = Array.new } ARGF.each_with_index do |line, index| abt = line.split.map { |s| s.to_i } list << abt lookupB[abt[1]] << index end for abt in list do for i in Array( lookupB[abt[0]] ) do delta = abt[2] - list[i][2] # T - U if (0<=delta) && (delta<100) puts "#{abt.join(' ')}" puts "#{list[i].join(' ')}" end end end

It's a dog, ~50x slower than a C solution, but perl is just as slow and less concise.

The C solution:

 #include #include #include // Throw caution, and error checking, to the winds. // #include #define RANGEMIN (1) #define RANGEMAX (50*1000*1000) #define SEARCHBOUNDARY (100) typedef struct { int A; int B; int T; } tuple_t; typedef struct bin { tuple_t slot; struct bin *next; // NULL=>0 items, self=>1 item, other=>overflow } bin_t; #define LISTSIZE (RANGEMAX) tuple_t list[LISTSIZE]; #define HASH(x) (x-1) #define LOOKUPSIZE (LISTSIZE) bin_t lookup[LOOKUPSIZE]; bin_t overflow[LISTSIZE]; int overflowNext = 0; // based on strtol() static inline int s2i(char *s, char **r) { char c; int l = 0; do { c = *s++; } while (!isdigit(c)); do { l = l * 10 + (c - '0'); c = *s++; } while (isdigit(c)); *r = s - 1; return l; } static inline void lookupInsert(tuple_t x) { bin_t *p = lookup + HASH(x.B); if (p->next) { overflow[overflowNext].slot = x; overflow[overflowNext].next = (p->next == p) ? p : p->next; p->next = overflow + overflowNext; overflowNext++; } else { p->slot = x; p->next = p; } } static void printOverflow(bin_t * head, bin_t * tail) { if (head->next != tail) { printOverflow(head->next, tail); } printf("%d %d %d\n", head->slot.A, head->slot.B, head->slot.T); } static inline void dumpLookupSortedOnB() { bin_t *p; for (p = lookup; p next) { printf("%d %d %d\n", p->slot.A, p->slot.B, p->slot.T); if (p != p->next) { printOverflow(p->next, p); } } } } static inline void printIfMatch(tuple_t abt, tuple_t cdu) { int A, B, T; int C, D, U; A = abt.A; D = cdu.B; if (D == A) { T = abt.T; U = cdu.T; if ((0 A); if (b->next) { bin_t *q; printIfMatch(*p, b->slot); for (q = b->next; q != b; q = q->next) { printIfMatch(*p, q->slot); } } } } static inline void overflowTattle(int n) { fprintf(stderr, "%d/%d items in overflow\n", overflowNext, n); } int main(int argc, char *argv[]) { int n; // initialize lookup[] { bin_t *p = lookup; for (n = 0; n next = NULL; p++; } } // read all tuples into list[] and insert into lookup[] & overflow[] { char line[64]; char *lp; tuple_t *p = list; for (n = 0; fgets(line, sizeof(line), stdin); n++) { p->A = s2i(line, &lp); p->B = s2i(lp, &lp); p->T = s2i(lp, &lp); lookupInsert(*p); p++; } } printMatches(n); exit(0); }

Compile with <"gcc -O3 -std=c99 -Wall -m64".