/*
 * Copyright © 2006 Keith Packard
 * Copyright © 2006 Carl Worth
 *
 * Permission to use, copy, modify, distribute, and sell this software and its
 * documentation for any purpose is hereby granted without fee, provided that
 * the above copyright notice appear in all copies and that both that copyright
 * notice and this permission notice appear in supporting documentation, and
 * that the name of the copyright holders not be used in advertising or
 * publicity pertaining to distribution of the software without specific,
 * written prior permission.  The copyright holders make no representations
 * about the suitability of this software for any purpose.  It is provided "as
 * is" without express or implied warranty.
 *
 * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
 * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
 * OF THIS SOFTWARE.
 */

#ifndef SKIPLIST_H
#define SKIPLIST_H

#include "cairoint.h"

/*
 * Skip lists are described in detail here:
 *
 *   http://citeseer.ist.psu.edu/pugh90skip.html
 */

/* 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
 * generate a structure for list elements that has as its final member
 * a skip_elt_t, (which will be allocated with variable size).
 *
 * The caller must also pass the size of the structure to
 * _cairo_skip_list_init.
 */
typedef struct _skip_elt {
    int prev_index;
    struct _skip_elt *prev;
    struct _skip_elt *next[1];
} skip_elt_t;

#define SKIP_LIST_ELT_TO_DATA(type, elt) ((type *) ((char *) (elt) - (sizeof (type) - sizeof (skip_elt_t))))

typedef int
(*cairo_skip_list_compare_t) (void *list, void *a, void *b);

typedef struct _skip_list {
    cairo_skip_list_compare_t compare;
    size_t elt_size;
    size_t data_size;
    skip_elt_t *chains[MAX_LEVEL];
    skip_elt_t *freelists[MAX_FREELIST_LEVEL];
    int		max_level;
} cairo_skip_list_t;

/* Initialize a new skip list. The compare function accepts a pointer
 * to the list as well as pointers to two elements. The function must
 * return a value greater than zero, zero, or less then 0 if the first
 * element is considered respectively greater than, equal to, or less
 * than the second element. The size of each object, (as computed by
 * sizeof) is passed for elt_size. Note that the structure used for
 * list elements must have as its final member a skip_elt_t
 */
cairo_private void
_cairo_skip_list_init (cairo_skip_list_t		*list,
		cairo_skip_list_compare_t	 compare,
		size_t			 elt_size);


/* Deallocate resources associated with a skip list and all elements
 * in it. (XXX: currently this simply deletes all elements.)
 */
cairo_private void
_cairo_skip_list_fini (cairo_skip_list_t		*list);

/* Insert a new element into the list at the correct sort order as
 * determined by compare. If unique is true, then duplicate elements
 * are ignored and the already inserted element is returned.
 * Otherwise data will be copied (elt_size bytes from <data> via
 * memcpy) and the new element is returned. */
cairo_private void *
_cairo_skip_list_insert (cairo_skip_list_t *list, void *data, int unique);

/* Find an element which compare considers equal to <data> */
cairo_private void *
_cairo_skip_list_find (cairo_skip_list_t *list, void *data);

/* Delete an element which compare considers equal to <data> */
cairo_private void
_cairo_skip_list_delete (cairo_skip_list_t *list, void *data);

/* Delete the given element from the list. */
cairo_private void
_cairo_skip_list_delete_given (cairo_skip_list_t *list, skip_elt_t *given);

#endif