Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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.