Bug 45160 - Add interval tree capable of holding plain old data (POD)
Summary: Add interval tree capable of holding plain old data (POD)
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: WebCore Misc. (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Kenneth Russell
URL:
Keywords:
Depends on: 45059
Blocks: 44729 45161
  Show dependency tree / graph
 
Reported: 2010-09-02 19:30 PDT by Kenneth Russell
Modified: 2010-09-05 20:47 PDT (History)
7 users (show)

See Also:

Attachments
Patch (14.48 KB, patch)
2010-09-02 19:48 PDT, Kenneth Russell 		kbr: commit-queue-
Details | Formatted Diff | Diff
Revised patch (14.50 KB, patch)
2010-09-02 20:10 PDT, Kenneth Russell 		fishd: review+
kbr: commit-queue-
Details | Formatted Diff | Diff
Show Obsolete (1) View All Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Kenneth Russell 2010-09-02 19:30:09 PDT 
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.
Comment 1 Kenneth Russell 2010-09-02 19:43:17 PDT 
Unit tests for the interval tree will be integrated separately under https://bugs.webkit.org/show_bug.cgi?id=45161 .
Comment 2 Kenneth Russell 2010-09-02 19:48:17 PDT 
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.
Comment 3 WebKit Review Bot 2010-09-02 19:52:47 PDT 
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.
Comment 4 Kenneth Russell 2010-09-02 20:10:16 PDT 
Created attachment 66466 [details]
Revised patch

Fixed style error in above patch.
Comment 5 Darin Fisher (:fishd, Google) 2010-09-03 16:12:15 PDT 
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
Comment 6 Kenneth Russell 2010-09-03 17:21:45 PDT 
(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.
Comment 7 Kenneth Russell 2010-09-03 17:25:21 PDT 
Committed r66779: <http://trac.webkit.org/changeset/66779>