From 127967334fbf3851debacbc0f2574461b542cbad Mon Sep 17 00:00:00 2001 From: Andrew Tridgell Date: Fri, 7 Apr 2006 10:36:54 +0000 Subject: 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) --- source4/librpc/idl/notify.idl | 21 ++++++++++++++++++++- 1 file changed, 20 insertions(+), 1 deletion(-) (limited to 'source4/librpc') 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 */ -- cgit