$```$

$/*$ initial test driver for strmap implementation $*/$

#include

#include "strmapbis.h$"/*$ includes string.h and stdlib.h $*/$

#define NUMTOPUT $400$

#define KEYLEN $10$

$/*$ buffer is twice the key size $*/$

#define BUFLEN $($KEYLEN $<mtext></mtext><mn>1</mn><mi>)</mi>$

#define SEED Ox$270$beef

$/*$ return a random printable character with high$-$order bit $=0*/$

#define ALFALEN $64$;

static char $*$alfabet $=$ "ABCDEFGHIJKLMNOPQRSTUVNDYZabcdefghijklmnopqrstuvwxyz"

$"123456789*+$:$"$;

static int count $=0$;

char randchar$($void$)\{$

static union $\{$

long bits;

unsigned char bytes$[4]$;

$\}$ u;

char c;

if $($count$==0)$

u$.$bits $=$ random$()$;

c $=$ alfabet$[$u$.$bytes$[$count$]$&$0$x$3$f$]$;

count $=($count $+1)$ & $3$;

return c;

$\}$

void randstring$($char $*$bufp$,$ int len$)\{$

int i;

for $($i$=0$; i$>1)$;

$/*$ make some random keys $*/$

srandom$($SEED$)$;

for $($ j$=0$; j $$ NUMTOPUT; j$++)$

randstring$($allkeys$[$j$],($random$()\%$KEYLEN$)+$ keypad$)$;

for $($j$=0$; j $$ NUMTOPUT; j$++)$

strmap$\_$put$($map$,$ allkeys$[$j$],($void $*)$j$)$;

strmap$\_$dump$($map$)$;

printf$("$before resizing: capacity $=\%$d$,$ load factor $=\%$f$.$

$",$

map$->$strmap$\_$nbuckets, strmap$\_$getloadfactor$($map$))$;

strmap$\_$resize$($map$,1\mathrm{.}0)$;

printf$("$after resizing w$/$target $1\mathrm{.}0$: capacity $=\%$d$,$ load factor $=\%$f$.$

$",$

map$->$strmap$\_$nbuckets, strmap$\_$getloadfactor$($map$))$;

strmap$\_$dump$($map$)$;

$/*$ now remove half of what's there $*/$

limit $=$ NUMTOPUT $>>1$;

for $($j$=0$; j $```$

void $*$pp $=$ strmap$\_$remove$($map$,$ allkeys$[$j$])$;

if $((($int$)$pp$)!=$ j$)$

printf$("$Error: strmap$\_$remove$(\%$s$)$ returned $\%$p $($expected $\%$x$).$

$",$

allkeys$[$j$],$pp$,$j$)$;

$\}$

printf$("$after removing $\%$d keys, load factor $=\%$f$.$

$",$limit$,$

strmap$\_$get loadfactor$($map$))$;

strmap$\_$resize$($map$,0\mathrm{.}75)$;

printf$("$after resizing $($target LF $=0\mathrm{.}75),$ load factor $=\%$f$,$ #buckets$=\%$d$.$

$",$

strmap$\_$getloadfactor$($map$),$strmap$\_$getnbuckets$($map$))$;

strmap$\_$dump$($map$)$;

printf$("$End of test$1.$c$.$

$")$;

return $0$;

$\}$

$``````$

#include $//$ for printf, ONLY IN strmap$\_$dump

#include $//$ for strcmp

#include $//$ for malloc$/$calloc

#define MAX$\_$BUCKETS $10000$

#define MIN$\_$BUCKETS $10$

#define LFSLOP $0\mathrm{.}125$

typedef struct strmap$\_$e $\{$

char $*$sme$\_$key;

void $*$sme$\_$value;

struct strmap$\_$e $*$sme$\_$next;

$\}$ smel$\_$t;

typedef struct sm $\{$

smel$\_$t $**$strmap$\_$buckets; $//$ array of pointers to elements

unsigned int strmap$\_$size; $///$ # elements in the table

unsigned int strmap$\_$nbuckets; $//$ size of the array

$\}$ strmap$\_$t;

$/*$ Create a new hashtab, initialized to empty. $*/$

strmap$\_$t $*$strmap$\_$create$($int numbuckets$)$;

$/*$ if the load factor is more than LFSLOP away from the target,

$*$ allocate a new array to bring the load factor within $1/8$ of

$*$ the given target $($i$.$e$.,$ between $7/8*$ target and $9/8*$target$),$

$*$ then re$-$hash everything into that array, free the old bucket

$*$ array, and make the map point to the new bucket array. $($The only

$*$ fields that change in the map are strmap$\_$buckets and strmap$\_$nbuckets.$)$

$*$ If the load factor is already within the target range,

$*$ the map is left unchanged.

$*/$

void strmap$\_$resize$($strmap$\_$t $*$m$,$ double target$)$;

$/*$ Insert an element with the given key and value.

$*$ Return the previous value associated with that key, or null if none.

$*/$

void $*$strmap$\_$put$($strmap$\_$t $*$m$,$ char $*$key$,$ void $*$value$)$;

$/*$ return the value associated with the given key, or null if none $*/$

void $*$strmap$\_$get$($strmap$\_$t $*$m$,$ char $*$key$)$;

$/*$ remove the element with the given key and return its value.

Return null if the hashtab contains no element with the given key $*/$

void $*$strmap$\_$remove$($strmap$\_$t $*$m$,$ char $*$key$)$;

$/*$ return the # of elements in the hashtab $*/$

int strmap$\_$getsize$($strmap$\_$t $*$m$)$;

$/*$ return the # of buckets in the hashtab $*/$

int strmap$\_$getnbuckets$($strmap$\_$t $*$m$)$;

$/*$ print out the contents of each bucket $*/$

void strmap$\_$dump$($strmap$\_$t $*$m$)$;

$/*$ return the current load factor of the map $*/$

double strmap$\_$getloadfactor$($strmap$\_$t $*$m$)$;

$```$