summaryrefslogtreecommitdiff
path: root/source4/librpc/idl
diff options
context:
space:
mode:
authorAndrew Tridgell <tridge@samba.org>2006-04-07 10:36:54 +0000
committerGerald (Jerry) Carter <jerry@samba.org>2007-10-10 14:00:45 -0500
commit127967334fbf3851debacbc0f2574461b542cbad (patch)
tree432b25cf38f45ff491a3c461d6ace17c03a3d1a3 /source4/librpc/idl
parentc07125d13309cf40cf4c68884421a7c102c3494a (diff)
downloadsamba-127967334fbf3851debacbc0f2574461b542cbad.tar.gz
samba-127967334fbf3851debacbc0f2574461b542cbad.tar.bz2
samba-127967334fbf3851debacbc0f2574461b542cbad.zip
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)
Diffstat (limited to 'source4/librpc/idl')
-rw-r--r--source4/librpc/idl/notify.idl21
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 */