aboutsummaryrefslogtreecommitdiff
path: root/iomt.h
diff options
context:
space:
mode:
authorFranklin Wei <me@fwei.tk>2018-07-09 19:07:28 -0400
committerFranklin Wei <me@fwei.tk>2018-07-09 19:07:28 -0400
commitab8d3d75ce0dbd2b328b0b40dcb4d1e5f9dc862d (patch)
tree1f8bbfaae0b7c86585e35292b8b5b01d0a648e1e /iomt.h
parent5de9ff09f0a812e78681e8eb53b5c36844da1e58 (diff)
downloadcsaa-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.h6
1 files changed, 5 insertions, 1 deletions
diff --git a/iomt.h b/iomt.h
index 1c0c0f7..723ce6c 100644
--- a/iomt.h
+++ b/iomt.h
@@ -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