cairo/src/cairo-skiplist-private.h

   1 /*
   2  * Copyright © 2006 Keith Packard
   3  * Copyright © 2006 Carl Worth
   4  *
   5  * Permission to use, copy, modify, distribute, and sell this software and its
   6  * documentation for any purpose is hereby granted without fee, provided that
   7  * the above copyright notice appear in all copies and that both that copyright
   8  * notice and this permission notice appear in supporting documentation, and
   9  * that the name of the copyright holders not be used in advertising or
  10  * publicity pertaining to distribution of the software without specific,
  11  * written prior permission.  The copyright holders make no representations
  12  * about the suitability of this software for any purpose.  It is provided "as
  13  * is" without express or implied warranty.
  14  *
  15  * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  16  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  17  * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  18  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
  19  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  20  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
  21  * OF THIS SOFTWARE.
  22  */
  23
  24 #ifndef SKIPLIST_H
  25 #define SKIPLIST_H
  26
  27 #include "cairoint.h"
  28
  29 /*
  30  * Skip lists are described in detail here:
  31  *
  32  *   http://citeseer.ist.psu.edu/pugh90skip.html
  33  */
  34
  35 /* Note that random_level() called from alloc_node_for_level() depends on
  36  * this being not more than 16.
  37  */
  38 #define MAX_LEVEL   15
  39
  40 /* Returns the index of the free-list to use for a node at level 'level' */
  41 #define FREELIST_FOR_LEVEL(level) (((level) - 1) / 2)
  42
  43 /* Returns the maximum level that uses the same free-list as 'level' does */
  44 #define FREELIST_MAX_LEVEL_FOR(level) (((level) + 1) & ~1)
  45
  46 #define MAX_FREELIST_LEVEL (FREELIST_FOR_LEVEL (MAX_LEVEL - 1) + 1)
  47
  48 /*
  49  * Skip list element. In order to use the skip list, the caller must
  50  * generate a structure for list elements that has as its final member
  51  * a skip_elt_t, (which will be allocated with variable size).
  52  *
  53  * The caller must also pass the size of the structure to
  54  * _cairo_skip_list_init.
  55  */
  56 typedef struct _skip_elt {
  57     int prev_index;
  58     struct _skip_elt *prev;
  59     struct _skip_elt *next[1];
  60 } skip_elt_t;
  61
  62 #define SKIP_LIST_ELT_TO_DATA(type, elt) ((type *) ((char *) (elt) - (sizeof (type) - sizeof (skip_elt_t))))
  63
  64 typedef int
  65 (*cairo_skip_list_compare_t) (void *list, void *a, void *b);
  66
  67 typedef struct _skip_list {
  68     cairo_skip_list_compare_t compare;
  69     size_t elt_size;
  70     size_t data_size;
  71     skip_elt_t *chains[MAX_LEVEL];
  72     skip_elt_t *freelists[MAX_FREELIST_LEVEL];
  73     int         max_level;
  74 } cairo_skip_list_t;
  75
  76 /* Initialize a new skip list. The compare function accepts a pointer
  77  * to the list as well as pointers to two elements. The function must
  78  * return a value greater than zero, zero, or less then 0 if the first
  79  * element is considered respectively greater than, equal to, or less
  80  * than the second element. The size of each object, (as computed by
  81  * sizeof) is passed for elt_size. Note that the structure used for
  82  * list elements must have as its final member a skip_elt_t
  83  */
  84 cairo_private void
  85 _cairo_skip_list_init (cairo_skip_list_t                *list,
  86                 cairo_skip_list_compare_t        compare,
  87                 size_t                   elt_size);
  88
  89
  90 /* Deallocate resources associated with a skip list and all elements
  91  * in it. (XXX: currently this simply deletes all elements.)
  92  */
  93 cairo_private void
  94 _cairo_skip_list_fini (cairo_skip_list_t                *list);
  95
  96 /* Insert a new element into the list at the correct sort order as
  97  * determined by compare. If unique is true, then duplicate elements
  98  * are ignored and the already inserted element is returned.
  99  * Otherwise data will be copied (elt_size bytes from <data> via
 100  * memcpy) and the new element is returned. */
 101 cairo_private void *
 102 _cairo_skip_list_insert (cairo_skip_list_t *list, void *data, int unique);
 103
 104 /* Find an element which compare considers equal to <data> */
 105 cairo_private void *
 106 _cairo_skip_list_find (cairo_skip_list_t *list, void *data);
 107
 108 /* Delete an element which compare considers equal to <data> */
 109 cairo_private void
 110 _cairo_skip_list_delete (cairo_skip_list_t *list, void *data);
 111
 112 /* Delete the given element from the list. */
 113 cairo_private void
 114 _cairo_skip_list_delete_given (cairo_skip_list_t *list, skip_elt_t *given);
 115
 116 #endif