def test_simple_access(self):
     AddressStack = get_address_stack()
     addr0 = raw_malloc(llmemory.sizeof(lltype.Signed))
     addr1 = raw_malloc(llmemory.sizeof(lltype.Signed))
     addr2 = raw_malloc(llmemory.sizeof(lltype.Signed))
     ll = AddressStack()
     ll.append(addr0)
     ll.append(addr1)
     ll.append(addr2)
     assert ll.non_empty()
     a = ll.pop()
     assert a == addr2
     assert ll.non_empty()
     a = ll.pop()
     assert a == addr1
     assert ll.non_empty()
     a = ll.pop()
     assert a == addr0
     assert not ll.non_empty()
     ll.append(addr0)
     ll.delete()
     ll = AddressStack()
     ll.append(addr0)
     ll.append(addr1)
     ll.append(addr2)
     ll.append(NULL)
     a = ll.pop()
     assert a == NULL
     ll.delete()
     raw_free(addr2)
     raw_free(addr1)
     raw_free(addr0)

 def f():
     addr = llmemory.raw_malloc(100)
     addr.signed[0] = 12
     (addr + 10).signed[0] = 42
     (addr + 20).char[0] = "a"
     addr1 = llmemory.raw_malloc(100)
     llmemory.raw_memcopy(addr, addr1, 100)
     result = addr1.signed[0] == 12
     result = result and (addr1 + 10).signed[0] == 42
     result = result and (addr1 + 20).char[0] == "a"
     llmemory.raw_free(addr)
     llmemory.raw_free(addr1)
     return result

 def malloc_fixedsize(self, typeid16, size, can_collect,
                      has_finalizer=False, contains_weakptr=False):
     if can_collect:
         self.maybe_collect()
     size_gc_header = self.gcheaderbuilder.size_gc_header
     try:
         tot_size = size_gc_header + size
         usage = raw_malloc_usage(tot_size)
         bytes_malloced = ovfcheck(self.bytes_malloced+usage)
         ovfcheck(self.heap_usage + bytes_malloced)
     except OverflowError:
         raise memoryError
     result = raw_malloc(tot_size)
     if not result:
         raise memoryError
     hdr = llmemory.cast_adr_to_ptr(result, self.HDRPTR)
     hdr.typeid16 = typeid16
     hdr.mark = False
     hdr.flags = '\x00'
     if has_finalizer:
         hdr.next = self.malloced_objects_with_finalizer
         self.malloced_objects_with_finalizer = hdr
     elif contains_weakptr:
         hdr.next = self.objects_with_weak_pointers
         self.objects_with_weak_pointers = hdr
     else:
         hdr.next = self.malloced_objects
         self.malloced_objects = hdr
     self.bytes_malloced = bytes_malloced
     result += size_gc_header
     #llop.debug_print(lltype.Void, 'malloc typeid', typeid16,
     #                 '->', llmemory.cast_adr_to_int(result))
     self.write_malloc_statistics(typeid16, tot_size, result, False)
     return llmemory.cast_adr_to_ptr(result, llmemory.GCREF)

 def malloc_varsize_clear(self, typeid16, length, size, itemsize,
                          offset_to_length, can_collect):
     if can_collect:
         self.maybe_collect()
     size_gc_header = self.gcheaderbuilder.size_gc_header
     try:
         fixsize = size_gc_header + size
         varsize = ovfcheck(itemsize * length)
         tot_size = ovfcheck(fixsize + varsize)
         usage = raw_malloc_usage(tot_size)
         bytes_malloced = ovfcheck(self.bytes_malloced+usage)
         ovfcheck(self.heap_usage + bytes_malloced)
     except OverflowError:
         raise memoryError
     result = raw_malloc(tot_size)
     if not result:
         raise memoryError
     raw_memclear(result, tot_size)        
     (result + size_gc_header + offset_to_length).signed[0] = length
     hdr = llmemory.cast_adr_to_ptr(result, self.HDRPTR)
     hdr.typeid16 = typeid16
     hdr.mark = False
     hdr.flags = '\x00'
     hdr.next = self.malloced_objects
     self.malloced_objects = hdr
     self.bytes_malloced = bytes_malloced
         
     result += size_gc_header
     #llop.debug_print(lltype.Void, 'malloc_varsize length', length,
     #                 'typeid', typeid16,
     #                 '->', llmemory.cast_adr_to_int(result))
     self.write_malloc_statistics(typeid16, tot_size, result, True)
     return llmemory.cast_adr_to_ptr(result, llmemory.GCREF)

 def f():
     adr = llmemory.raw_malloc(sizeofs)
     s = llmemory.cast_adr_to_ptr(adr, STRUCTPTR)
     s.y = 5 # does not crash
     result = (adr + offsety).signed[0] * 10 + int(offsety < sizeofs)
     llmemory.raw_free(adr)
     return result

 def f():
     addr = raw_malloc(INT_SIZE*100)
     ll = AddressStack()
     ll.append(addr)
     ll.append(addr + INT_SIZE*1)
     ll.append(addr + INT_SIZE*2)
     a = ll.pop()
     res = (a - INT_SIZE*2 == addr)
     a = ll.pop()
     res = res and (a - INT_SIZE*1 == addr)
     res = res and ll.non_empty()
     a = ll.pop()
     res = res and a == addr
     res = res and not ll.non_empty()
     ll.append(addr)
     for i in range(300):
         ll.append(addr + INT_SIZE*i)
     for i in range(299, -1, -1):
         a = ll.pop()
         res = res and (a - INT_SIZE*i == addr)
     for i in range(300):
         ll.append(addr + INT_SIZE*i)
     for i in range(299, -1, -1):
         a = ll.pop()
         res = res and (a - INT_SIZE*i == addr)
     ll.delete()
     ll = AddressStack()
     ll.append(addr)
     ll.append(addr + INT_SIZE*1)
     ll.append(addr + INT_SIZE*2)
     ll.delete()
     raw_free(addr)
     return res

 def _emergency_initial_block(self, requested_size):
     # xxx before the GC is fully setup, we might get there.  Hopefully
     # we will only allocate a couple of strings, e.g. in read_from_env().
     # Just allocate them raw and leak them.
     debug_start("gc-initial-block")
     debug_print("leaking", requested_size, "bytes")
     debug_stop("gc-initial-block")
     return llmemory.raw_malloc(requested_size)

 def do_malloc_fixedsize_clear(self, RESTYPE, type_id, size, can_collect,
                               has_finalizer, contains_weakptr):
     assert can_collect
     assert not contains_weakptr
     p = llmemory.raw_malloc(size)
     p = llmemory.cast_adr_to_ptr(p, RESTYPE)
     flags = int(has_finalizer) << 16
     tid = llop.combine_ushort(lltype.Signed, type_id, flags)
     self.record.append(("fixedsize", repr(size), tid, p))
     return p

 def test_remove(self):
     AddressStack = get_address_stack()
     addrs = [raw_malloc(llmemory.sizeof(lltype.Signed))
              for i in range(2200)]
     ll = AddressStack()
     for i in range(2200):
         ll.append(addrs[i])
     ll.remove(addrs[-400])
     expected = range(2200)
     del expected[-400]
     expected.reverse()
     for i in expected:
         a = ll.pop()
         assert a == addrs[i]
     assert not ll.non_empty()

 def test_big_access(self):
     import random
     AddressDeque = get_address_deque(10)
     deque = AddressDeque()
     expected = []
     for i in range(3000):
         assert deque.non_empty() == (len(expected) > 0)
         r = random.random()
         if r < 0.51 and expected:
             x = deque.popleft()
             y = expected.pop(0)
             assert x == y
         else:
             x = raw_malloc(llmemory.sizeof(lltype.Signed))
             deque.append(x)
             expected.append(x)

    def test_foreach(self):
        AddressStack = get_address_stack()
        addrs = [raw_malloc(llmemory.sizeof(lltype.Signed))
                 for i in range(3000)]
        ll = AddressStack()
        for i in range(3000):
            ll.append(addrs[i])

        seen = []

        def callback(addr, fortytwo):
            assert fortytwo == 42
            seen.append(addr)

        ll.foreach(callback, 42)
        assert seen == addrs or seen[::-1] == addrs   # order not guaranteed

    def build_stack_root_iterator(self):
        xxx
        from pypy.rlib.rstack import stack_capture
        sizeofaddr = llmemory.sizeof(llmemory.Address)
        gcdata = self.gcdata
        captured_frame_holder = llmemory.raw_malloc(sizeofaddr)
        captured_frame_holder.address[0] = llmemory.NULL

        class StackRootIterator:
            _alloc_flavor_ = 'raw'

            def setup_root_stack():
                pass
            setup_root_stack = staticmethod(setup_root_stack)

            need_root_stack = False

            def __init__(self):
                # XXX what should be done with the stack_capture()d frames
                # when we are finished?  what about moving GCs?
                frame = llmemory.cast_ptr_to_adr(stack_capture())
                self.static_current = gcdata.static_root_start
                captured_frame_holder.address[0] = frame
                self.finished = False

            def pop(self):
                while self.static_current != gcdata.static_root_end:
                    result = self.static_current
                    self.static_current += sizeofaddr
                    if result.address[0].address[0] != llmemory.NULL:
                        return result.address[0]
                if not self.finished:
                    self.finished = True
                    return captured_frame_holder
                return llmemory.NULL

        return StackRootIterator

 def __init__(self):
     self.addr = llmemory.raw_malloc(SIZE)

 def allocate_external_object(self, totalsize):
     # XXX maybe we should use arena_malloc() above a certain size?
     # If so, we'd also use arena_reset() in malloc_varsize_marknsweep().
     return llmemory.raw_malloc(totalsize)

 def op_raw_malloc(self, size):
     assert lltype.typeOf(size) == lltype.Signed
     return llmemory.raw_malloc(size)

 def allocate_stack(self):
     result = llmemory.raw_malloc(self.rootstacksize)
     if result:
         llmemory.raw_memclear(result, self.rootstacksize)
     return result

 def complex_struct():
     adr = llmemory.raw_malloc(sizeofsbase)
     s = llmemory.cast_adr_to_ptr(adr, SBASEPTR)
     s.b.s2.a = 42
     return (adr + offset_toa).signed[0]

 def _malloc(self, type_id, size):
     tid = llop.combine_ushort(lltype.Signed, type_id, 0)
     x = llmemory.raw_malloc(self.gcheaderbuilder.size_gc_header + size)
     x += self.gcheaderbuilder.size_gc_header
     return x, tid

 def setup_root_walker(self):
     stackbase = llmemory.raw_malloc(self.rootstacksize)
     ll_assert(bool(stackbase), "could not allocate root stack")
     llmemory.raw_memclear(stackbase, self.rootstacksize)
     self.gcdata.root_stack_top  = stackbase
     self.gcdata.root_stack_base = stackbase

def llimpl_arena_malloc(nbytes, zero):
    addr = llmemory.raw_malloc(nbytes)
    if zero and bool(addr):
        clear_large_memory_chunk(addr, nbytes)
    return addr