Home | History | Annotate | Download | only in nine 
      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 }
    101