servo: Merge #591 - Automatic tile removal (from eschweic:del-tiles); r=pcwalton
authoreschweic <eschweickart@mozilla.com>
Wed, 17 Jul 2013 11:46:24 -0700
changeset 333520 18ed9188f1ef77c3bc4bf8566025a528ad9ee5c6
parent 333519 5fd4247c7e9b89ed61a28a30659babbd74d0ade6
child 333521 5d28d0d019c11172cc5f89cff87192bb0e6f93a5
push id31307
push usergszorc@mozilla.com
push dateSat, 04 Feb 2017 00:59:06 +0000
treeherdermozilla-central@94079d43835f [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerspcwalton
servo: Merge #591 - Automatic tile removal (from eschweic:del-tiles); r=pcwalton The quadtree is now initialized with a memory limit, and tiles are deleted automatically if that limit is exceeded. The memory limit can also be set to None to prevent this behavior. Source-Repo: https://github.com/servo/servo Source-Revision: c17ede3716d64c703ed8aed56d84d8187bf8a854
servo/src/components/main/compositing/mod.rs
servo/src/components/main/compositing/quadtree.rs
servo/src/components/msg/compositor_msg.rs
--- a/servo/src/components/main/compositing/mod.rs
+++ b/servo/src/components/main/compositing/mod.rs
@@ -304,22 +304,19 @@ impl CompositorTask {
                                                                  -world_offset.y,
                                                                  0.0));
             *recomposite = true;
         };
 
         let ask_for_tiles: @fn() = || {
             match *quadtree {
                 Some(ref mut quad) => {
-                    let valid = |tile: &~LayerBuffer| -> bool {
-                        tile.resolution == *world_zoom
-                    };
                     let (tile_request, redisplay) = quad.get_tile_rects(Rect(Point2D(world_offset.x as int,
                                                                                      world_offset.y as int),
-                                                                             *window_size), valid, *world_zoom);
+                                                                             *window_size), *world_zoom);
 
                     if !tile_request.is_empty() {
                         match *render_chan {
                             Some(ref chan) => {
                                 chan.send(ReRenderMsg(tile_request, *world_zoom));
                             }
                             _ => {
                                 println("Warning: Compositor: Cannot send tile request, no render chan initialized");
@@ -414,20 +411,19 @@ impl CompositorTask {
                         let size = window.size();
                         chan.send(Size2D(size.width as int, size.height as int));
                     }
 
                     GetGLContext(chan) => chan.send(current_gl_context()),
                     
                     NewLayer(new_size, tile_size) => {
                         *page_size = Size2D(new_size.width as f32, new_size.height as f32);
-                        *quadtree = Some(Quadtree::new(0, 0,
-                                                       new_size.width.max(&(window_size.width as uint)),
+                        *quadtree = Some(Quadtree::new(new_size.width.max(&(window_size.width as uint)),
                                                        new_size.height.max(&(window_size.height as uint)),
-                                                       tile_size));
+                                                       tile_size, Some(10000000u)));
                         ask_for_tiles();
                         
                     }
                     ResizeLayer(new_size) => {
                         *page_size = Size2D(new_size.width as f32, new_size.height as f32);
                         // TODO: update quadtree, ask for tiles
                     }
                     DeleteLayer => {
@@ -597,17 +593,17 @@ impl CompositorTask {
                 *done = true;
             }
 
             if *recomposite {
                 *recomposite = false;
                 composite();
             }
 
-            timer::sleep(&uv_global_loop::get(), 100);
+            timer::sleep(&uv_global_loop::get(), 10);
 
             // If a pinch-zoom happened recently, ask for tiles at the new resolution
             if *zoom_action && precise_time_s() - *zoom_time > 0.3 {
                 *zoom_action = false;
                 ask_for_tiles();
             }
 
         }
--- a/servo/src/components/main/compositing/quadtree.rs
+++ b/servo/src/components/main/compositing/quadtree.rs
@@ -5,123 +5,151 @@
 // Implements a Quadtree data structure to keep track of which tiles have
 // been rasterized and which have not.
 
 use geom::point::Point2D;
 use geom::size::Size2D;
 use geom::rect::Rect;
 use std::uint::{div_ceil, next_power_of_two};
 use std::vec::build_sized;
+use std::util::replace;
 use gfx::render_task::BufferRequest;
+use servo_msg::compositor_msg::Tile;
 
 /// Parent to all quadtree nodes. Stores variables needed at all levels. All method calls
 /// at this level are in pixel coordinates.
 pub struct Quadtree<T> {
     root: QuadtreeNode<T>,
     max_tile_size: uint,
+    max_mem: Option<uint>,
 }
 
 /// A node in the tree. All method calls at this level are in page coordinates.
 struct QuadtreeNode<T> {
     /// The tile belonging to this node. Note that parent nodes can have tiles.
     tile: Option<T>,
     /// The position of the node in page coordinates.
     origin: Point2D<f32>,
     /// The width and height of the node in page coordinates.
     size: f32,
     /// The node's children.
     quadrants: [Option<~QuadtreeNode<T>>, ..4],
     /// If this node is marked for rendering
     render_flag: bool,
+    /// Combined size of self.tile and tiles of all descendants
+    tile_mem: uint,
 }
 
 priv enum Quadrant {
     TL = 0,
     TR = 1,
     BL = 2,
     BR = 3,
 }
 
-impl<T> Quadtree<T> {
+impl<T: Tile> Quadtree<T> {
     /// Public method to create a new Quadtree
-    pub fn new(x: uint, y: uint, width: uint, height: uint, tile_size: uint) -> Quadtree<T> {        
+    /// Takes in the initial width and height of the space, a maximum tile size, and
+    /// a maximum amount of memory. Tiles will be deleted if this memory is exceeded.
+    /// Set max_mem to None to turn off automatic tile removal.
+    pub fn new(width: uint, height: uint, tile_size: uint, max_mem: Option<uint>) -> Quadtree<T> {
         // Spaces must be squares and powers of 2, so expand the space until it is
         let longer = width.max(&height);
         let num_tiles = div_ceil(longer, tile_size);
         let power_of_two = next_power_of_two(num_tiles);
         let size = power_of_two * tile_size;
         
         Quadtree {
             root: QuadtreeNode {
                 tile: None,
-                origin: Point2D(x as f32, y as f32),
+                origin: Point2D(0f32, 0f32),
                 size: size as f32,
                 quadrants: [None, None, None, None],
                 render_flag: false,
+                tile_mem: 0,
             },
             max_tile_size: tile_size,
+            max_mem: max_mem,
         }
     }
 
     /// Return the maximum allowed tile size
     pub fn get_tile_size(&self) -> uint {
         self.max_tile_size
     }
     /// Get a tile at a given pixel position and scale.
     pub fn get_tile<'r>(&'r self, x: uint, y: uint, scale: f32) -> &'r Option<T> {
         self.root.get_tile(x as f32 / scale, y as f32 / scale)
     }
     /// Add a tile associtated with a given pixel position and scale.
+    /// If the tile pushes the total memory over its maximum, tiles will be removed
+    /// until total memory is below the maximum again.
     pub fn add_tile(&mut self, x: uint, y: uint, scale: f32, tile: T) {
         self.root.add_tile(x as f32 / scale, y as f32 / scale, tile, self.max_tile_size as f32 / scale);
+        match self.max_mem {
+            Some(max) => {
+                while self.root.tile_mem > max {
+                    let r = self.root.remove_tile(x as f32 / scale, y as f32 / scale);
+                    match r {
+                        (Some(_), _, _) => {}
+                        _ => fail!("Quadtree: No valid tiles to remove"),
+                    }
+                }
+            }
+            None => {}
+        }
     }
     /// Get the tile rect in screen and page coordinates for a given pixel position
     pub fn get_tile_rect(&mut self, x: uint, y: uint, scale: f32) -> BufferRequest {
         self.root.get_tile_rect(x as f32 / scale, y as f32 / scale, scale, self.max_tile_size as f32 / scale)
     }
     /// Get all the tiles in the tree
     pub fn get_all_tiles<'r>(&'r self) -> ~[&'r T] {
         self.root.get_all_tiles()
     }
     /// Ask a tile to be deleted from the quadtree. This tries to delete a tile that is far from the
     /// given point in pixel coordinates.
-    pub fn remove_tile(&mut self, x: uint, y: uint, scale: f32) {
-        self.root.remove_tile(x as f32 / scale, y as f32 / scale);
+    pub fn remove_tile(&mut self, x: uint, y: uint, scale: f32) -> T {
+        let r = self.root.remove_tile(x as f32 / scale, y as f32 / scale);
+        match r {
+            (Some(tile), _, _) => tile,
+            _ => fail!("Quadtree: No valid tiles to remove"),
+        }
     }
-    /// Given a window rect in pixel coordinates and a function to check if an existing tile is "valid"
-    /// (i.e. is the correct resolution), this function returns a list of BufferRequests for tiles that
+    /// Given a window rect in pixel coordinates, this function returns a list of BufferRequests for tiles that
     /// need to be rendered. It also returns a boolean if the window needs to be redisplayed, i.e. if
     /// no tiles need to be rendered, but the display tree needs to be rebuilt. This can occur when the
     /// user zooms out and cached tiles need to be displayed on top of higher resolution tiles.
-    pub fn get_tile_rects(&mut self, window: Rect<int>, valid: &fn(&T) -> bool, scale: f32) ->
-        (~[BufferRequest], bool) {
-        
-        self.root.get_tile_rects(Rect(Point2D(window.origin.x as f32 / scale, window.origin.y as f32 / scale),
-                                      Size2D(window.size.width as f32 / scale, window.size.height as f32 / scale)),
-                                 valid, scale, self.max_tile_size as f32 / scale)
-            
+    /// When this happens, higher resolution tiles will be removed from the quadtree.
+    pub fn get_tile_rects(&mut self, window: Rect<int>, scale: f32) -> (~[BufferRequest], bool) {
+        let (ret, redisplay, _) = self.root.get_tile_rects(
+            Rect(Point2D(window.origin.x as f32 / scale, window.origin.y as f32 / scale),
+                 Size2D(window.size.width as f32 / scale, window.size.height as f32 / scale)),
+            scale, self.max_tile_size as f32 / scale);
+        (ret, redisplay)
     }
 
     /// Generate html to visualize the tree. For debugging purposes only.
     pub fn get_html(&self) -> ~str {
         static HEADER: &'static str = "<!DOCTYPE html><html>";
         fmt!("%s<body>%s</body></html>", HEADER, self.root.get_html())
     }
 
 }
 
-impl<T> QuadtreeNode<T> {
+impl<T: Tile> QuadtreeNode<T> {
     /// Private method to create new children
     fn new_child(x: f32, y: f32, size: f32) -> QuadtreeNode<T> {
         QuadtreeNode {
             tile: None,
             origin: Point2D(x, y),
             size: size,
             quadrants: [None, None, None, None],
             render_flag: false,
+            tile_mem: 0,
         }
     }
     
     /// Determine which child contains a given point in page coords.
     fn get_quadrant(&self, x: f32, y: f32) -> Quadrant {
         if x < self.origin.x + self.size / 2.0 {
             if y < self.origin.y + self.size / 2.0 { 
                 TL
@@ -166,69 +194,66 @@ impl<T> QuadtreeNode<T> {
         }
 
 
         return ret;
     }
 
     /// Add a tile associated with a given position in page coords. If the tile size exceeds the maximum,
     /// the node will be split and the method will recurse until the tile size is within limits.
-    fn add_tile(&mut self, x: f32, y: f32, tile: T, tile_size: f32) {
+    /// Returns an the difference in tile memory between the new quadtree node and the old quadtree node.
+    fn add_tile(&mut self, x: f32, y: f32, tile: T, tile_size: f32) -> int {
         debug!("Quadtree: Adding: (%?, %?) size:%?px", self.origin.x, self.origin.y, self.size);
 
         if x >= self.origin.x + self.size || x < self.origin.x
             || y >= self.origin.y + self.size || y < self.origin.y {
             fail!("Quadtree: Tried to add tile to invalid region");
         }
         
         if self.size <= tile_size { // We are the child
+            let old_size = self.tile_mem;
+            self.tile_mem = tile.get_mem();
             self.tile = Some(tile);
             // FIXME: This should be inline, but currently won't compile
             let quads = [TL, TR, BL, BR];
             for quads.iter().advance |quad| {
                 self.quadrants[*quad as int] = None;
             }
             self.render_flag = false;
+            self.tile_mem as int - old_size as int
         } else { // Send tile to children            
             let quad = self.get_quadrant(x, y);
             match self.quadrants[quad as int] {
-                Some(ref mut child) => child.add_tile(x, y, tile, tile_size),
+                Some(ref mut child) => {
+                    let delta = child.add_tile(x, y, tile, tile_size);
+                    self.tile_mem = (self.tile_mem as int + delta) as uint;
+                    delta
+                }
                 None => { // Make new child      
                     let new_size = self.size / 2.0;
                     let new_x = match quad {
                         TL | BL => self.origin.x,
                         TR | BR => self.origin.x + new_size,
                     };
                     let new_y = match quad {
                         TL | TR => self.origin.y,
                         BL | BR => self.origin.y + new_size,
                     };
                     let mut c = ~QuadtreeNode::new_child(new_x, new_y, new_size);
-                    c.add_tile(x, y, tile, tile_size);
+                    let delta = c.add_tile(x, y, tile, tile_size);
+                    self.tile_mem = (self.tile_mem as int + delta) as uint;    
                     self.quadrants[quad as int] = Some(c);
-
-                    // If my tile is completely occluded, get rid of it.
-                    // FIXME: figure out a better way to determine if a tile is completely occluded
-                    // e.g. this alg doesn't work if a tile is covered by its grandchildren
-                    match self.quadrants {
-                        [Some(ref tl_child), Some(ref tr_child), Some(ref bl_child), Some(ref br_child)] => {
-                            match (&tl_child.tile, &tr_child.tile, &bl_child.tile, &br_child.tile) {
-                                (&Some(_), &Some(_), &Some(_), &Some(_)) => self.tile = None,
-                                _ => {}
-                            }
-                        }
-                        _ => {}
-                    }
+                    delta
                 }
             }
         }
     }
 
     /// Get a tile rect in screen and page coords for a given position in page coords
-    fn get_tile_rect(&mut self, x: f32, y: f32, scale: f32, tile_size: f32) -> BufferRequest {    
+    fn get_tile_rect(&mut self, x: f32, y: f32, scale: f32, tile_size: f32) -> BufferRequest {
         if x >= self.origin.x + self.size || x < self.origin.x
             || y >= self.origin.y + self.size || y < self.origin.y {
             fail!("Quadtree: Tried to query a tile rect outside of range");
         }
         
         if self.size <= tile_size {
             let self_x = (self.origin.x * scale).ceil() as uint;
             let self_y = (self.origin.y * scale).ceil() as uint;
@@ -254,88 +279,91 @@ impl<T> QuadtreeNode<T> {
                 let result = c.get_tile_rect(x, y, scale, tile_size);
                 self.quadrants[quad as int] = Some(c);
                 result
             }
             Some(ref mut child) => child.get_tile_rect(x, y, scale, tile_size),
         }
     }
 
-    /// Removes a tile that is far from the given input point in page coords. Returns true if the child
-    /// has no tiles and needs to be deleted.
-    fn remove_tile(&mut self, x: f32, y: f32) -> bool {
-        match (&self.tile, &self.quadrants) {
-            (&Some(_), &[None, None, None, None]) => {
-                self.tile = None;
-                return true;
+    /// Removes a tile that is far from the given input point in page coords. Returns the tile removed,
+    /// a bool that is true if the child has no tiles and needs to be deleted, and an integer showing the
+    /// amount of memory changed by the operation. Unfortunately, the tile has to be an option, because
+    /// there are occasionally leaves without tiles. However, the option will always be Some as long as
+    /// this quadtree node or at least one of its descendants is not empty.
+    fn remove_tile(&mut self, x: f32, y: f32) -> (Option<T>, bool, int) {
+        if self.tile.is_some() {
+            let ret = replace(&mut(self.tile), None);
+            return match (ret, &self.quadrants)  {
+                (Some(tile), &[None, None, None, None]) => { 
+                    let size = -(tile.get_mem() as int);
+                    (Some(tile), true, size)
+                }
+                (Some(tile), _) => {
+                    let size = -(tile.get_mem() as int);
+                    (Some(tile), false, size)
+                }
+                _ => fail!("Quadtree: tile query failure in remove_tile"),
             }
-            (&Some(_), _) => {
-                self.tile = None;
-                return false;
-            }
-            _ => {}
         }
         
         // This is a hacky heuristic to find a tile that is "far away". There are better methods.
         let quad = self.get_quadrant(x, y);
-        let my_child = match quad {
-            TL => {
-                match (&self.quadrants[BR as int], &self.quadrants[BL as int], &self.quadrants[TR as int]) {
-                    (&Some(_), _, _) => BR,
-                    (&None, &Some(_), _) => BL,
-                    (&None, &None, &Some(_)) => TR,
-                    _ => TL,
+        let queue = match quad {
+            TL => [BR, BL, TR, TL], 
+            TR => [BL, BR, TL, TR],
+            BL => [TR, TL, BR, BL], 
+            BR => [TL, TR, BL, BR],
+        };
+
+        let mut del_quad: Option<Quadrant> = None;
+        let mut ret = (None, false, 0);
+        
+        for queue.iter().advance |quad| {
+            match self.quadrants[*quad as int] {
+                Some(ref mut child) => {
+                    let (tile, flag, delta) = child.remove_tile(x, y);
+                    match tile {
+                        Some(_) => {
+                            self.tile_mem = (self.tile_mem as int + delta) as uint;
+                            if flag {
+                                del_quad = Some(*quad);
+                            } else {
+                                return (tile, flag, delta);
+                            }
+
+                            ret = (tile, flag, delta);
+                            break;
+                        }
+                        None => {},
+                    }
                 }
+                None => {},
             }
-            TR => {
-                match (&self.quadrants[BL as int], &self.quadrants[BR as int], &self.quadrants[TL as int]) {
-                    (&Some(_), _, _) => BL,
-                    (&None, &Some(_), _) => BR,
-                    (&None, &None, &Some(_)) => TL,
-                    _ => TR,
+        }
+        
+        match del_quad {
+            Some(quad) => {
+                self.quadrants[quad as int] = None;
+                let (tile, _, delta) = ret;
+                match (&self.tile, &self.quadrants) {
+                    (&None, &[None, None, None, None]) => (tile, true, delta),
+                    _ => (tile, false, delta)
                 }
             }
-            BL => {
-                match (&self.quadrants[TR as int], &self.quadrants[TL as int], &self.quadrants[BR as int]) {
-                    (&Some(_), _, _) => TR,
-                    (&None, &Some(_), _) => TL,
-                    (&None, &None, &Some(_)) => BR,
-                    _ => BL,
-                }
-            }
-            BR => {
-                match (&self.quadrants[TL as int], &self.quadrants[TR as int], &self.quadrants[BL as int]) {
-                    (&Some(_), _, _) => TL,
-                    (&None, &Some(_), _) => TR,
-                    (&None, &None, &Some(_)) => BL,
-                    _ => BR,
-                }
-            }
-        };
-
-        match self.quadrants[my_child as int] {
-            Some(ref mut child) if !child.remove_tile(x, y) => {
-                return false;
-            }
-            Some(_) => {} // fall through
-            None => fail!("Quadtree: child query failure"),
-        }
-
-        // child.remove_tile() returned true
-        self.quadrants[my_child as int] = None;
-        match self.quadrants {
-            [None, None, None, None] => true,
-            _ => false,
+            None => ret,
         }
     }
     
-    /// Given a window rect in page coordinates and a tile validation function, returns a BufferRequest array
-    /// and a redisplay boolean. See QuadTree function description for more details.
-    fn get_tile_rects(&mut self, window: Rect<f32>, valid: &fn(&T) -> bool, scale: f32, tile_size: f32) ->
-        (~[BufferRequest], bool) {
+    /// Given a window rect in page coordinates, returns a BufferRequest array,
+    /// a redisplay boolean, and the difference in tile memory between the new and old quadtree nodes.
+    /// NOTE: this method will sometimes modify the tree by deleting tiles.
+    /// See the QuadTree function description for more details.
+    fn get_tile_rects(&mut self, window: Rect<f32>, scale: f32, tile_size: f32) ->
+        (~[BufferRequest], bool, int) {
         
         let w_x = window.origin.x;
         let w_y = window.origin.y;
         let w_width = window.size.width;
         let w_height = window.size.height;
         let s_x = self.origin.x;
         let s_y = self.origin.y;
         let s_size = self.size;
@@ -344,32 +372,37 @@ impl<T> QuadtreeNode<T> {
             || w_y < s_y || w_y + w_height > s_y + s_size {
             println(fmt!("window: %?, %?, %?, %?; self: %?, %?, %?",
                          w_x, w_y, w_width, w_height, s_x, s_y, s_size));
             fail!("Quadtree: tried to query an invalid tile rect");
         }
         
         if s_size <= tile_size { // We are the child
             return match self.tile {
-                _ if self.render_flag => (~[], false),
-                Some(ref tile) if valid(tile) => {
+                _ if self.render_flag => (~[], false, 0),
+                Some(ref tile) if tile.is_valid(scale) => {
                     let redisplay = match self.quadrants {
                         [None, None, None, None] => false,
                         _ => true,
                     };
+                    let mut delta = 0;
                     if redisplay {
+                        let old_mem = self.tile_mem;
                         // FIXME: This should be inline, but currently won't compile
                         let quads = [TL, TR, BL, BR];
                         for quads.iter().advance |quad| {
                             self.quadrants[*quad as int] = None;
                         }
+                        self.tile_mem = tile.get_mem();
+                        delta = self.tile_mem as int - old_mem as int;
+
                     }
-                    (~[], redisplay)
+                    (~[], redisplay, delta)
                 }
-                _ => (~[self.get_tile_rect(s_x, s_y, scale, tile_size)], false),
+                _ => (~[self.get_tile_rect(s_x, s_y, scale, tile_size)], false, 0),
             }
         }
         
         // Otherwise, we either have children or will have children
         let w_tl_quad = self.get_quadrant(w_x, w_y);
         let w_br_quad = self.get_quadrant(w_x + w_width, w_y + w_height);
         
         // Figure out which quadrants the window is in
@@ -395,16 +428,17 @@ impl<T> QuadtreeNode<T> {
                 }
             }
         };
         
         let quads_to_check = build_sized(4, builder);
         
         let mut ret = ~[];
         let mut redisplay = false;
+        let mut delta = 0;
         
         for quads_to_check.iter().advance |quad| {
             // Recurse into child
             let new_window = match *quad {
                 TL => Rect(window.origin,
                            Size2D(w_width.min(&(s_x + s_size / 2.0 - w_x)),
                                   w_height.min(&(s_y + s_size / 2.0 - w_y)))),
                 TR => Rect(Point2D(w_x.max(&(s_x + s_size / 2.0)),
@@ -417,41 +451,42 @@ impl<T> QuadtreeNode<T> {
                                   w_height.min(&(w_y + w_height - (s_y + s_size / 2.0))))),
                 BR => Rect(Point2D(w_x.max(&(s_x + s_size / 2.0)),
                                    w_y.max(&(s_y + s_size / 2.0))),
                            Size2D(w_width.min(&(w_x + w_width - (s_x + s_size / 2.0))),
                                   w_height.min(&(w_y + w_height - (s_y + s_size / 2.0))))), 
                 
             };
 
-            let (c_ret, c_redisplay) = match self.quadrants[*quad as int] {
-                Some(ref mut child) => child.get_tile_rects(new_window, |x| valid(x), scale, tile_size),
+            let (c_ret, c_redisplay, c_delta) = match self.quadrants[*quad as int] {
+                Some(ref mut child) => child.get_tile_rects(new_window, scale, tile_size),
                 None => {
                     // Create new child
                     let new_size = self.size / 2.0;
                     let new_x = match *quad {
                         TL | BL => self.origin.x,
                         TR | BR => self.origin.x + new_size,
                     };
                     let new_y = match *quad {
                         TL | TR => self.origin.y,
                         BL | BR => self.origin.y + new_size,
                     };
                     let mut child = ~QuadtreeNode::new_child(new_x, new_y, new_size);
-                    let (a, b) = child.get_tile_rects(new_window, |x| valid(x), scale, tile_size);
+                    let (a, b, c) = child.get_tile_rects(new_window, scale, tile_size);
                     self.quadrants[*quad as int] = Some(child);
-                    (a, b)
+                    (a, b, c)
                 }
             };
             
+            delta = delta + c_delta;
             ret = ret + c_ret;
             redisplay = redisplay || c_redisplay;
-        }
-        
-        (ret, redisplay)
+        } 
+        self.tile_mem = (self.tile_mem as int + delta) as uint;
+        (ret, redisplay, delta)
     }
 
 
     /// Generate html to visualize the tree.
     /// This is really inefficient, but it's for testing only.
     fn get_html(&self) -> ~str {
         let mut ret = ~"";
         match self.tile {
@@ -487,20 +522,47 @@ impl<T> QuadtreeNode<T> {
         }
         return ret;
     }
 
 }
 
 
 #[test]
-fn test_add_tile() {
-    let mut t = Quadtree::new(50, 30, 20, 20, 10);
-    assert!(t.get_tile(50, 30, 1.0).is_none());
-    t.add_tile(50, 30, 1.0, 1);
-    assert!(t.get_tile(50, 30, 1.0).get() == 1);
-    assert!(t.get_tile(59, 39, 1.0).get() == 1);
-    assert!(t.get_tile(60, 40, 1.0).is_none());
-    assert!(t.get_tile(110, 70, 2.0).get() == 1);
-    t.add_tile(100, 60, 2.0, 2);
-    assert!(t.get_tile(109, 69, 2.0).get() == 2);
-    assert!(t.get_tile(110, 70, 2.0).get() == 1);
-}
\ No newline at end of file
+pub fn test() {
+    struct T {
+        a: int,
+    }
+    
+    impl Tile for T {
+        fn get_mem(&self) -> uint {
+            1
+        }
+        
+        fn is_valid(&self, _: f32) -> bool {
+            true
+        }
+    }
+    
+    let mut q = Quadtree::new(8, 8, 2, Some(4));
+    q.add_tile(0, 0, 1f32, T{a: 0});  
+    q.add_tile(0, 0, 2f32, T{a: 1});
+    q.add_tile(0, 0, 2f32, T{a: 2});
+    q.add_tile(2, 0, 2f32, T{a: 3});
+    assert!(q.root.tile_mem == 3);
+    assert!(q.get_all_tiles().len() == 3);
+    q.add_tile(0, 2, 2f32, T{a: 4});
+    q.add_tile(2, 2, 2f32, T{a: 5});
+    assert!(q.root.tile_mem == 4);
+
+    let (request, _) = q.get_tile_rects(Rect(Point2D(0, 0), Size2D(2, 2)), 2f32);
+    assert!(request.is_empty());
+    let (request, _) = q.get_tile_rects(Rect(Point2D(0, 0), Size2D(2, 2)), 1.9);
+    assert!(request.is_empty());
+    let (request, _) = q.get_tile_rects(Rect(Point2D(0, 0), Size2D(2, 2)), 1f32);
+    assert!(request.len() == 4);
+
+    q.add_tile(0, 0, 0.5, T{a: 6});
+    q.add_tile(0, 0, 1f32, T{a: 7});
+    let (_, redisplay) = q.get_tile_rects(Rect(Point2D(0, 0), Size2D(2, 2)), 0.5);
+    assert!(redisplay);
+    assert!(q.root.tile_mem == 1);
+}
--- a/servo/src/components/msg/compositor_msg.rs
+++ b/servo/src/components/msg/compositor_msg.rs
@@ -4,16 +4,17 @@
 
 use azure::azure_hl::DrawTarget;
 use azure::azure::AzGLContext;
 use geom::rect::Rect;
 use geom::size::Size2D;
 
 use extra::arc;
 
+
 #[deriving(Clone)]
 pub struct LayerBuffer {
     draw_target: DrawTarget,
 
     // The rect in the containing RenderLayer that this represents.
     rect: Rect<f32>,
 
     // The rect in pixels that will be drawn to the screen.
@@ -63,8 +64,26 @@ pub trait RenderListener {
     fn set_render_state(&self, render_state: RenderState);
 }
 
 /// The interface used by the script task to tell the compositor to update its ready state,
 /// which is used in displaying the appropriate message in the window's title.
 pub trait ScriptListener : Clone {
     fn set_ready_state(&self, ReadyState);
 }
+
+/// The interface used by the quadtree to get info about LayerBuffers
+pub trait Tile {
+    /// Returns the amount of memory used by the tile
+    fn get_mem(&self) -> uint;
+    /// Returns true if the tile is displayable at the given scale
+    fn is_valid(&self, f32) -> bool;
+}
+
+impl Tile for ~LayerBuffer {
+    fn get_mem(&self) -> uint {
+        // This works for now, but in the future we may want a better heuristic
+        self.screen_pos.size.width * self.screen_pos.size.height
+    }
+    fn is_valid(&self, scale: f32) -> bool {
+        self.resolution.approx_eq(&scale)
+    }    
+}