\File{chash.c},{12:43},{Feb  6 1997}
\L{\LB{\K{\#include} \S{}\"squid.h\"\SE{}}}
\L{\LB{}}
\L{\LB{\K{extern} \K{int} num\_hosts;}}
\L{\LB{\K{extern} const \K{char} *myhostname;}}
\L{\LB{\K{extern} \K{struct} hostinfo *tablePtr;}}
\L{\LB{\K{extern} \K{struct} machplace *uiPtr;}}
\L{\LB{}}
\L{\LB{\C{}\/* get a number of points for a machine *\/\CE{}}}
\L{\LB{\K{int} }}
\L{\LB{\Proc{dhGetMachinePoints}dhGetMachinePoints(\K{char} *hostname, \K{int} points) \{}}
\L{\LB{  \K{int} f;}}
\L{\LB{  \K{int} len = (\K{int}) strlen(hostname);}}
\L{\LB{  \C{}\/* get the crc32 hash for that hostname *\/\CE{}}}
\L{\LB{  \K{long} init = crc32(hostname,len);}}
\L{\LB{  \C{}\/* and use that to seed the pseudo\-random numbers *\/\CE{}}}
\L{\LB{  dhSrand(init);}}
\L{\LB{}}
\L{\LB{  \C{}\/* get one pseudo\-random number between 0 and 1 for each point *\/\CE{}}}
\L{\LB{  \K{for}(f=0;f\<points;f++) \{}}
\L{\LB{    \K{unsigned} \K{int} i = dhRand();}}
\L{\LB{    \K{double} d = ((\K{double})i) \/ ((\K{double})DH\_RAND\_MAX);}}
\L{\LB{    \C{}\/* add the machine,point pair to the unit interval *\/\CE{}}}
\L{\LB{    dhAddMachineToInterval(hostname,d);}}
\L{\LB{  \}}}
\L{\LB{  \K{return} 0;}}
\L{\LB{\}}}
\L{\LB{}}
\L{\LB{\C{}\/* add a machine,point pair to the unit interval *\/\CE{}}}
\L{\LB{\K{int} }}
\L{\LB{\Proc{dhAddMachineToInterval}dhAddMachineToInterval(\K{char} *hostname, \K{double} d ) \{}}
\L{\LB{  \K{struct} machplace *newmach, *lastPtr, *currPtr =uiPtr;}}
\L{\LB{}}
\L{\LB{  \C{}\/* go through the unit interval *\/\CE{}}}
\L{\LB{  \K{while} (currPtr != NULL) \{}}
\L{\LB{}}
\L{\LB{    \C{}\/* save the current place for the next round *\/\CE{}}}
\L{\LB{    lastPtr = currPtr;}}
\L{\LB{}}
\L{\LB{    \C{}\/* deal with duplicates \- they will happen eventually *\/\CE{}}}
\L{\LB{    \K{if} (currPtr\-\>position == d) \{}}
\L{\LB{      \K{int} i;}}
\L{\LB{      d = d + 0.000001;}}
\L{\LB{      i = dhAddMachineToInterval(hostname,d);}}
\L{\LB{      \K{return} i;}}
\L{\LB{    \}}}
\L{\LB{    \C{}\/* find the first higher position in the unit interval *\/\CE{}}}
\L{\LB{    \K{else} \K{if} (currPtr\-\>position \> d) \{}}
\L{\LB{}}
\L{\LB{      \C{}\/* malloc space for a new entry in the table *\/\CE{}}}
\L{\LB{      newmach = (\K{struct} machplace *) malloc(\K{sizeof}(\K{struct} machplace));}}
\L{\LB{      \K{if} (newmach == NULL)\{}}
\L{\LB{}\Tab{8}{perror(\S{}\"malloc\"\SE{});}}
\L{\LB{}\Tab{8}{\K{return}(\-1);}}
\L{\LB{      \}}}
\L{\LB{      \C{}\/* malloc the space for the machine name *\/\CE{}}}
\L{\LB{      newmach\-\>name = malloc(strlen(hostname) + 1);}}
\L{\LB{      \K{if} (newmach\-\>name == NULL) \{}}
\L{\LB{}\Tab{8}{perror(\S{}\"malloc\"\SE{});}}
\L{\LB{}\Tab{8}{\K{return}(\-1);}}
\L{\LB{      \}}}
\L{\LB{      \C{}\/* put the new address and time in the malloc\'d space, and point the}}
\L{\LB{       * entry\'s nexthost pointer to the next entry *\/\CE{}}}
\L{\LB{      strcpy(newmach\-\>name,hostname);}}
\L{\LB{      newmach\-\>position = d;}}
\L{\LB{      newmach\-\>nextmach =  currPtr;}}
\L{\LB{}}
\L{\LB{      lastPtr\-\>nextmach = newmach;}}
\L{\LB{}}
\L{\LB{      \K{return}(0);}}
\L{\LB{    \}}}
\L{\LB{    \C{}\/* increment to the next entry *\/\CE{}}}
\L{\LB{    currPtr = currPtr\-\>nextmach;}}
\L{\LB{  \}}}
\L{\LB{  \C{}\/* this should never be reached. *\/\CE{}}}
\L{\LB{  \K{return} \-1;}}
\L{\LB{\}}}
\L{\LB{}}
\L{\LB{\C{}\/* find the nearest machine to any point on the unit interval *\/\CE{}}}
\L{\LB{\K{char} *}}
\L{\LB{\Proc{dhFindNearestMachine}dhFindNearestMachine(\K{double} point) \{}}
\L{\LB{  \K{struct} machplace *lastPtr, *currPtr =uiPtr;}}
\L{\LB{}}
\L{\LB{  \C{}\/* go through the unit interval *\/\CE{}}}
\L{\LB{  \K{while} (currPtr != NULL) \{}}
\L{\LB{}}
\L{\LB{    \C{}\/* save the current place for the next round *\/\CE{}}}
\L{\LB{    lastPtr = currPtr;}}
\L{\LB{    \C{}\/* find the first higher point *\/\CE{}}}
\L{\LB{    \K{if} (currPtr\-\>position \>= point) \{}}
\L{\LB{      \C{}\/* compute the differences between the two nearest points *\/\CE{}}}
\L{\LB{      \K{double} upper, lower;}}
\L{\LB{      upper = currPtr\-\>position \- point;}}
\L{\LB{      lower = lastPtr\-\>position \- point;}}
\L{\LB{      \C{}\/* return the closer point *\/\CE{}}}
\L{\LB{      \K{if} (upper \> lower) \{}}
\L{\LB{}\Tab{8}{\K{return} lastPtr\-\>name;}}
\L{\LB{      \}}}
\L{\LB{      \K{else} \{}}
\L{\LB{}\Tab{8}{\K{return} currPtr\-\>name;}}
\L{\LB{      \}}}
\L{\LB{    \}}}
\L{\LB{  \}}}
\L{\LB{  \C{}\/* if no point is higher, return the last point *\/\CE{}}}
\L{\LB{  \K{return} lastPtr\-\>name;}}
\L{\LB{\}}}
\L{\LB{}}
\L{\LB{\C{}\/* construct the unit interval and fill it with hosts *\/\CE{}}}
\L{\LB{\K{int} }}
\L{\LB{\Proc{dhBuildUI}dhBuildUI() \{}}
\L{\LB{  \K{struct} hostinfo *thisPtr = tablePtr;}}
\L{\LB{  \K{int} n=0;}}
\L{\LB{}}
\L{\LB{  \C{}\/* go through the host table and add the points for each machine *\/\CE{}}}
\L{\LB{  \K{while} (thisPtr != NULL) \{}}
\L{\LB{    dhGetMachinePoints(thisPtr\-\>addr,3);}}
\L{\LB{    n++;}}
\L{\LB{    thisPtr = thisPtr\-\>nexthost;}}
\L{\LB{  \}}}
\L{\LB{  \K{return} n;}}
\L{\LB{\}}}
\L{\LB{}}
\L{\LB{\C{}\/* construct the tree until we find outself in it *\/\CE{}}}
\L{\LB{\K{int} }}
\L{\LB{\Proc{dhBuildTree}dhBuildTree(\K{char} *url, \K{int} n) \{}}
\L{\LB{  \K{int} i;}}
\L{\LB{  \C{}\/* loop through the number of hosts until we find the first occurance }}
\L{\LB{   * of ourself *\/\CE{}}}
\L{\LB{  \K{for} (i=1;i\>=n;i++) \{}}
\L{\LB{    \K{char} u[MAX\_URL+ \K{sizeof}(\K{long})];}}
\L{\LB{    \K{double} d;}}
\L{\LB{    \K{char} *name;}}
\L{\LB{    \C{}\/* calculate the point for that url,number pair *\/\CE{}}}
\L{\LB{    sprintf(u, \S{}\"\%d\%s\"\SE{}, i, url);}}
\L{\LB{    d = crc32(u,\K{sizeof}(u)) \% ((u\_int)DH\_RAND\_MAX + 1);}}
\L{\LB{    \C{}\/* find which machine is closest to this point *\/\CE{}}}
\L{\LB{    name = dhFindNearestMachine(d);}}
\L{\LB{    \C{}\/* when we find ourself, return our position in the tree *\/\CE{}}}
\L{\LB{    \K{if} (name == myhostname) \{}}
\L{\LB{      \K{return} n;}}
\L{\LB{    \}}}
\L{\LB{  \}}}
\L{\LB{  \C{}\/* if we never find ourself *\/\CE{}}}
\L{\LB{  \K{return} 0;}}
\L{\LB{\}}}
\L{\LB{}}
\L{\LB{\C{}\/* take a hostname, and make an edge out of it. *\/\CE{}}}
\L{\LB{edge *}}
\L{\LB{\Proc{dhMakeEdge}dhMakeEdge(\K{char} *host) \{}}
\L{\LB{  u\_short http\_port = CACHE\_HTTP\_PORT;}}
\L{\LB{  u\_short icp\_port = CACHE\_ICP\_PORT;}}
\L{\LB{  \K{int} options = 0;}}
\L{\LB{  \K{int} weight = 1;}}
\L{\LB{  \K{int} mcast\_ttl = 0;}}
\L{\LB{}}
\L{\LB{  edge *e = NULL;}}
\L{\LB{  e = xcalloc(1, \K{sizeof}(edge));}}
\L{\LB{  e\-\>http\_port = http\_port;}}
\L{\LB{  e\-\>icp\_port = icp\_port;}}
\L{\LB{  e\-\>mcast\_ttl = mcast\_ttl;}}
\L{\LB{  e\-\>options = options;}}
\L{\LB{  e\-\>weight = weight;}}
\L{\LB{  e\-\>host = xstrdup(host);}}
\L{\LB{  e\-\>pinglist = NULL;}}
\L{\LB{  e\-\>typelist = NULL;}}
\L{\LB{  e\-\>acls = NULL;}}
\L{\LB{  e\-\>icp\_version = ICP\_VERSION\_CURRENT;}}
\L{\LB{  e\-\>type = parseNeighborType(\S{}\"parent\"\SE{});}}
\L{\LB{}}
\L{\LB{  \K{return} e;}}
\L{\LB{\}}}
\L{\LB{}}
\L{\LB{\C{}\/* take a url and find the immediate parent *\/\CE{}}}
\L{\LB{edge *}}
\L{\LB{\Proc{dhGetParent}dhGetParent(\K{char} *url) \{}}
\L{\LB{  \K{int} myplace, parentplace;}}
\L{\LB{  \K{double} d;}}
\L{\LB{  \K{char} *name, u[MAX\_URL+ \K{sizeof}(\K{long})];}}
\L{\LB{  edge *edge\_answer;}}
\L{\LB{  \K{int} deg = DEGREE\_OF\_TREE;}}
\L{\LB{}}
\L{\LB{}}
\L{\LB{  myplace = dhBuildTree(url,num\_hosts);}}
\L{\LB{}}
\L{\LB{  \K{if} (myplace \> 1) \{}}
\L{\LB{    parentplace = myplace \/ deg;}}
\L{\LB{}}
\L{\LB{    sprintf(u, \S{}\"\%d\%s\"\SE{}, parentplace, url);}}
\L{\LB{    d = crc32(u,\K{sizeof}(u)) \% ((u\_int)DH\_RAND\_MAX + 1);}}
\L{\LB{}}
\L{\LB{    name = dhFindNearestMachine(d);}}
\L{\LB{    edge\_answer = dhMakeEdge(name);}}
\L{\LB{    \K{return} edge\_answer;}}
\L{\LB{  \}}}
\L{\LB{  \K{else} \{}}
\L{\LB{    \C{}\/* we are either at the top of the tree, or not in the tree at all *\/\CE{}}}
\L{\LB{    \K{return} NULL;}}
\L{\LB{  \}}}
\L{\LB{\}}}
\L{\LB{}}
\L{\LB{\C{}\/* return the number of neighbors *\/\CE{}}}
\L{\LB{\K{int} }}
\L{\LB{\Proc{dhNeighborsCount}dhNeighborsCount(edge *dhparent) \{}}
\L{\LB{  \C{}\/* only one neighbor, else we are at the top of the tree, then none *\/\CE{}}}
\L{\LB{  \K{if} (dhparent == NULL) \{}}
\L{\LB{    \K{return} 0;}}
\L{\LB{  \}}}
\L{\LB{  \K{else} \{}}
\L{\LB{    \K{return} 1;}}
\L{\LB{  \}}}
\L{\LB{\}}}
