src/gallium/state_trackers/nine/nine_helpers.c

   1 /*
   2  * Copyright 2013 Christoph Bumiller
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * on the rights to use, copy, modify, merge, publish, distribute, sub
   8  * license, and/or sell copies of the Software, and to permit persons to whom
   9  * the Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
  18  * THE AUTHOR(S) AND/OR THEIR SUPPLIERS BE LIABLE FOR ANY CLAIM,
  19  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
  20  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
  21  * USE OR OTHER DEALINGS IN THE SOFTWARE. */
  22
  23 #include "nine_helpers.h"
  24
  25 static struct nine_range *
  26 nine_range_pool_more(struct nine_range_pool *pool)
  27 {
  28     struct nine_range *r = MALLOC(64 * sizeof(struct nine_range));
  29     int i;
  30     assert(!pool->free);
  31
  32     if (pool->num_slabs == pool->num_slabs_max) {
  33         unsigned p = pool->num_slabs_max;
  34         unsigned n = pool->num_slabs_max * 2;
  35         if (!n)
  36             n = 4;
  37         pool->slabs = REALLOC(pool->slabs,
  38                               p * sizeof(struct nine_range *),
  39                               n * sizeof(struct nine_range *));
  40         pool->num_slabs_max = n;
  41     }
  42     pool->free = pool->slabs[pool->num_slabs++] = r;
  43
  44     for (i = 0; i < 63; ++i, r = r->next)
  45         r->next = (struct nine_range *)
  46             ((uint8_t *)r + sizeof(struct nine_range));
  47     r->next = NULL;
  48
  49     return pool->free;
  50 }
  51
  52 static inline struct nine_range *
  53 nine_range_pool_get(struct nine_range_pool *pool, int16_t bgn, int16_t end)
  54 {
  55     struct nine_range *r = pool->free;
  56     if (!r)
  57         r = nine_range_pool_more(pool);
  58     assert(r);
  59     pool->free = r->next;
  60     r->bgn = bgn;
  61     r->end = end;
  62     return r;
  63 }
  64
  65 static inline void
  66 nine_ranges_coalesce(struct nine_range *r, struct nine_range_pool *pool)
  67 {
  68     struct nine_range *n;
  69
  70     while (r->next && r->end >= r->next->bgn) {
  71         n = r->next->next;
  72         r->end = (r->end >= r->next->end) ? r->end : r->next->end;
  73         nine_range_pool_put(pool, r->next);
  74         r->next = n;
  75     }
  76 }
  77
  78 void
  79 nine_ranges_insert(struct nine_range **head, int16_t bgn, int16_t end,
  80                    struct nine_range_pool *pool)
  81 {
  82     struct nine_range *r, **pn = head;
  83
  84     for (r = *head; r && bgn > r->end; pn = &r->next, r = r->next);
  85
  86     if (!r || end < r->bgn) {
  87         *pn = nine_range_pool_get(pool, bgn, end);
  88         (*pn)->next = r;
  89     } else
  90     if (bgn < r->bgn) {
  91         r->bgn = bgn;
  92         if (end > r->end)
  93             r->end = end;
  94         nine_ranges_coalesce(r, pool);
  95     } else
  96     if (end > r->end) {
  97         r->end = end;
  98         nine_ranges_coalesce(r, pool);
  99     }
 100 }