r14956: change the notify search to be much more efficient by using a

per-depth bisection search. This makes the notify_trigger() call
log(N) which makes us scale well for large numbers of outstanding
notifies
(This used to be commit 16fd00925fdbf77e7a403ad501bf6ea429404c76)

1 files changed, 20 insertions, 1 deletions

diff --git a/source4/librpc/idl/notify.idl b/source4/librpc/idl/notify.idl
index 51c7cd1a01..cf544f3a68 100644
--- a/source4/librpc/idl/notify.idl
+++ b/source4/librpc/idl/notify.idl
@@ -19,12 +19,31 @@ interface notify
 		uint32 filter; /* filter to apply in this directory */
 		uint32 subdir_filter; /* filter to apply in child directories */
 		utf8string path;
+		uint32 path_len; /* saves some computation on search */
 		pointer private;
 	} notify_entry;
 
-	typedef [public] struct {
+	/*
+	  to allow for efficient search for matching entries, we
+	  divide them by the directory depth, with a separate array
+	  per depth. The entries within each depth are sorted by path,
+	  allowing for a bisection search.
+
+	  The max_mask and max_mask_subdir at each depth is the
+	  bitwise or of the filters and subdir filters for all entries
+	  at that depth. This allows a depth to be quickly skipped if
+	  no entries will match the target filter	  
+	*/
+	typedef struct {
+		uint32 max_mask;
+		uint32 max_mask_subdir;
 		uint32 num_entries;
 		notify_entry entries[num_entries];
+	} notify_depth;
+
+	typedef [public] struct {
+		uint32 num_depths;
+		notify_depth depth[num_depths];
 	} notify_array;
 
 	/* structure sent between servers in notify messages */