Material‎ > ‎

Storage Management in Memory

Dieses Programm illustriert, wie Speicherverwaltung tatsächlich auf der "untersten Ebene" in Sprachen wie C funktioniert.

Das Programm kann entweder direkt in Beanshell (www.beanshell.org) ausgeführt werden, oder in prozedurales Java unter Verwendung von "static" und "public" umgewandelt werden.

// -*- bsh -*-

// This file is written in Beanshell; you can either run this code
// by using the bsh interpreter, or you can wrap all the global functions
// below into a class.

// The following code illustrates how lists are represented in
// languages like assembly, C, and C++.

// Computer memory can be viewed as a large array of integers.

int[] memory = new int[65536];

// We need a special value to represent "null".  Usually, that's
// the value 0, but since 0 is a valid index in our memory array,
// we just use -1.  This also represents the empty list.
// By convention, it is called "nil".

int nil = -1;

// This time, we don't get to define any Java data structures; we need
// to represent data structures directly in memory.  We do that by
// using the type "int" to represent a reference to a list; it refers
// to the index of a list in the memory array.

// Since we don't get to use any Java syntax, we also end up having
// to define accessors ourselves.

int head(int l) {         // head(l) is the equivalent of l.head
    return memory[l];
}

int tail(int l) {         // tail(l) is the equivalent of l.tail
    return memory[l+1];
}

void set_head(int l,int v) { // set_head(l,v) is the equivalent of l.head = v
    memory[l] = v;
}

void set_tail(int l,int l2) { // set_tail(l,v) is the equivalent of l.tail = l2
    memory[l+1] = l2;
}

// As in the Java pool example, we maintain a freelist.  However, we cannot rely
// on the Java storage allocator anymore.  Instead, we initialize all of memory
// into a single large list by setting the locations correctly.

int freelist = nil;

for(int i=0;i<memory.length;i+=2) {
    set_head(i,-1);
    set_tail(i,freelist);
    freelist = i;
}

int in_use = 0;

// Constructing a new list element is similar to the pool example;
// however, once the freelist is empty, we have used up all available
// memory.  This is an out-of-memory condition.

int cons(int head,int tail) {
    in_use++;
    if(freelist!=nil) {
        int result = freelist;
        freelist = tail(freelist);
        set_head(result,head);
        set_tail(result,tail);
        return result;
    } else {
        System.err.println("out of memory");
        return -1;
    }
}

// The "free" procedure just adds its argument to the freelist, the
// list of elements that can be reused.  It also decreases the in_use
// count.

void free(int l) {
    set_tail(l,freelist);
    freelist = l;
    --in_use;
}

// This procedure reports how many list elements are currently in use.

void used() {
    System.err.println("in use: "+in_use);
}

// A simple procedure for printing out a list.

void printl(int l) {
    System.out.print("(");
    while(l!=nil) {
        System.out.print(" "+head(l));
        l = tail(l);
    }
    System.out.println(")");
}

l = cons(1,cons(2,cons(3,nil)));
printl(l);

// Let's now look at how this works in the context of a destructive
// delete procedure.  This is analogous to the versions of the code we
// had before, but we now use integer values as references, instead of
// Java's abstract types.

int destructive_delete(int l,int x) {
    if(l==nil) return nil;
    while(l!=nil && head(l)==x) {
        int temp = l;
        l = tail(l);
        free(temp);
    }
    if(l==nil) return nil;
    int start = l;
    while(tail(l)!=nil) {
        if(head(tail(l))==x) {
            int temp = tail(l);
            set_tail(l,tail(tail(l)));
            free(temp);
        } else {
            l = tail(l);
        }
    }
    return start;
}

print("== destructive delete ==");

l = cons(1,cons(2,cons(3,nil)));
printl(l); // prints: ( 1 2 3)
l = destructive_delete(l,1);
printl(l); // prints: ( 2 3)
l = destructive_delete(l,3);
printl(l); // prints: ( 2)
l = destructive_delete(l,2);
printl(l); // prints: ()


Comments