78fd01e7d81e12b132a1a9d2238015c67e25475f
angie
  Thu Sep 28 10:02:48 2017 -0700
Added option to structure joinerPair routeList as a tree using joinerPairListToTree() and new child pointer, so that if one pair's b is the same table as another pair's a, the second pair becomes the child of the first pair.  This enables us to generate more efficient SQL joins.

diff --git src/hg/inc/joiner.h src/hg/inc/joiner.h
index 468531d..5c43a7e 100644
--- src/hg/inc/joiner.h
+++ src/hg/inc/joiner.h
@@ -141,37 +141,38 @@
 
 void joinerDtfToSqlTableString(struct joinerDtf *dtf, char *db, char *buf, size_t bufSize);
 /* If dtf->database is different from db (or db is NULL), write database.table info buf,
  * otherwise just table. */
 
 void joinerDtfFree(struct joinerDtf **pDtf);
 /* Free up memory associated with joinerDtf. */
 
 void joinerDtfFreeList(struct joinerDtf **pList);
 /* Free up memory associated with list of joinerDtfs. */
 
 struct joinerDtf *joinerDtfFromDottedTriple(char *triple);
 /* Get joinerDtf from something in db.table.field format. */
 
 struct joinerPair
-/* A pair of linked fields. */
+/* A pair of linked fields (possibly with a child whose a->table is the same as this b->table. */
     {
     struct joinerPair *next;	/* Next in list. */
     struct joinerDtf *a;	/* Typically contains field from input table */
     struct joinerDtf *b;	/* Field in another table */
     struct joinerSet *identifier;	/* Identifier this is based on,
                                          * not allocated here. */
+    struct joinerPair *child;   /* Optional tree structure for representing hierarchical routes. */
     };
 
 void joinerPairFree(struct joinerPair **pJp);
 /* Free up memory associated with joiner pair. */
 
 void joinerPairFreeList(struct joinerPair **pList);
 /* Free up memory associated with list of joinerPairs. */
 
 void joinerPairDump(struct joinerPair *jpList, FILE *out);
 /* Write out joiner pair list to file mostly for debugging. */
 
 struct joinerPair *joinerRelate(struct joiner *joiner, char *database, 
 	char *table);
 /* Get list of all ways to link table in given database to other tables,
  * possibly in other databases. */
@@ -180,32 +181,37 @@
 /* Return list of self, children, and parents (but not siblings).
  * slFreeList result when done. */
 
 struct joinerField *joinerSetFindField(struct joinerSet *js, struct joinerDtf *dtf);
 /* Find field in set if any that matches dtf */
 
 boolean joinerDtfSameTable(struct joinerDtf *a, struct joinerDtf *b);
 /* Return TRUE if they are in the same database and table. */
 
 boolean joinerDtfAllSameTable(struct joinerDtf *fieldList);
 /* Return TRUE if all joinerPairs refer to same table. */
 
 struct joinerPair *joinerFindRoute(struct joiner *joiner, 
 	struct joinerDtf *a,  struct joinerDtf *b);
 /* Find route between a and b.  Note the field element of a and b
- * are unused. */
+ * are unused.  No tree structure (joinerPair->child not used). */
 
 struct joinerPair *joinerFindRouteThroughAll(struct joiner *joiner, 
 	struct joinerDtf *tableList);
 /* Return route that gets to all tables in fieldList.  Note that
- * the field element of the items in tableList can be NULL. */
+ * the field element of the items in tableList can be NULL.
+ * No tree structure (joinerPair->child not used). */
+
+void joinerPairListToTree(struct joinerPair *routeList);
+/* Convert a linear routeList (only next used, not child) to a tree structure in which
+ * pairs like {X,Y} and {Y,Z} (first b == second a) are connected using child instead of next. */
 
 char *joinerFieldChopKey(struct joinerField *jf, char *key);
 /* If jf includes chopBefore and/or chopAfter, apply those to key and return a starting
  * offset in key, which may be modified. */
 
 void joinerFieldIterateKey(struct joinerField *jf, void(*callback)(void *context, char *key),
                            void *context, char *key);
 /* Process key according to jf -- if jf->separator, may result in list of processed keys --
  * and invoke callback with each processed key. */
 
 #endif /* JOINER_H */