如何理解memory-mapped - Chinaunix

/*
* This program implements a simple address book. It is implemented as a
* binary tree inside a memory-mapped file so that it can survive
* between executions of the program.
*/
#include <stdio.h>;
#include <string.h>;
#include <stdlib.h>;
#include <errno.h>;
/* Header record placed at the start of the storage area. It describes the
free parts and contains the root of the BST. */
struct header
{
int nunused; /* Number of unused blocks. */
int firstun; /* Offset of the first unused block. */
int firstfree; /* First block of the freelist. */
int root; /* Root of the tree. */
};
/* Note that nodes on the free list, when the exist, are linked into a single
linked list using the left pointer of each node, and ignoring the right
pointer. */
/* Form of the tree nodes. */
struct node
{
char lname[20]; /* First name. */
char fname[20]; /* Last name. */
char addr[40]; /* Address. */
char phone[14]; /* Phone number. */
int left, right; /* Tree links. */
};
/* Note that left and right are integers. They represent the byte offset
of the left and right nodes relative to the start of the header. */
/* Macros to convert between offsets relative to the base of the area, and
pointers to node structures. */
#define OFFSET_TO_PTR(base, offset) \
((struct node *)((char *)(base) + (offset)))
#define PTR_TO_OFFSET(base, ptr) \
((char *)(ptr) - (char *)(base))
/* Location record returned by the tree search function. */
struct lrec {
int *plink; /* Where the node found is specified. */
struct node *node; /* The node found, or NULL. */
};
/* Program name. */
char *pname;
/* Number of node records in the storage area. Any portion of them may be
marked free. */
#define NREC 1000
/*
* Store a new header to inialize the space the first time.
*/
void format(char *area)
{
struct header *header = (struct header *)area;
/* Fill in the header information. */
header->;nunused = NREC; /* All records initially unused. */
header->;firstun = /* The first follows immediately. */
sizeof(struct header);
header->;firstfree = 0; /* The free list is empty. */
header->;root = 0; /* The tree is empty. */
}
/*
* Free list operations.
*/
/* Get a free node. The links are cleared. */
struct node *getnode(struct header *head)
{
struct node *retval; /* Return value. */
/* See if there is a node on the free list. */
if(head->;firstfree != 0) {
/* Use it. */
retval = OFFSET_TO_PTR(head, head->;firstfree);
head->;firstfree = retval->;left;
}
else
/* See if there is a node which has never been used. */
if(head->;nunused)
{
/* Use it. */
retval = OFFSET_TO_PTR(head, head->;firstun);
head->;firstun += sizeof(struct node);
--head->;nunused;
}
else
{
/* Cannot allocate. Bye. */
fprintf(stderr, "Allocation failed.\n");
exit(10);
}
retval->;left = retval->;right = 0;
return retval;
}
/* Add a node to the free list. */
void freenode(struct node *node, struct header *head)
{
node->;left = head->;firstfree;
head->;firstfree = PTR_TO_OFFSET(head, node);
}
/* Search the BST for a key. It takes the pointer to the control area, and
returns a locator record which contains enough info to delete, insert, or
just access the node with the indicated key. */
struct lrec locate(struct header *head, char *key)
{
int *locator = &head->;root;
while(1)
{
int cmp; /* Comparison result. */
struct node *node = /* Present node of scan. */
OFFSET_TO_PTR(head, *locator);
/* See if we reached a leaf. */
if(*locator == 0)
{
struct lrec retval = { locator, NULL };
return retval;
}
/* See if we have found the node. */
cmp = strcmp(key, node->;lname);
if(cmp == 0)
{
/* Found. */
struct lrec retval = { locator, node };
return retval;
}
else if(cmp < 0)
/* The key was less than the node. */
locator = &(node->;left);
else
/* The key was greater than the node. */
locator = &(node->;right);
}
}
/* Insert the node n into the tree, using the loc information returned by
locate. Obviously, if insert is passed a bad value for loc, it can
corrupt the tree by inserting in the wrong place. */
insert(struct header *header, struct node *n, struct lrec loc)
{
n->;right = 0;
n->;left = *loc.plink;
*loc.plink = PTR_TO_OFFSET(header, n);
}
/*
* Delete the node described by loc.
*/
delete(struct header *head, struct lrec loc)
{
struct node *node = loc.node;
if(node == NULL) return;
/* Check the cases. */
if(node->;left == 0)
/* Can connect up to right. */
*loc.plink = node->;right;
else if(node->;right == 0)
/* Can connect to left. */
*loc.plink = node->;left;
else
{
/* Two children. Must find a leaf. */
struct node *surr; /* Single child repl. node */
int surroff; /* Offset of surr. */
int *scan = &node->;left; /* Scanner to find it. */
while(1)
{
int rlink = OFFSET_TO_PTR(head, *scan)->;right;
if(rlink == 0) break;
scan = &OFFSET_TO_PTR(head, *scan)->;right;
}
/* Get information about the replacement. */
surroff = *scan;
surr = OFFSET_TO_PTR(head, surroff);
/* Detach the replacement. */
*scan = surr->;left;
/* Link it in place of the doomed node. */
surr->;left = node->;left;
surr->;right = node->;right;
*loc.plink = surroff;
}
/* Return the node to the free list. */
freenode(node, head);
}
/* Print the tree. */
prtree_r(struct header *head, struct node *node)
{
if(node->;left != 0)
prtree_r(head, OFFSET_TO_PTR(head, node->;left));
printf("%s\n", node->;lname);
if(node->;right != 0)
prtree_r(head, OFFSET_TO_PTR(head, node->;right));
}
prtree(struct header *head)
{
if(head->;root == 0)
printf("No entries.\n");
else
prtree_r(head, OFFSET_TO_PTR(head, head->;root));
}
/*
* Prompt and get an answer, and place it into place, which is of size size.
*/
void prompt(char *p, char *place, int size)
{
char buf[200]; /* Temp storage for response. */
int end; /* Loc. of last char. */
printf("%s: ", p);
fgets(buf, sizeof buf, stdin);
end = strlen(buf) - 1;
if(buf[end] == '\n') buf[end] = 0;
strncpy(place, buf, size - 1);
place[size - 1] = 0;
}
/*
* Run the command interpreter.
*/
void commands(char *area)
{
struct header *head = (struct header *)area;
char buf[200];
printf("addrs>; ");
for(;fgets(buf, sizeof buf, stdin) != NULL; printf("addrs>; "))
{
char cmd[21], lname[21];
int ret = sscanf(buf, "%20s %20s", cmd, lname);
if(ret < 1) continue;
if(strcmp(cmd, "add") == 0)
{
/* Return value of locate. */
struct lrec loc;
/* Add an entry. */
struct node *n = getnode(head);
if(ret >; 1) {
printf("Last name: %s\n", lname);
strncpy(n->;lname, lname, sizeof n->;lname);
n->;lname[sizeof n->;lname - 1] = 0;
}
else
prompt("Enter last name",
n->;lname, sizeof n->;lname);
loc = locate(head, n->;lname);
if(loc.node != NULL)
{
printf("There is alredy a %s on file.\n",
lname);
continue;
}
prompt("Enter first name", n->;fname, sizeof n->;fname);
prompt("Enter address", n->;addr, sizeof n->;addr);
prompt("Enter phone", n->;phone, sizeof n->;phone);
insert(head, n, loc);
}
else if(strcmp(cmd, "del") == 0)
{
/* Return value of locate. */
struct lrec loc;
if(ret < 2)
{
printf("Please give a name to delete.\n");
continue;
}
/* Search the tree, and delete. */
loc = locate(head, lname);
if(loc.node == NULL)
printf("%s not found.\n", lname);
else
delete(head, loc);
}
else if(strcmp(cmd, "find") == 0)
{
/* Return value of locate. */
struct lrec loc;
/* Find and print an entry. */
if(ret < 2)
{
printf("Please give a name to find.\n");
continue;
}
/* Search the tree. */
loc = locate(head, lname);
if(loc.node == NULL)
printf("%s not found.\n", lname);
else
{
printf("Last name: %s\n", loc.node->;lname);
printf("First name: %s\n", loc.node->;fname);
printf("Address: %s\n", loc.node->;addr);
printf("Phone: %s\n", loc.node->;phone);
}
}
else if(strcmp(cmd, "list") == 0)
{
printf("The following names are on file:\n");
prtree(head);
}
else if(strcmp(cmd, "quit") == 0)
return;
else
{
printf("No such command %s.\n", cmd);
}
}
}
/*
* Do the work.
*/
int main(int argc, char **argv)
{
/* Get the space. */
char *area = malloc(sizeof(struct header) + NREC*sizeof(struct node));
if(area == NULL)
{
fprintf(stderr, "Allocation failed.\n");
exit(1);
}
/* Format it into an empty phone book. */
format(area);
/* Run commands. */
commands(area);
/* Free the space. */
free(area);
exit(0);
}

复制代码