21-MAR-81 Virtual memory package for C programs 21-MAR-81 This documents the use of two C library routines and the macros which have been designed to simplify their use. Also documented is a set of routines which implement a heap structure on disk. These heap routines make use of the below described routines and macros. The macros were designed with the following goals in mind: 1. There should be only a minimal number of actual routines which do any real work. All user calls should map to these primatives via macro calls. 2. The burden of supplying many parameters (which could be incorrectly set up) should be reduced where possible. For example: The expected use of these routines is to implement a heap structure on disk. Therefore it is expected that only 1 disk file will actually be used with the macros described below. This reduces 1 parameter reference as the file variable can be made fixed within the file. 3. The user interface should be at the variable or structure level. That is, transfers to and from the disk heap should be for composite data types rather than just byte streams (which is the level of the file system) of sizes in which the user would ordinarily need to set up himself. General Usage: The following file needs to be included in every source file to define the set of macros described below. #include The only routines which do any real i/o are the below two routines which are also described in the JPL C library documentation. getat(fd,pointer,var,size) and putat(fd,pointer,var,size) Where: fd is a file variable pointer is a LONG integer which contains the address of the data on disk. var is the location in memory (not disk) where the transfer takes place in or out of. size is the size in bytes of the transfer and the type definitions are: FILE *fd; long pointer; char *var; int size -1- 21-MAR-81 Virtual memory package for C programs 21-MAR-81 For example: FILE fd; long data; char a[20]; getat(fd,data,a,sizeof(a)); Note the use of the sizeof operator. This would be mapped to 20 in this example and therefore retreive an array of 20 characters from location `data' on the disk (file fd) into the char array `a'. A putat call to reverse the transfer would look essentially identical. putat(fd,data,a,sizeof(a)); The following macros exsist which shorten calls to getat/putat. Since all calls to getat and putat require a fd parameter, the macros were designed to hide that parameter. To do this they need to be able to get at the fd somehow. Thus the user must have the following definition in his program: (before the include of files.h) #define FILEX fd Where fd is the name of the variable to use in each call to getat or putat. Since this definition is global to the file, it is recomended that any fd variables also be global to a file. Otherwise, FILEX could have several meanings (depending on what function the following macros are called from). Note that usually the user will only have a single file for virtual memory. If this it not the case, then these macros will probably be of little use. The following macro definitions exist. The actual source of these macros will be shown also. GETvar(pointer,variable) long pointer; var variable; PUTvar(pointer,variable) long pointer; var variable; These two macros are used for transfering a single variable by name. Examples: long d_name; char name[20]; long d_addr; char addr[30]; long d_zip; char zip[10]; long d_age; int age; d_name = ; /* These are probably set */ d_addr = /* up using the heap allocator */ d_zip = ; /* or are in fixed locations */ d_age = ; /* These need not be arrays */ -2- 21-MAR-81 Virtual memory package for C programs 21-MAR-81 getvar(d_name,name); /* transfers 20 bytes */ getvar(d_addr,addr); /* 30 */ getvar(d_zip,zip); /* 10 */ getvar(d_age,age); /* 2 */ The macro definitions are as follows: #define getvar(seek,varr) getat(FILEX,seek,&varr,sizeof(varr)) #define putvar(seek,varr) putat(FILEX,seek,&varr,sizeof(varr)) Note that the & operator is always applied. Thus on arrays this means that the expression &array is compiled. On some C compilers this may be illegal; rather the expression must be &array[0]. Thus a getvar call is safest as for example getvar(d_zip,zip[0]); GETstruct(pointer,strptr) long pointer; struct *strptr; PUTstruct(pointer,strptr) long pointer; struct *strptr; These two are for transfering to and from structures where the structure is only known via a pointer variable. (If the structure is known as a variable - static or automatic - use getvar). For example: Struct person { char name[20]; char addr[30]; char zip[10]; int age; } *thisguy; long john; john =
; thisguy = alloc(sizeof(person)); getstruct(john,thisguy); The macro definitions are as follows: #define getstruct(seek,ptr) getat(FILEX,seek,ptr,sizeof(*ptr)) #define putstruct(seek,ptr) putat(FILEX,seek,ptr,sizeof(*ptr)) GETn(pointer,address,n) long pointer; var *address; PUTn(pointer,address,n) long pointer; var *address; -3- 21-MAR-81 Virtual memory package for C programs 21-MAR-81 These are for transfering a known number of bytes. They are in fact very close to the actual transfer routines getat and putat. They only serve to shorten the calls slightly; the file parameter is not necessary. for example: /* on disk is the following variable length structure int size; char string[size]; where size and string are contiguously stored. */ long loc; int size; char string[MAXSIZE]; loc = ; getvar(loc,size); getn(RELATIVE,min(size,MAXSIZE)); Note the symbol RELATIVE; it is a value for a getat or putat call which means start where the last transfer left off. It actually is the value -1l but use the word RELATIVE. Thus the string in the above example has the format: nchars followed by the chars. The macro definitions are as follows: #define getn(seek,varr,size) getat(FILEX,seek,&varr,size) #define putn(seek,varr,size) putat(FILEX,seek,&varr,size) -4- 21-MAR-81 Virtual memory package for C programs 21-MAR-81 The following describes the available heap management routines. In addition to the files.h include file described above, the following is necessary. #include A disk file is formated as follows: Disk block addresses 0-01000 (1000 octal) are scratch to be used for list heads etc. The free list starts at 01000, all other storage is allocated dynamically following the free list area. The following are the basic low level allocators and releasers. They should not be called directly if one wishes to link all the storage together into doubly linked lists. However, if only large blocks that are not linked are desired, then these can be used. They are called on behalf of the user when one uses the linked list allocator described below. initf(fd,size) FILE fd; long size; Initialize a disk file (fd) for use as a heap. Size is the amount of initial allocation (in bytes) and also how much the disk file is to be expanded each time room is needed. Long falloc(fd,n) FILE fd; long n; Allocates a block of n bytes, returns a long pointer to the storage area. ffree(fd,pointer) FILE fd; long pointer; Releases storage gotten with falloc. Does not verify pointer, it had better be correct. The following are linked list routines for disk storage. long fnew(fd,size) FILE fd; long size; Returns a node with left and right links initialized to a list of a single node. The value returned is the pointer to the data area of size = size byte. The pointers are actually stored just ahead of this area, but the user should never mess with them. Pointers to nodes always point to the data area, not the links. -5- 21-MAR-81 Virtual memory package for C programs 21-MAR-81 frelease(fd,pointer) FILE fd; long pointer; Releases a node gotten by fnew. Don't mix frelease and ffree as disaster is sure to occur. No checking is done to verify correct pointers. flh(fd,loc) FILE fd; long loc; This will create a listhead node (usually at a loc in the lower 01000 bytes). It will also initialize the least head to an empty list. An empty list is one in which the listhead only points to itself. long finsert(fd,after,newnode); FILE fd; long after,newnode; Inserts a single node (a list in itself, usually gotten via fnew) into the list in which `after' is allready contained (but it could be the only node in that list, say if it is just a list head) and is positioned after `after'. This means that given after, a call to fnext (see below) would return a pointer to newnode. It returns the pointer to newnode. long fnext(fd,pointer) FILE fd; long pointer; Gets a pointer to the node in the list following the node pointed to by pointer. long fprev(fd,pointer) FILE fd; long pointer; Gets a pointer to the node in the list previous to the node pointed to by pointer. Example: The following routine reads a file of text strings and allocates n+3 chars per string from the disk heap. This provides room for the string length, the string itself, and 1 char more for the null. The length of the string is stored ahead of the text on disk. After each string is put onto the disk heap in a node, that node is inserted into a list. The list has a list head at location 0100 on the disk. The symbolic LIST1 is used for this. Note that the value must be a long integer. For ease of documentation, all text on the right are in ADA comment notation: i.e. -- comment. #define FILEX fd -- must define this for the macros to use #define LIST1 0100l -- This is where the list head resides #include -- get definitions for files access -6- 21-MAR-81 Virtual memory package for C programs 21-MAR-81 #include -- get more def's for linked list stuff static FILE *fd -- declare once in the file static char a[100] = {0}; -- char array to read strings into main(argc,argv) int argc; char *argv[]; { long gotit ; -- pointer to disk long after; -- another pointer to disk long p; -- linked list pointer on disk register int i,nn; -- some spare integers int size; if (fd = fopen(argv[2],"update","u") != 1) { -- open file exit(4); -- return to system with error status } -- on any error lrumax(fd,10); -- allow for 10 blocks of memory -- to be used by file primatives initf(fd,01000l); -- initialize the file as a heap -- with expand size = 01000 bytes flh(fd,LIST1); -- create a listhead for our list at after = LIST1; -- location LIST1 on disk -- and init `after' at the listhead /* Load all the text strings from the stdin file onto our disk heap linked together so we can reverse their order later on. */ for (;;) -- read the entire text file if ( getstr(stdin,a,99) < 0 ) { break; -- until end of file } size = strlen(a) + 1; -- compute size of line + 1 gotit = fnew(fd, (long) size+sizeof(int))); -- get some disk space putvar(gotit,size); -- output the size putn(RELATIVE,a,size); -- then follow with the string in a after = finsert(fd,after,gotit); -- and insert `gotit' next to } -- `after' in list /* All the text strings have been input and linked on the disk Now to traverse the list in reverse order and output the strings. */ p = LIST1; -- set pointer to listhead for (;;) -- cycle p = fprev(fd,p); -- get pointer to previous in list if (p == LIST1) { -- if back to list head, then done -7- 21-MAR-81 Virtual memory package for C programs 21-MAR-81 break; } getvar(p,size); -- else get the string size getn(RELATIVE,a,size); -- following by the sting itself printf("%s\n",a); -- and print it out } exit(1); -- all done, close file } -8-