def __init__(self, config, chunk_size=DEFAULT_CHUNK_SIZE,
                 nursery_size=128,
                 min_nursery_size=128,
                 auto_nursery_size=False,
                 space_size=4096,
                 max_space_size=sys.maxint//2+1):
        SemiSpaceGC.__init__(self, config, chunk_size = chunk_size,
                             space_size = space_size,
                             max_space_size = max_space_size)
        assert min_nursery_size <= nursery_size <= space_size // 2
        self.initial_nursery_size = nursery_size
        self.auto_nursery_size = auto_nursery_size
        self.min_nursery_size = min_nursery_size

        # define nursery fields
        self.reset_nursery()
        self._setup_wb()

        # compute the constant lower bounds for the attributes
        # largest_young_fixedsize and largest_young_var_basesize.
        # It is expected that most (or all) objects have a fixedsize
        # that is much lower anyway.
        sz = self.get_young_fixedsize(self.min_nursery_size)
        self.lb_young_fixedsize = sz
        sz = self.get_young_var_basesize(self.min_nursery_size)
        self.lb_young_var_basesize = sz

    def __init__(self, chunk_size=DEFAULT_CHUNK_SIZE,
                 nursery_size=128,
                 min_nursery_size=128,
                 auto_nursery_size=False,
                 space_size=4096,
                 max_space_size=sys.maxint//2+1):
        SemiSpaceGC.__init__(self, chunk_size = chunk_size,
                             space_size = space_size,
                             max_space_size = max_space_size)
        assert min_nursery_size <= nursery_size <= space_size // 2
        self.initial_nursery_size = nursery_size
        self.auto_nursery_size = auto_nursery_size
        self.min_nursery_size = min_nursery_size
        self.old_objects_pointing_to_young = self.AddressStack()
        # ^^^ a list of addresses inside the old objects space; it
        # may contain static prebuilt objects as well.  More precisely,
        # it lists exactly the old and static objects whose
        # GCFLAG_NO_YOUNG_PTRS bit is not set.
        self.young_objects_with_weakrefs = self.AddressStack()
        self.reset_nursery()

        # compute the constant lower bounds for the attributes
        # largest_young_fixedsize and largest_young_var_basesize.
        # It is expected that most (or all) objects have a fixedsize
        # that is much lower anyway.
        sz = self.get_young_fixedsize(self.min_nursery_size)
        self.lb_young_fixedsize = sz
        sz = self.get_young_var_basesize(self.min_nursery_size)
        self.lb_young_var_basesize = sz

 def semispace_collect(self, size_changing=False):
     self.reset_young_gcflags() # we are doing a full collection anyway
     self.weakrefs_grow_older()
     self.reset_nursery()
     if DEBUG_PRINT:
         llop.debug_print(lltype.Void, "major collect, size changing", size_changing)
     SemiSpaceGC.semispace_collect(self, size_changing)
     if DEBUG_PRINT and not size_changing:
         llop.debug_print(lltype.Void, "percent survived", float(self.free - self.tospace) / self.space_size)

 def setup(self):
     SemiSpaceGC.setup(self)
     self.set_nursery_size(self.initial_nursery_size)
     # the GC is fully setup now.  The rest can make use of it.
     if self.auto_nursery_size:
         newsize = nursery_size_from_env()
         if newsize <= 0:
             newsize = estimate_best_nursery_size()
         if newsize > 0:
             self.set_nursery_size(newsize)

 def debug_check_consistency(self):
     if self.DEBUG:
         self._d_oopty = self.old_objects_pointing_to_young.stack2dict()
         self._d_lgro = self.last_generation_root_objects.stack2dict()
         SemiSpaceGC.debug_check_consistency(self)
         self._d_oopty.delete()
         self._d_lgro.delete()
         self.old_objects_pointing_to_young.foreach(
             self._debug_check_flag_1, None)
         self.last_generation_root_objects.foreach(
             self._debug_check_flag_2, None)

 def setup(self):
     self.last_generation_root_objects = self.AddressStack()
     self.young_objects_with_id = self.AddressDict()
     SemiSpaceGC.setup(self)
     self.set_nursery_size(self.initial_nursery_size)
     # the GC is fully setup now.  The rest can make use of it.
     if self.auto_nursery_size:
         newsize = nursery_size_from_env()
         if newsize <= 0:
             newsize = estimate_best_nursery_size(
                 self.config.gcconfig.debugprint)
         if newsize > 0:
             self.set_nursery_size(newsize)

 def malloc_fixedsize_clear(self, typeid, size, can_collect,
                            has_finalizer=False, contains_weakptr=False):
     if (has_finalizer or not can_collect or
         (raw_malloc_usage(size) > self.lb_young_var_basesize and
          raw_malloc_usage(size) > self.largest_young_fixedsize)):
         # ^^^ we do two size comparisons; the first one appears redundant,
         #     but it can be constant-folded if 'size' is a constant; then
         #     it almost always folds down to False, which kills the
         #     second comparison as well.
         ll_assert(not contains_weakptr, "wrong case for mallocing weakref")
         # "non-simple" case or object too big: don't use the nursery
         return SemiSpaceGC.malloc_fixedsize_clear(self, typeid, size,
                                                   can_collect,
                                                   has_finalizer,
                                                   contains_weakptr)
     size_gc_header = self.gcheaderbuilder.size_gc_header
     totalsize = size_gc_header + size
     result = self.nursery_free
     if raw_malloc_usage(totalsize) > self.nursery_top - result:
         result = self.collect_nursery()
     llarena.arena_reserve(result, totalsize)
     # GCFLAG_NO_YOUNG_PTRS is never set on young objs
     self.init_gc_object(result, typeid, flags=0)
     self.nursery_free = result + totalsize
     if contains_weakptr:
         self.young_objects_with_weakrefs.append(result + size_gc_header)
     return llmemory.cast_adr_to_ptr(result+size_gc_header, llmemory.GCREF)

 def make_a_copy(self, obj, objsize):
     # During a full collect, all copied objects might implicitly come
     # from the nursery.  If they do, we must add the GCFLAG_NO_YOUNG_PTRS.
     # If they don't, we count how many times they are copied and when
     # some threshold is reached we make the copy a non-movable "external"
     # object.  The threshold is MAX_SEMISPACE_AGE.
     tid = self.header(obj).tid
     # XXX the following logic is not doing exactly what is explained
     # above: any object without GCFLAG_NO_YOUNG_PTRS has its age not
     # incremented.  This is accidental: it means that objects that
     # are very often modified to point to young objects don't reach
     # the 3rd generation.  For now I'll leave it this way because
     # I'm not sure that it's a bad thing.
     if not (tid & GCFLAG_NO_YOUNG_PTRS):
         tid |= GCFLAG_NO_YOUNG_PTRS    # object comes from the nursery
     elif (tid & GCFLAG_AGE_MASK) < GCFLAG_AGE_MAX:
         tid += GCFLAG_AGE_ONE
     else:
         newobj = self.make_a_nonmoving_copy(obj, objsize)
         if newobj:
             return newobj
         tid &= ~GCFLAG_AGE_MASK
     # skip GenerationGC.make_a_copy() as we already did the right
     # thing about GCFLAG_NO_YOUNG_PTRS
     newobj = SemiSpaceGC.make_a_copy(self, obj, objsize)
     self.header(newobj).tid = tid
     return newobj

 def _compute_id(self, obj):
     if self.is_in_nursery(obj):
         result = self.young_objects_with_id.get(obj)
         if not result:
             result = self._next_id()
             self.young_objects_with_id.setitem(obj, result)
         return result
     else:
         return SemiSpaceGC._compute_id(self, obj)

 def coalloc_varsize_clear(self, coallocator, typeid,
                           length, size, itemsize,
                           offset_to_length):
     if self.is_in_nursery(coallocator):
         return self.malloc_varsize_clear(typeid, length, size, itemsize,
                                          offset_to_length, True, False)
     else:
         return SemiSpaceGC.malloc_varsize_clear(self, typeid, length, size,
                                                 itemsize, offset_to_length,
                                                 True, False)

 def debug_check_object(self, obj):
     """Check the invariants about 'obj' that should be true
     between collections."""
     SemiSpaceGC.debug_check_object(self, obj)
     tid = self.header(obj).tid
     if tid & GCFLAG_NO_YOUNG_PTRS:
         ll_assert(not self.is_in_nursery(obj),
                   "nursery object with GCFLAG_NO_YOUNG_PTRS")
         self.trace(obj, self._debug_no_nursery_pointer, None)
     elif not self.is_in_nursery(obj):
         ll_assert(self._d_oopty.contains(obj),
                   "missing from old_objects_pointing_to_young")
     if tid & GCFLAG_NO_HEAP_PTRS:
         ll_assert(self.is_last_generation(obj),
                   "GCFLAG_NO_HEAP_PTRS on non-3rd-generation object")
         self.trace(obj, self._debug_no_gen1or2_pointer, None)
     elif self.is_last_generation(obj):
         ll_assert(self._d_lgro.contains(obj),
                   "missing from last_generation_root_objects")

 def coalloc_fixedsize_clear(self, coallocator, typeid, size):
     # note: a coallocated object can never return a weakref, since the
     # coallocation analysis is done at a time where weakrefs are
     # represented as opaque objects which aren't allocated using malloc but
     # with weakref_create
     if self.is_in_nursery(coallocator):
         return self.malloc_fixedsize_clear(typeid, size,
                                            True, False, False)
     else:
         return SemiSpaceGC.malloc_fixedsize_clear(self, typeid, size,
                                                   True, False, False)

    def setup(self):
        self.old_objects_pointing_to_young = self.AddressStack()
        # ^^^ a list of addresses inside the old objects space; it
        # may contain static prebuilt objects as well.  More precisely,
        # it lists exactly the old and static objects whose
        # GCFLAG_NO_YOUNG_PTRS bit is not set.
        self.young_objects_with_weakrefs = self.AddressStack()

        self.last_generation_root_objects = self.AddressStack()
        self.young_objects_with_id = self.AddressDict()
        SemiSpaceGC.setup(self)
        self.set_nursery_size(self.initial_nursery_size)
        # the GC is fully setup now.  The rest can make use of it.
        if self.auto_nursery_size:
            newsize = nursery_size_from_env()
            if newsize <= 0:
                newsize = estimate_best_nursery_size()
            if newsize > 0:
                self.set_nursery_size(newsize)

        self.reset_nursery()

    def malloc_varsize_clear(self, typeid, length, size, itemsize,
                             offset_to_length, can_collect,
                             has_finalizer=False):
        # Only use the nursery if there are not too many items.
        if not raw_malloc_usage(itemsize):
            too_many_items = False
        else:
            # The following line is usually constant-folded because both
            # min_nursery_size and itemsize are constants (the latter
            # due to inlining).
            maxlength_for_minimal_nursery = (self.min_nursery_size // 4 //
                                             raw_malloc_usage(itemsize))
            
            # The actual maximum length for our nursery depends on how
            # many times our nursery is bigger than the minimal size.
            # The computation is done in this roundabout way so that
            # only the only remaining computation is the following
            # shift.
            maxlength = maxlength_for_minimal_nursery << self.nursery_scale
            too_many_items = length > maxlength

        if (has_finalizer or not can_collect or
            too_many_items or
            (raw_malloc_usage(size) > self.lb_young_var_basesize and
             raw_malloc_usage(size) > self.largest_young_var_basesize)):
            # ^^^ we do two size comparisons; the first one appears redundant,
            #     but it can be constant-folded if 'size' is a constant; then
            #     it almost always folds down to False, which kills the
            #     second comparison as well.
            return SemiSpaceGC.malloc_varsize_clear(self, typeid, length, size,
                                                    itemsize, offset_to_length,
                                                    can_collect, has_finalizer)
        # with the above checks we know now that totalsize cannot be more
        # than about half of the nursery size; in particular, the + and *
        # cannot overflow
        size_gc_header = self.gcheaderbuilder.size_gc_header
        totalsize = size_gc_header + size + itemsize * length
        result = self.nursery_free
        if raw_malloc_usage(totalsize) > self.nursery_top - result:
            result = self.collect_nursery()
        llarena.arena_reserve(result, totalsize)
        # GCFLAG_NO_YOUNG_PTRS is never set on young objs
        self.init_gc_object(result, typeid, flags=0)
        (result + size_gc_header + offset_to_length).signed[0] = length
        self.nursery_free = result + llarena.round_up_for_allocation(totalsize)
        return llmemory.cast_adr_to_ptr(result+size_gc_header, llmemory.GCREF)

    def malloc_varsize_clear(self, typeid, length, size, itemsize,
                             offset_to_length, can_collect,
                             has_finalizer=False):
        if has_finalizer or not can_collect:
            return SemiSpaceGC.malloc_varsize_clear(self, typeid, length, size,
                                                    itemsize, offset_to_length,
                                                    can_collect, has_finalizer)
        size_gc_header = self.gcheaderbuilder.size_gc_header
        nonvarsize = size_gc_header + size

        # Compute the maximal length that makes the object still
        # below 'nonlarge_max'.  All the following logic is usually
        # constant-folded because self.nonlarge_max, size and itemsize
        # are all constants (the arguments are constant due to
        # inlining) and self.has_gcptr_in_varsize() is constant-folded.
        if self.has_gcptr_in_varsize(typeid):
            nonlarge_max = self.nonlarge_gcptrs_max
        else:
            nonlarge_max = self.nonlarge_max

        if not raw_malloc_usage(itemsize):
            too_many_items = raw_malloc_usage(nonvarsize) > nonlarge_max
        else:
            maxlength = nonlarge_max - raw_malloc_usage(nonvarsize)
            maxlength = maxlength // raw_malloc_usage(itemsize)
            too_many_items = length > maxlength

        if not too_many_items:
            # With the above checks we know now that totalsize cannot be more
            # than 'nonlarge_max'; in particular, the + and * cannot overflow.
            # Let's try to fit the object in the nursery.
            totalsize = nonvarsize + itemsize * length
            result = self.nursery_free
            if raw_malloc_usage(totalsize) <= self.nursery_top - result:
                llarena.arena_reserve(result, totalsize)
                # GCFLAG_NO_YOUNG_PTRS is never set on young objs
                self.init_gc_object(result, typeid, flags=0)
                (result + size_gc_header + offset_to_length).signed[0] = length
                self.nursery_free = result + llarena.round_up_for_allocation(
                    totalsize)
                return llmemory.cast_adr_to_ptr(result+size_gc_header,
                                                llmemory.GCREF)
        return self.malloc_varsize_slowpath(typeid, length)

 def make_a_copy(self, obj, objsize):
     newobj = SemiSpaceGC.make_a_copy(self, obj, objsize)
     # During a full collect, all copied objects might implicitly come
     # from the nursery.  In case they do, we must add this flag:
     self.header(newobj).tid |= GCFLAG_NO_YOUNG_PTRS
     return newobj

 def enumerate_all_roots(self, callback, arg):
     self.last_generation_root_objects.foreach(callback, arg)
     SemiSpaceGC.enumerate_all_roots(self, callback, arg)

 def collect(self, gen=1):
     if gen == 0:
         self.collect_nursery()
     else:
         SemiSpaceGC.collect(self)

 def trace_and_copy(self, obj):
     # during a full collect, all objects copied might come from the nursery and
     # so must have this flag set:
     self.header(obj).tid |= GCFLAG_NO_YOUNG_PTRS
     SemiSpaceGC.trace_and_copy(self, obj)

 def semispace_collect(self, size_changing=False):
     self.reset_young_gcflags() # we are doing a full collection anyway
     self.weakrefs_grow_older()
     self.ids_grow_older()
     self.reset_nursery()
     SemiSpaceGC.semispace_collect(self, size_changing)