Bug 45160 – Add interval tree capable of holding plain old data (POD)

• Status: RESOLVED
• Resolution: FIXED
• Component: WebCore Misc.

[Kenneth Russell]

An interval tree capable of holding plain old data (POD) is needed in support of some graphics algorithms currently being integrated. It can be used for a general class of graphics problems, including determining all overlaps of sets of rectangles.

[Kenneth Russell]

Unit tests for the interval tree will be integrated separately under https://bugs.webkit.org/show_bug.cgi?id=45161 .

[Kenneth Russell]

Created attachment 66462 [details]
Patch

From the ChangeLog:

Adding an interval tree currently capable of holding types which do not require their destructors to be called. POD is a slight misnomer which will be corrected soon, hopefully by removing this restriction.

This class is based on the augmentable property of the red/black tree integrated under bug 45059.

Unit tests for the PODIntervalTree will be integrated separately under bug 45161.

[WebKit Review Bot]

Attachment 66462 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style']" exit_code: 1
WebCore/platform/graphics/gpu/PODIntervalTree.h:37:  Alphabetical sorting problem.  [build/include_order] [4]
Total errors found: 1 in 3 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Kenneth Russell]

Created attachment 66466 [details]
Revised patch

Fixed style error in above patch.

[Darin Fisher (:fishd, Google)]

Comment on attachment 66466 [details]
Revised patch

View in context: https://bugs.webkit.org/attachment.cgi?id=66466&action=prettypatch

> WebCore/platform/graphics/gpu/PODIntervalTree.h:81
> +class PODInterval {
nit: move to a separate header file (PODInterval.h)

> WebCore/platform/graphics/gpu/PODIntervalTree.h:170
> +                     public PODRedBlackTree<PODInterval<T, UserData> > {
nit: indentation

> WebCore/platform/graphics/gpu/PODIntervalTree.h:336
> +String valueToString(const PODInterval<T, UserData>& interval)
nit: move to PODInterval.h


R=me w/ those changes

[Kenneth Russell]

(In reply to comment #5)
> (From update of attachment 66466 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=66466&action=prettypatch
> 
> > WebCore/platform/graphics/gpu/PODIntervalTree.h:81
> > +class PODInterval {
> nit: move to a separate header file (PODInterval.h)
> 
> > WebCore/platform/graphics/gpu/PODIntervalTree.h:170
> > +                     public PODRedBlackTree<PODInterval<T, UserData> > {
> nit: indentation
> 
> > WebCore/platform/graphics/gpu/PODIntervalTree.h:336
> > +String valueToString(const PODInterval<T, UserData>& interval)
> nit: move to PODInterval.h
> 
> 
> R=me w/ those changes

Will fix these in the landed patch.

[Kenneth Russell]

Committed r66779: <http://trac.webkit.org/changeset/66779>