[cairo-commit] 2 commits - BIBLIOGRAPHY src/cairo-skiplist.c src/cairo-skiplist-private.h

[Behdad Esfahbod]

 BIBLIOGRAPHY                 |    8 ++++++++
 src/cairo-skiplist-private.h |    6 ++++++
 src/cairo-skiplist.c         |    2 +-
 3 files changed, 15 insertions(+), 1 deletion(-)

New commits:
diff-tree 9da86e4a386505288c3a933f30583abf7706c950 (from ad0e13805c036941a03e49215b1bb525b4666033)
Author: Behdad Esfahbod <behdad at behdad.org>
Date:   Sun Apr 8 22:56:30 2007 -0400

    Add references to the skiplist paper

diff --git a/BIBLIOGRAPHY b/BIBLIOGRAPHY
index 073e636..dacd532 100644
--- a/BIBLIOGRAPHY
+++ b/BIBLIOGRAPHY
@@ -60,6 +60,14 @@ algorithm for robustness against edges b
 intersection coordinates to the grid available by finite-precision
 arithmetic. This is one algorithm we have not implemented yet.
 
+We use a data-structure called Skiplists in the our implementation
+of Bentley-Ottmann:
+
+	W. Pugh, Skip Lists: a Probabilistic Alternative to Balanced Trees,
+	Communications of the ACM, vol. 33, no. 6, pp.668-676, 1990.
+
+	http://citeseer.ist.psu.edu/pugh90skip.html
+
 From the result of the intersection-finding pass, we are currently
 computing a tessellation of trapezoids, (the exact manner is
 undergoing some work right now with some important speedup), but we
diff --git a/src/cairo-skiplist-private.h b/src/cairo-skiplist-private.h
index b152f4b..2ad4034 100644
--- a/src/cairo-skiplist-private.h
+++ b/src/cairo-skiplist-private.h
@@ -26,6 +26,12 @@
 
 #include "cairoint.h"
 
+/*
+ * Skip lists are described in detail here:
+ *
+ *   http://citeseer.ist.psu.edu/pugh90skip.html
+ */
+
 #define MAX_LEVEL   31
 
 /*
diff-tree ad0e13805c036941a03e49215b1bb525b4666033 (from e8072e6e0ac86b2b0baefb54dcc551ee548164af)
Author: Behdad Esfahbod <behdad at behdad.org>
Date:   Sun Apr 8 22:50:51 2007 -0400

    [cairo-skiplist] Clarify MAX_LEVEL in comment, and adjust accordingly
    
    Reading the code, MAX_LEVEL is in fact what could have been named
    MAX_NUM_LEVELS.  That is, it is maximum possible level plus one.
    All code is correct: it uses MAX_LEVEL as array size and never produces
    a level of MAX_LEVEL.  The comment is fixed.

diff --git a/src/cairo-skiplist.c b/src/cairo-skiplist.c
index a12392a..c8a3018 100644
--- a/src/cairo-skiplist.c
+++ b/src/cairo-skiplist.c
@@ -261,7 +261,7 @@ _cairo_skip_list_fini (cairo_skip_list_t
  * Generate a random level number, distributed
  * so that each level is 1/4 as likely as the one before
  *
- * Note that level numbers run 1 <= level <= MAX_LEVEL
+ * Note that level numbers run 1 <= level < MAX_LEVEL
  */
 static int
 random_level (void)