diff options
author | Franklin Wei <me@fwei.tk> | 2018-07-09 19:07:28 -0400 |
---|---|---|
committer | Franklin Wei <me@fwei.tk> | 2018-07-09 19:07:28 -0400 |
commit | ab8d3d75ce0dbd2b328b0b40dcb4d1e5f9dc862d (patch) | |
tree | 1f8bbfaae0b7c86585e35292b8b5b01d0a648e1e /iomt.h | |
parent | 5de9ff09f0a812e78681e8eb53b5c36844da1e58 (diff) | |
download | csaa-ab8d3d75ce0dbd2b328b0b40dcb4d1e5f9dc862d.zip csaa-ab8d3d75ce0dbd2b328b0b40dcb4d1e5f9dc862d.tar.gz csaa-ab8d3d75ce0dbd2b328b0b40dcb4d1e5f9dc862d.tar.bz2 csaa-ab8d3d75ce0dbd2b328b0b40dcb4d1e5f9dc862d.tar.xz |
Optimize IOMT leaf lookup/encloser search
We now use three separate searches, which are O(log n) time each, whereas the
OR'd together version would incur a O(n) scan of the entire leaves table.
Diffstat (limited to 'iomt.h')
-rw-r--r-- | iomt.h | 6 |
1 files changed, 5 insertions, 1 deletions
@@ -41,7 +41,11 @@ struct iomt { sqlite3_stmt *getnode, *updatenode, *insertnode; sqlite3_stmt *getleaf, *updateleaf, *insertleaf; - sqlite3_stmt *findleaf, *findencloser, *findleaf_or_encloser; + sqlite3_stmt *findleaf; + sqlite3_stmt *findencloser[3]; /* 3 cases, OR'd together + * (we run them + * individually so they're + * O(logn) each */ } db; struct { hash_t *mt_nodes; /* this has 2 * mt_leafcount - 1 elements. Note |