Back to index

plt-scheme  4.2.1
roots.c
Go to the documentation of this file.
00001 
00002 /* 
00003    Provides:
00004       GC_add_roots
00005       my_qsort
00006       roots, roots_count
00007    Requires:
00008       WORD_SIZE
00009 */
00010 
00011 #define ROOTS_PTR_ALIGNMENT WORD_SIZE
00012 #define ROOTS_PTR_TO_INT(x) ((unsigned long)x)
00013 
00014 static void grow_roots(Roots *roots) {
00015   unsigned long *new_roots;
00016 
00017   roots->size = roots->size ? ( 2 * roots->size ) : 500;
00018   new_roots   = (unsigned long *)ofm_malloc(sizeof(unsigned long) * (roots->size + 1));
00019 
00020   memcpy((void *)new_roots, (void *)roots->roots, sizeof(unsigned long) * roots->count);
00021 
00022   if (roots->roots)
00023     free(roots->roots);
00024 
00025   roots->roots = new_roots;
00026 }
00027 
00028 static int compare_roots(const void *a, const void *b)
00029 {
00030   if (*(unsigned long *)a < *(unsigned long *)b)
00031     return -1;
00032   else
00033     return 1;
00034 }
00035 
00036 static void sort_and_merge_roots(Roots *roots)
00037 {
00038   if (roots->nothing_new)
00039     return;
00040 
00041   if (roots->count < 4)
00042     return;
00043 
00044   my_qsort(roots->roots, roots->count >> 1, 2 * sizeof(unsigned long), compare_roots);
00045 
00046   {
00047     int i;
00048     int offset = 0;
00049     int top = roots->count;
00050     for (i = 2; i < top; i += 2) {
00051       int astart = i - 2 - offset;
00052       int aend   = i - 1 - offset;
00053       int bstart = i;
00054       int bend   = i + 1;
00055       /*|----a----|
00056        *       |----b----| */
00057       if (    (roots->roots[astart] <= roots->roots[bstart])
00058           && ((roots->roots[aend] + (ROOTS_PTR_ALIGNMENT - 1)) >= roots->roots[bstart])) {
00059         /* merge overlapping roots: */
00060         if (roots->roots[bend] > roots->roots[aend])
00061           roots->roots[aend] = roots->roots[bend];
00062         offset += 2;
00063         roots->count -= 2;
00064       } else if (roots->roots[bstart] == roots->roots[bend]) {
00065         /* Remove empty range: */
00066         offset += 2;
00067         roots->count -= 2;
00068       } else if (offset) {
00069         /* compact: */
00070         int emptystart = i - offset;
00071         int emptyend   = i + 1 - offset;
00072         roots->roots[emptystart] = roots->roots[bstart];
00073         roots->roots[emptyend]   = roots->roots[bend];
00074       }
00075     }
00076   }
00077 
00078   roots->nothing_new = 1;
00079 }
00080 
00081 void GC_add_roots(void *start, void *end)
00082 {
00083   GCTYPE *gc = GC_get_GC();
00084   Roots *roots = &gc->roots;
00085 
00086   if (roots->count >= roots->size) {
00087     grow_roots(roots);
00088   }
00089 
00090   roots->roots[roots->count++] = ROOTS_PTR_TO_INT(start);
00091   roots->roots[roots->count++] = ROOTS_PTR_TO_INT(end) - ROOTS_PTR_ALIGNMENT;
00092   roots->nothing_new = 0;
00093 }