src/cairo-skiplist.c

   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 #include "cairoint.h"
  25
  26 #include "cairo-skiplist-private.h"
  27
  28 #if HAVE_FFS
  29 #include <strings.h> /* ffs() */
  30 #endif
  31
  32 #define ELT_DATA(elt) (void *)  ((char*) (elt) - list->data_size)
  33 #define NEXT_TO_ELT(next)       (skip_elt_t *) ((char *) (next) - offsetof (skip_elt_t, next))
  34
  35 static uint32_t
  36 hars_petruska_f54_1_random (void)
  37 {
  38 #  define rol(x,k) ((x << k) | (x >> (32-k)))
  39     static uint32_t x = 0;
  40     x = (x ^ rol(x, 5) ^ rol(x, 24)) + 0x37798849;
  41     return x;
  42 #  undef rol
  43 }
  44
  45 struct pool {
  46     struct pool *next;
  47     char *ptr;
  48     unsigned int rem;
  49 };
  50
  51 static struct pool *
  52 pool_new (void)
  53 {
  54     struct pool *pool;
  55
  56     pool = malloc (8192 - 8);
  57     if (unlikely (pool == NULL))
  58         return NULL;
  59
  60     pool->next = NULL;
  61     pool->rem = 8192 - 8 - sizeof (struct pool);
  62     pool->ptr = (char *) (pool + 1);
  63
  64     return pool;
  65 }
  66
  67 static void
  68 pools_destroy (struct pool *pool)
  69 {
  70     while (pool->next != NULL) {
  71         struct pool *next = pool->next;
  72         free (pool);
  73         pool = next;
  74     }
  75 }
  76
  77 /*
  78  * Initialize an empty skip list
  79  */
  80 void
  81 _cairo_skip_list_init (cairo_skip_list_t        *list,
  82                        cairo_skip_list_compare_t compare,
  83                        size_t                    elt_size)
  84 {
  85     int i;
  86
  87     list->compare = compare;
  88     list->elt_size = elt_size;
  89     list->data_size = elt_size - sizeof (skip_elt_t);
  90     list->pool = (struct pool *) list->pool_embedded;
  91     list->pool->next = NULL;
  92     list->pool->rem = sizeof (list->pool_embedded) - sizeof (struct pool);
  93     list->pool->ptr = list->pool_embedded + sizeof (struct pool);
  94
  95     for (i = 0; i < MAX_LEVEL; i++) {
  96         list->chains[i] = NULL;
  97     }
  98
  99     for (i = 0; i < MAX_FREELIST_LEVEL; i++) {
 100         list->freelists[i] = NULL;
 101     }
 102
 103     list->max_level = 0;
 104 }
 105
 106 void
 107 _cairo_skip_list_fini (cairo_skip_list_t *list)
 108 {
 109     pools_destroy (list->pool);
 110 }
 111
 112 /*
 113  * Generate a random level number, distributed
 114  * so that each level is 1/4 as likely as the one before
 115  *
 116  * Note that level numbers run 1 <= level < MAX_LEVEL
 117  */
 118 static int
 119 random_level (void)
 120 {
 121     /* tricky bit -- each bit is '1' 75% of the time.
 122      * This works because we only use the lower MAX_LEVEL
 123      * bits, and MAX_LEVEL < 16 */
 124     uint32_t bits = hars_petruska_f54_1_random ();
 125 #if HAVE_FFS
 126     return ffs (-(1<<MAX_LEVEL) | bits | bits >> 16);
 127 #else
 128     int level = 1;
 129
 130     bits |= -(1<<MAX_LEVEL) | bits >> 16;
 131     while ((bits & 1) == 0) {
 132         level++;
 133         bits >>= 1;
 134     }
 135     return level;
 136 #endif
 137 }
 138
 139 static void *
 140 pool_alloc (cairo_skip_list_t *list,
 141             unsigned int level)
 142 {
 143     unsigned int size;
 144     struct pool *pool;
 145     void *ptr;
 146
 147     size = list->elt_size +
 148         (FREELIST_MAX_LEVEL_FOR (level) - 1) * sizeof (skip_elt_t *);
 149
 150     pool = list->pool;
 151     if (size > pool->rem) {
 152         pool = pool_new ();
 153         if (unlikely (pool == NULL))
 154             return NULL;
 155
 156         pool->next = list->pool;
 157         list->pool = pool;
 158     }
 159
 160     ptr = pool->ptr;
 161     pool->ptr += size;
 162     pool->rem -= size;
 163
 164     return ptr;
 165 }
 166
 167 static void *
 168 alloc_node_for_level (cairo_skip_list_t *list, unsigned level)
 169 {
 170     int freelist_level = FREELIST_FOR_LEVEL (level);
 171     if (list->freelists[freelist_level]) {
 172         skip_elt_t *elt = list->freelists[freelist_level];
 173         list->freelists[freelist_level] = elt->prev;
 174         return ELT_DATA(elt);
 175     }
 176     return pool_alloc (list, level);
 177 }
 178
 179 static void
 180 free_elt (cairo_skip_list_t *list, skip_elt_t *elt)
 181 {
 182     int level = elt->prev_index + 1;
 183     int freelist_level = FREELIST_FOR_LEVEL (level);
 184     elt->prev = list->freelists[freelist_level];
 185     list->freelists[freelist_level] = elt;
 186 }
 187
 188 /*
 189  * Insert 'data' into the list
 190  */
 191 void *
 192 _cairo_skip_list_insert (cairo_skip_list_t *list, void *data, int unique)
 193 {
 194     skip_elt_t **update[MAX_LEVEL];
 195     skip_elt_t *prev[MAX_LEVEL];
 196     char *data_and_elt;
 197     skip_elt_t *elt, **next;
 198     int     i, level, prev_index;
 199
 200     /*
 201      * Find links along each chain
 202      */
 203     elt = NULL;
 204     next = list->chains;
 205     for (i = list->max_level; --i >= 0; )
 206     {
 207         if (elt != next[i])
 208         {
 209             for (; (elt = next[i]); next = elt->next)
 210             {
 211                 int cmp = list->compare (list, ELT_DATA(elt), data);
 212                 if (unique && 0 == cmp)
 213                     return ELT_DATA(elt);
 214                 if (cmp > 0)
 215                     break;
 216             }
 217         }
 218         update[i] = next;
 219         if (next != list->chains)
 220             prev[i] = NEXT_TO_ELT (next);
 221         else
 222             prev[i] = NULL;
 223     }
 224     level = random_level ();
 225     prev_index = level - 1;
 226
 227     /*
 228      * Create new list element
 229      */
 230     if (level > list->max_level)
 231     {
 232         level = list->max_level + 1;
 233         prev_index = level - 1;
 234         prev[prev_index] = NULL;
 235         update[list->max_level] = list->chains;
 236         list->max_level = level;
 237     }
 238
 239     data_and_elt = alloc_node_for_level (list, level);
 240     if (unlikely (data_and_elt == NULL)) {
 241         _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
 242         return NULL;
 243     }
 244
 245     memcpy (data_and_elt, data, list->data_size);
 246     elt = (skip_elt_t *) (data_and_elt + list->data_size);
 247
 248     elt->prev_index = prev_index;
 249     elt->prev = prev[prev_index];
 250
 251     /*
 252      * Insert into all chains
 253      */
 254     for (i = 0; i < level; i++)
 255     {
 256         elt->next[i] = update[i][i];
 257         if (elt->next[i] && elt->next[i]->prev_index == i)
 258             elt->next[i]->prev = elt;
 259         update[i][i] = elt;
 260     }
 261
 262     return data_and_elt;
 263 }
 264
 265 void *
 266 _cairo_skip_list_find (cairo_skip_list_t *list, void *data)
 267 {
 268     int i;
 269     skip_elt_t **next = list->chains;
 270     skip_elt_t *elt;
 271
 272     /*
 273      * Walk chain pointers one level at a time
 274      */
 275     for (i = list->max_level; --i >= 0;)
 276         while (next[i] && list->compare (list, data, ELT_DATA(next[i])) > 0)
 277         {
 278             next = next[i]->next;
 279         }
 280     /*
 281      * Here we are
 282      */
 283     elt = next[0];
 284     if (elt && list->compare (list, data, ELT_DATA (elt)) == 0)
 285         return ELT_DATA (elt);
 286
 287     return NULL;
 288 }
 289
 290 void
 291 _cairo_skip_list_delete (cairo_skip_list_t *list, void *data)
 292 {
 293     skip_elt_t **update[MAX_LEVEL], *prev[MAX_LEVEL];
 294     skip_elt_t *elt, **next;
 295     int i;
 296
 297     /*
 298      * Find links along each chain
 299      */
 300     next = list->chains;
 301     for (i = list->max_level; --i >= 0; )
 302     {
 303         for (; (elt = next[i]); next = elt->next)
 304         {
 305             if (list->compare (list, ELT_DATA (elt), data) >= 0)
 306                 break;
 307         }
 308         update[i] = &next[i];
 309         if (next == list->chains)
 310             prev[i] = NULL;
 311         else
 312             prev[i] = NEXT_TO_ELT (next);
 313     }
 314     elt = next[0];
 315     assert (list->compare (list, ELT_DATA (elt), data) == 0);
 316     for (i = 0; i < list->max_level && *update[i] == elt; i++) {
 317         *update[i] = elt->next[i];
 318         if (elt->next[i] && elt->next[i]->prev_index == i)
 319             elt->next[i]->prev = prev[i];
 320     }
 321     while (list->max_level > 0 && list->chains[list->max_level - 1] == NULL)
 322         list->max_level--;
 323     free_elt (list, elt);
 324 }
 325
 326 void
 327 _cairo_skip_list_delete_given (cairo_skip_list_t *list, skip_elt_t *given)
 328 {
 329     skip_elt_t **update[MAX_LEVEL], *prev[MAX_LEVEL];
 330     skip_elt_t *elt, **next;
 331     int i;
 332
 333     /*
 334      * Find links along each chain
 335      */
 336     if (given->prev)
 337         next = given->prev->next;
 338     else
 339         next = list->chains;
 340     for (i = given->prev_index + 1; --i >= 0; )
 341     {
 342         for (; (elt = next[i]); next = elt->next)
 343         {
 344             if (elt == given)
 345                 break;
 346         }
 347         update[i] = &next[i];
 348         if (next == list->chains)
 349             prev[i] = NULL;
 350         else
 351             prev[i] = NEXT_TO_ELT (next);
 352     }
 353     elt = next[0];
 354     assert (elt == given);
 355     for (i = 0; i < (given->prev_index + 1) && *update[i] == elt; i++) {
 356         *update[i] = elt->next[i];
 357         if (elt->next[i] && elt->next[i]->prev_index == i)
 358             elt->next[i]->prev = prev[i];
 359     }
 360     while (list->max_level > 0 && list->chains[list->max_level - 1] == NULL)
 361         list->max_level--;
 362     free_elt (list, elt);
 363 }
 364
 365 #if MAIN
 366 typedef struct {
 367     int n;
 368     skip_elt_t elt;
 369 } test_elt_t;
 370
 371 static int
 372 test_cmp (void *list, void *A, void *B)
 373 {
 374     const test_elt_t *a = A, *b = B;
 375     return a->n - b->n;
 376 }
 377
 378 int
 379 main (void)
 380 {
 381     cairo_skip_list_t list;
 382     test_elt_t elt;
 383     int n;
 384
 385     _cairo_skip_list_init (&list, test_cmp, sizeof (test_elt_t));
 386     for (n = 0; n < 10000000; n++) {
 387         void *elt_and_data;
 388         elt.n = n;
 389         elt_and_data = _cairo_skip_list_insert (&list, &elt, TRUE);
 390         assert (elt_and_data != NULL);
 391     }
 392     _cairo_skip_list_fini (&list);
 393
 394     return 0;
 395 }
 396
 397 /* required supporting stubs */
 398 cairo_status_t _cairo_error (cairo_status_t status) { return status; }
 399 #endif