diff options
| -rw-r--r-- | src/cairo-skiplist-private.h | 15 | ||||
| -rw-r--r-- | src/cairo-skiplist.c | 28 |
2 files changed, 32 insertions, 11 deletions
diff --git a/src/cairo-skiplist-private.h b/src/cairo-skiplist-private.h index 2ad40341c..3a948afce 100644 --- a/src/cairo-skiplist-private.h +++ b/src/cairo-skiplist-private.h @@ -32,7 +32,18 @@ * http://citeseer.ist.psu.edu/pugh90skip.html */ -#define MAX_LEVEL 31 +/* Note that random_level() called from alloc_node_for_level() depends on + * this being not more than 16. + */ +#define MAX_LEVEL 15 + +/* Returns the index of the free-list to use for a node at level 'level' */ +#define FREELIST_FOR_LEVEL(level) (((level) - 1) / 2) + +/* Returns the maximum level that uses the same free-list as 'level' does */ +#define FREELIST_MAX_LEVEL_FOR(level) (((level) + 1) & ~1) + +#define MAX_FREELIST_LEVEL (FREELIST_FOR_LEVEL (MAX_LEVEL - 1) + 1) /* * Skip list element. In order to use the skip list, the caller must @@ -58,7 +69,7 @@ typedef struct _skip_list { size_t elt_size; size_t data_size; skip_elt_t *chains[MAX_LEVEL]; - skip_elt_t *freelists[MAX_LEVEL]; + skip_elt_t *freelists[MAX_FREELIST_LEVEL]; int max_level; } cairo_skip_list_t; diff --git a/src/cairo-skiplist.c b/src/cairo-skiplist.c index d493731b5..72ca6ce15 100644 --- a/src/cairo-skiplist.c +++ b/src/cairo-skiplist.c @@ -232,6 +232,9 @@ _cairo_skip_list_init (cairo_skip_list_t *list, for (i = 0; i < MAX_LEVEL; i++) { list->chains[i] = NULL; + } + + for (i = 0; i < MAX_FREELIST_LEVEL; i++) { list->freelists[i] = NULL; } @@ -247,7 +250,7 @@ _cairo_skip_list_fini (cairo_skip_list_t *list) while ((elt = list->chains[0])) { _cairo_skip_list_delete_given (list, elt); } - for (i=0; i<MAX_LEVEL; i++) { + for (i=0; i<MAX_FREELIST_LEVEL; i++) { elt = list->freelists[i]; while (elt) { skip_elt_t *nextfree = elt->prev; @@ -266,9 +269,12 @@ _cairo_skip_list_fini (cairo_skip_list_t *list) static int random_level (void) { - /* tricky bit -- each bit is '1' 75% of the time */ - long int bits = lfsr_random() | lfsr_random(); int level = 0; + /* tricky bit -- each bit is '1' 75% of the time. + * This works because we only use the lower MAX_LEVEL + * bits, and MAX_LEVEL < 16 */ + long int bits = lfsr_random(); + bits |= bits >> 16; while (++level < MAX_LEVEL) { @@ -282,19 +288,23 @@ random_level (void) static void * alloc_node_for_level (cairo_skip_list_t *list, unsigned level) { - if (list->freelists[level-1]) { - skip_elt_t *elt = list->freelists[level-1]; - list->freelists[level-1] = elt->prev; + int freelist_level = FREELIST_FOR_LEVEL (level); + if (list->freelists[freelist_level]) { + skip_elt_t *elt = list->freelists[freelist_level]; + list->freelists[freelist_level] = elt->prev; return ELT_DATA(elt); } - return malloc (list->elt_size + (level-1) * sizeof (skip_elt_t *)); + return malloc (list->elt_size + + (FREELIST_MAX_LEVEL_FOR (level) - 1) * sizeof (skip_elt_t *)); } static void free_elt (cairo_skip_list_t *list, skip_elt_t *elt) { - elt->prev = list->freelists[elt->prev_index]; - list->freelists[elt->prev_index] = elt; + int level = elt->prev_index + 1; + int freelist_level = FREELIST_FOR_LEVEL (level); + elt->prev = list->freelists[freelist_level]; + list->freelists[freelist_level] = elt; } /* |