src/hg/lib/hdb.c 1.410

1.410 2009/08/20 18:11:36 larrym
avoid N^2 list scan in hasTrackDbAlready by using a loaded hash
Index: src/hg/lib/hdb.c
===================================================================
RCS file: /projects/compbio/cvsroot/kent/src/hg/lib/hdb.c,v
retrieving revision 1.409
retrieving revision 1.410
diff -b -B -U 4 -r1.409 -r1.410
--- src/hg/lib/hdb.c	14 Aug 2009 07:16:16 -0000	1.409
+++ src/hg/lib/hdb.c	20 Aug 2009 18:11:36 -0000	1.410
@@ -3292,20 +3292,10 @@
     chromOk =  (stringArrayIx(chrom, tdb->restrictList, tdb->restrictCount)) >= 0;
 return chromOk;
 }
 
-static boolean hasTrackDbAlready(struct trackDb *tdb, struct trackDb *list)
-/* Return true if the given list already has the given track (check names) */
-{
-struct trackDb *check;
-for (check = list; check != NULL; check = check->next)
-    if (sameString(check->tableName,tdb->tableName))
-	return TRUE;
-return FALSE;
-}
-
 static boolean loadOneTrackDb(char *db, char *where, char *tblSpec,
-                              struct trackDb **tdbList)
+                              struct trackDb **tdbList, struct hash *loaded)
 /* Load a trackDb table, including handling profiles:tbl. Returns
  * TRUE if table exists */
 {
 char *tbl;
@@ -3315,10 +3305,11 @@
     {
     struct trackDb *oneTable = trackDbLoadWhere(conn, tbl, where), *oneRow;
     while ((oneRow = slPopHead(&oneTable)) != NULL)
         {
-        if (!hasTrackDbAlready(oneRow, *tdbList))
+        if (!hashLookup(loaded, oneRow->tableName))
             {
+            hashAddInt(loaded, oneRow->tableName, 1);
             slAddHead(tdbList, oneRow);
             // record for use in check available tracks
             char *profileName = getTrackProfileName(oneRow);
             if (profileName != NULL)
@@ -3337,17 +3328,20 @@
 {
 struct trackDb *tdbList = NULL;
 struct slName *tableList = hTrackDbList(), *one;
 boolean foundOne = FALSE;
+// A cleaner implementation of loaded hash would be something like slListContainer with support for an exists method
+struct hash *loaded = hashNew(0);
 for (one = tableList; one != NULL; one = one->next)
     {
-    if (loadOneTrackDb(db, where, one->name, &tdbList))
+    if (loadOneTrackDb(db, where, one->name, &tdbList, loaded))
         foundOne = TRUE;
     }
 if (!foundOne)
     errAbort("can not find any trackDb tables for %s, check db.trackDb specification in hg.conf",
              db);
 slNameFreeList(&tableList);
+hashFree(&loaded);
 
 /* fill in supertrack fields, if any in settings */
 trackDbSuperSettings(tdbList);
 return tdbList;