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;