Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!elroy.jpl.nasa.gov!swrinde!zaphod.mps.ohio-state.edu!rpi!uupsi!sunic!ugle.unit.no!nuug!ifi!oystein From: oystein@ifi.uio.no (ystein Carl Emil Hebnes) Newsgroups: comp.sys.acorn Subject: Re: Memory handling Message-ID: <1991Mar22.171119.11147@ifi.uio.no> Date: 22 Mar 91 17:11:19 GMT References: <1991Mar20.143227.247@ecc.tased.oz.au> Sender: oystein@ifi.uio.no (\ystein Carl Emil Hebnes) Organization: Dept. of Informatics, University of Oslo, Norway Lines: 105 Nntp-Posting-Host: svipall.ifi.uio.no Originator: oystein@svipall.ifi.uio.no In article <1991Mar20.143227.247@ecc.tased.oz.au>, ecc_jim@ecc.tased.oz.au writes: > We are developing a package using C 1.3B that makes extensive use of tree > structures for handling indexes into data files. > > These structures are loaded into memory when needed (using malloc) and > discarded when finished with (using free). If the current wimpslot is too > small to handle the data, it is automatically extended to accomodate it > (this is handled by RISC_OSLIB). > > Unfortunately, when the associated memory has been "free'd" it is not handed > back to the operating system for general usage. The memory gets re-used > within the program so when another "malloc" is done the memory is not > wasted. > > This has the unfortunate side effect of building the wimpslot up to a > certain maximum level (depending on the size of the indexes). This level is > approaching the limit for 1 megabyte machines - hence the problem. > [...] > ANSI C release 3 has an additional memory management tool called a flex > pool. This is a method of claiming free operating system memory and then > passing it back when finished with (Edit does this for the files it loads). > There is, however, a restriction on a flex memory allocation (from page 225 > of the ANSI C release 3 guide): > > "...you cannot have flex pointers within blocks of memory allocated by > flex." > > This means that you cannot have linked lists or binary trees - the main > reason that memory is being used by our application. > > That is the problem, does anyone have a solution? > I'll try a quick, mindless reply to this. Say you want to build a B-tree or indeed any high-level data structure dynamically allocating room for elements (nodes) as you go along, and wanting to be able to free this space at will. If you use malloc(), the memory can't be reused by the system until the application quits, even though you free() it. So, you try flex. If you try to allocate room for the individual nodes, and then keep node pointers inside these memory areas, the flex manager will fail to update any pointers to a node as it moves it around the memory. The C manual explains this in more detail. So, you're stuck, right? Well, I did a wee bit of thinking, and came up with the following: Let's assume all the nodes have the same size (nsize = sizeof (struct foo)). We can't keep pointers to the nodes themselves, so we have to be a bit more devious. The first thing to do is to allocate an array of void pointers. Call this the anchor block. It will contain anchors, as required by the flex functions. It is vital that the anchor block is never moved around, so malloc() it, or flex_alloc() it before anything else (the first call to flex_alloc() is guaranteed to return a pointer to an area which will never be moved around.) Now, you're ready to allocate your first node. The thing to do, is to allocate a block of several nodes, say 100. This is the other type of block, a node block. The first anchor in the anchor block should point to this block (you pass that pointer's address as a parameter to flex_alloc().) As you allocate more nodes, you'll fill up the first node block, and eventually, you'll allocate another node block in the same way, and it'll be pointed to by the second anchor, and so on. Just make sure that no_of_anchors * nodes_per_block gives you enough nodes. An overestimate does no harm, anchor pointers are cheap. So, what about the internal node pointers in the structure? The left/right, next or parent pointers? They won't be ordinary pointers. They must contain 2 elements. First the node block number, and then the node number in the node block. That's the trick. To access e.g. the next node in a list, then, you first read the node block number, then aquire the actual node block address by following the right pointer in the anchor block, and then calculate the node address by a formula similar to node_block_start + (node_no - 1) * nsize. As you see, following pointers requires a bit more work than usual, but you gain the ability to dynamically manage memory. Which brings me to the subject of freeing memory again. You could maintain a free list for each node block, and when a block has its last node freed, you can flex_free() the whole node block. The best strategy for freeing depends on the pattern of insertions and deletions from the structure. If you do these in a stackwise or queuewise fashion, you can put many nodes in each node block and minimize administration overhead. If, however, insertions and deletions occur in random order for random nodes, the node blocks should be kept rather small, so that you don't get stuck with a lot of node blocks with only a few nodes in each. Please feel free to comment on and correct all the inaccuracies, overkills and actual errors in this method. I didn't consult the manuals on this one, and there's probably room for some improvement. Last, but not least: where's that C++ 2.1 compiler for the Archimedes ??? Acorn ??? _/ _ | _ . _ | "There are no problems, only 8 ft thick, 20 ft high, //\ \/ |_ -|- |_| | |/ || reinforced concrete walls (i.e. challenges!) /_/ / \_| |_ |_ | | || The solution? Nuke'em or dig under them (i.e. use a ________________________| Cray or apply a bit of lateral thinking.)"