Back to index

plt-scheme  4.2.1
page_range.c
Go to the documentation of this file.
00001 
00002 /* 
00003    Provides:
00004     initialize_page_ranges
00005     flush_page_ranges
00006     add_page_range
00007 */
00008 
00009 #define Tree Range
00010 #define Splay_Item(t) (t)->start
00011 #define Set_Splay_Item(t, v) (t)->start = (v)
00012 #define splay range_splay
00013 #define splay_insert range_splay_insert
00014 #define OMIT_SPLAY_DELETE
00015 #include "../utils/splay.c"
00016 #undef splay
00017 #undef splay_insert
00018 #undef OMIT_SPLAY_DELETE
00019 #undef Tree
00020 #undef Splay_Item
00021 #undef Set_Splay_Item
00022 
00023 static void initialize_page_ranges(Page_Range *pr, void *block, unsigned long size)
00024 {
00025   pr->range_root = NULL;
00026   pr->range_start = NULL;
00027   pr->range_alloc_block = block;
00028   pr->range_alloc_size = size;
00029   pr->range_alloc_used = 0;
00030 }
00031 
00032 static void compact_page_ranges(Page_Range *pr)
00033 {
00034   Range *work, *next;
00035   unsigned long start, len;
00036 
00037   for (work = pr->range_start; work; work = next) {
00038     next = work->next;
00039 
00040     start = work->start;
00041     len = work->len;
00042 
00043     /* Collapse adjacent nodes: */
00044     while (next && (next->start == start + len)) {
00045       len += next->len;
00046       next = next->next;
00047     }
00048 
00049     work->start = start;
00050     work->len = len;
00051     work->next = next;
00052   }
00053 }
00054 
00055 static void reset_page_ranges(Page_Range *pr)
00056 {
00057   pr->range_alloc_used = 0;
00058   pr->range_root = NULL;
00059   pr->range_start = NULL;
00060 }
00061 
00062 static int try_extend(Range *r, unsigned long start, unsigned long len)
00063 {
00064   if (!r)
00065     return 0;
00066 
00067   if (r->start == start + len) {
00068     r->start = start;
00069     r->len += len;
00070     return 1;
00071   }
00072   if (r->start + r->len == start) {
00073     r->len += len;
00074     return 1;
00075   }
00076 
00077   return 0;
00078  }
00079 
00080 static int add_page_range(Page_Range *pr, void *_start, unsigned long len, unsigned long alignment)
00081 {
00082   unsigned long start = (unsigned long)_start;
00083   Range *r, *range_root = pr->range_root;
00084 
00085   len += (alignment - 1);
00086   len -= (len & (alignment - 1));
00087 
00088   range_root = range_splay(start, range_root);
00089 
00090   if (range_root) {
00091     if (try_extend(range_root, start, len)
00092         || try_extend(range_root->prev, start, len)
00093         || try_extend(range_root->next, start, len)) {
00094       pr->range_root = range_root;
00095       return 1;
00096     }
00097   }
00098 
00099   r = (Range *)((char *)pr->range_alloc_block + pr->range_alloc_used);
00100   pr->range_alloc_used += sizeof(Range);
00101   if (pr->range_alloc_used > pr->range_alloc_size) {
00102     return 0;
00103   } else {
00104     r->len = len;
00105     if (range_root) {
00106       if (start < range_root->start) {
00107         r->next = range_root;
00108         r->prev = range_root->prev;
00109         if (r->prev)
00110           r->prev->next = r;
00111         else
00112           pr->range_start = r;
00113         range_root->prev = r;
00114       } else {
00115         r->prev = range_root;
00116         r->next = range_root->next;
00117         if (r->next)
00118           r->next->prev = r;
00119         range_root->next = r;
00120       }
00121       range_root = range_splay_insert(start, r, range_root);
00122     } else {
00123       r->prev = r->next = NULL;
00124       r->left = r->right = NULL;
00125       range_root = r;
00126       r->start = start;
00127       pr->range_start = r;
00128     }
00129     pr->range_root = range_root;
00130     return 1;
00131   }
00132 }
00133