*Figure 8.8:Some identifiers requiring 3 bits per character(p.414)
*Figure 8.9: A trie to hole identifiers(p.415)
*Program 8.5: Dynamic hashing (p.421) #include #include #include #define WORD_SIZE 5 /* max number of directory bits */ #define PAGE_SIZE 10 /* max size of a page */ #define DIRECTORY_SIZE 32 /* max size of directory */ typedef struct page *paddr; typedef struct page { int local_depth; /* page level */ char *name[PAGE_SIZE]; int num_idents; /* #of identifiers in page */ }; typedef struct { char *key; /* pointer to string */ /*other fields */ } brecord; int global_depth; /* trie height */ paddr directory[DIRECTORY_SIZE]; /* pointers to pages */
paddr hash(char *, short int); paddr buddy(paddr); short int pgsearch(char *, paddr ); int convert(paddr); void enter(brecord, paddr); void pgdelete(char *, paddr); paddr find(brecord, char *); void insert (brecord, char *); int size(paddr); void coalesce (paddr, paddr); void delete(brecord, char *); paddr hash(char *key, short int precision) { /* *key is hashed using a uniform hash function, and the low precision bits are returned as the page address */ }
paddr buddy(paddr index) { /*Take an address of a page and returns the page’s buddy, i. e., the leading bit is complemented */ } int size(paddr ptr) { /* return the number of identifiers in the page */ } void coalesce(paddr ptr, paddr, buddy) { /*combine page ptr and its buddy into a single page */ } short int pgsearch{char *key, paddr index) { /*Search a page for a key. If found return 1 otherwise return 0 */ }
void convert (paddr ptr) { /* Convert a pointer to a pointer to a page to an equivalent integer */ } void enter(brecord r, paddr ptr) { /* Insert a new record into the page pointed at by ptr */ } void pgdelete(char *key, paddr ptr) { /* remove the record with key, hey, from the page pointed to by ptr */ } short int find (char *key, paddr *ptr) { /* return 0 if key is not found and 1 if it is. Also, return a pointer (in ptr) to the page that was searched. Assume that an empty directory has one page. */
paddr index; int intindex; index = hash(key, global_depth); intindex = convert(index); *ptr = directory[intindex]; return pgsearch(key, ptr); } void insert(brecord r, char *key) { paddr ptr; if find(key, &ptr) { fprintr(stderr, “ The key is already in the table.\n”); exit(1); } if (ptr-> num_idents != PAGE_SIZE) { enter(r, ptr); ptr->num_idents++; } else{ /*Split the page into two, insert the new key, and update global_depth if necessary.
If this causes global_depth to exceed WORD_SIZE then print an error and terminate. */ }; } void delete(brecord r, char *key) { /* find and delete the record r from the file */ paddr ptr; if (!find (key, &ptr )) { fprintf(stderr, “Key is not in the table.\n”); return; /* non-fatal error */ } pgdelete(key, ptr); if (size(ptr) + size(buddy(ptr)) <= PAGE_SIZE) coalesce(ptr, buddy(ptr)); } void main(void) { }
*Figure 8.12: A trie mapped to a directoryless, contiguous storage (p.424)
*Figure 8.13: An example with two insertions (p.425)
*Figure 8.14: During the rth phase of expansion of directoryless method (p.426)
*Program 8.6:Modified hash function (p.427) if ( hash(key,r) < q) page = hash(key, r+1); else page = hash(key, r); if needed, then follow overflow pointers;
