home *** CD-ROM | disk | FTP | other *** search
/ CGI How-To / CGI HOW-TO.iso / chap4 / 4_4 / comp_c / dict.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-06-15  |  7.2 KB  |  416 lines
  1.  
  2.  
  3. #include "dict.h"
  4.  
  5. static int ceilPrime(int aValue)
  6. {
  7.     int retVal;
  8.     
  9.     retVal = aValue;
  10.     
  11.     if(aValue <= 5) retVal = 5;
  12.     else if(aValue <= 10) retVal = 11;
  13.     else if(aValue <= 15) retVal = 17;
  14.     else if(aValue <= 50) retVal = 51;
  15.     else if(aValue <= 95) retVal = 97;
  16.     else if(aValue <= 240) retVal = 241;
  17.     else if(aValue <= 395) retVal = 397;
  18.     else if(aValue <= 495) retVal = 499;
  19.     else if(aValue <= 740) retVal = 743;
  20.     else if(aValue <= 995) retVal = 997;
  21.     else if(aValue <= 1490) retVal = 1499;
  22.     else if(aValue <= 1990) retVal = 1999;
  23.     else if(aValue <= 3975) retVal = 3989;
  24.     else if((aValue % 2) == 0) retVal+=1;
  25.     
  26.     return retVal;
  27. }
  28.  
  29. static int stringHash(const char *theString)
  30. {
  31.     unsigned long theHash = 0, g;
  32.     char *tmpString = (char *)theString;
  33.     
  34.     if(tmpString)
  35.     {
  36.         while((*tmpString) != '\0')
  37.         {
  38.             
  39.             /* Old version theHash = *tmpString++ + (31 * theHash); */
  40.             theHash = (theHash << 4 ) + *tmpString++;
  41.             
  42.             if( g = theHash & 0xF0000000 ) theHash ^= g >> 24;
  43.             
  44.             theHash &= ~g;
  45.         
  46.         }
  47.     
  48.     }
  49.     return theHash;
  50. }
  51.  
  52. Dictionary dict_alloc()
  53. {
  54.     Dictionary retVal;
  55.     int newS;
  56.     
  57.     retVal = (Dictionary) malloc(sizeof(struct _dict));
  58.     
  59.     newS = ceilPrime(DEF_CAPACITY);
  60.     
  61.     retVal->hashtable = (struct listnode **)
  62.                         calloc(newS,sizeof(struct listnode *));
  63.     retVal->size = newS;
  64.     retVal->used = 0;
  65.     
  66.     return retVal;
  67. }
  68.  
  69. void dict_free(Dictionary aDict)
  70. {
  71.     if(aDict)
  72.     {
  73.         struct listnode *newNode = 0;
  74.         struct listnode *nextNode = 0;
  75.         int i;
  76.     
  77.         for(i = 0; i < aDict->size; i++)
  78.         {
  79.             newNode = aDict->hashtable[i];
  80.         
  81.             while(newNode)
  82.             {
  83.                 nextNode = newNode->next;
  84.                 free(newNode->key);
  85.                 free(newNode);
  86.                 newNode = nextNode;
  87.             }
  88.         
  89.             aDict->hashtable[i] = 0;
  90.         }
  91.     
  92.         if(aDict->hashtable) free(aDict->hashtable);
  93.  
  94.         free(aDict);
  95.         
  96.         aDict = 0;
  97.     }
  98. }
  99.  
  100. void dict_freeWithData(Dictionary aDict,void(*freer)())
  101. {
  102.     if(aDict)
  103.     {
  104.         struct listnode *newNode = 0;
  105.         struct listnode *nextNode = 0;
  106.         int i;
  107.     
  108.         for(i = 0; i < aDict->size; i++)
  109.         {
  110.             newNode = aDict->hashtable[i];
  111.         
  112.             while(newNode)
  113.             {
  114.                 nextNode = newNode->next;
  115.                 free(newNode->key);
  116.                 freer(newNode->value);
  117.                 free(newNode);
  118.                 newNode = nextNode;
  119.             }
  120.         
  121.             aDict->hashtable[i] = 0;
  122.         }
  123.     
  124.         if(aDict->hashtable) free(aDict->hashtable);
  125.  
  126.         free(aDict);
  127.         
  128.         aDict = 0;
  129.     }
  130. }
  131.  
  132. int dict_isKey(Dictionary aDict, const char *aStr)
  133. {
  134.     return (dict_valueForKey(aDict, aStr)) ? 1 : 0;
  135. }
  136.  
  137. void * dict_setValueForKey(Dictionary aDict, const char *aKey, void *theValue)
  138. {
  139.     void * valueToReturn = 0;
  140.     
  141.     if(aKey)
  142.     {
  143.         unsigned long index;
  144.         struct listnode *node = 0;
  145.         
  146.         index = (stringHash(aKey) % (aDict->size));
  147.         
  148.         node = aDict->hashtable[index];
  149.         
  150.         if(node){
  151.         
  152.             do
  153.             {
  154.                 if( node->key && (0 == strcmp(aKey,node->key)) )
  155.                 {
  156.                     valueToReturn = node->value;/*cache the old one and*/
  157.                     
  158.                     node->value = theValue;/*replace it*/
  159.                 }
  160.                 else
  161.                 {
  162.                     node = node->next;
  163.                 }
  164.                 
  165.             }while((!valueToReturn)&& node);
  166.         
  167.         }
  168.         
  169.         if(!valueToReturn)
  170.         {
  171.             node = (struct listnode *) calloc(1,sizeof(struct listnode));
  172.             
  173.             node->key = (char *)malloc(sizeof(char) * (strlen(aKey) + 1));
  174.             strcpy(node->key,aKey);
  175.             
  176.             node->value = theValue;
  177.             node->next = aDict->hashtable[index];
  178.             
  179.             aDict->hashtable[index]= node;
  180.             
  181.             aDict->used++;
  182.             
  183.             /*check if we need to grow*/
  184.             if(aDict->used >= (GROW_PERCENTAGE * aDict->size)){
  185.             
  186.                 struct listnode **newTable;
  187.                 int newS = GROWTH_RATE * aDict->size, newUsed = 0;
  188.                 DictState iterator;
  189.                 struct listnode *newNode = 0;
  190.                 struct listnode *nextNode = 0;
  191.                 unsigned long curIndex, i;
  192.                 
  193.                 
  194.                 iterator = dict_initState(aDict);
  195.                 
  196.                 newS = ceilPrime(newS);
  197.                 
  198.                 newTable = (struct listnode **) calloc(newS,sizeof(struct listnode *));
  199.                 
  200.                 while(dict_nextState(&iterator))
  201.                 {
  202.                 
  203.                     curIndex = (stringHash(iterator.curNode->key) % (newS));
  204.                     
  205.                     newNode = 
  206.                         (struct listnode *) calloc(1,sizeof(struct listnode));
  207.                     
  208.                     newNode->key = iterator.curNode->key;
  209.                     newNode->value = iterator.curNode->value;
  210.                     newNode->next = newTable[curIndex];
  211.                     newTable[curIndex]= newNode;
  212.                     
  213.                     newUsed++;
  214.                 }
  215.                 
  216.                 for(i = 0; i < aDict-> size; i++)
  217.                 {
  218.                     newNode = aDict->hashtable[i];
  219.                     
  220.                     while(newNode)
  221.                     {
  222.                     
  223.                         nextNode = newNode->next;
  224.                         free(newNode);
  225.                         newNode = nextNode;
  226.                     
  227.                     }
  228.                     
  229.                     aDict->hashtable[i] = 0;
  230.                 
  231.                 }
  232.                 
  233.                 free(aDict->hashtable);
  234.                 
  235.                 aDict->hashtable = newTable;
  236.                 aDict->size = newS;
  237.                 aDict->used = newUsed;
  238.             }
  239.         }
  240.     }
  241.     
  242.     return valueToReturn;
  243. }
  244.  
  245.  
  246. void * dict_valueForKey(Dictionary aDict, const char *theKey)
  247. {
  248.     void * returnValue = 0;
  249.  
  250.     if( theKey &&( aDict->used > 0))
  251.     {
  252.         unsigned long index;
  253.         struct listnode *node = 0;
  254.         
  255.         index = (stringHash(theKey) % (aDict->size));
  256.         node = aDict->hashtable[index];
  257.         
  258.         if(node)
  259.         {
  260.             do
  261.             {
  262.                 if( node->key && (0 == strcmp(theKey,node->key)) )
  263.                 {
  264.                     returnValue = node->value;
  265.                 }
  266.                 else
  267.                 {
  268.                     node = node->next;
  269.                 }
  270.             
  271.             }while( !returnValue && node);
  272.         }
  273.     }
  274.     
  275.     return returnValue;
  276. }
  277.  
  278. void * dict_orphanValueForKey(Dictionary aDict, const char *theKey)
  279. {
  280.     void * returnValue = 0;
  281.  
  282.     if( theKey &&( aDict->used > 0))
  283.     {
  284.         unsigned long index;
  285.         struct listnode *node = 0;
  286.         struct listnode *prevNode = 0;
  287.         
  288.         index = (stringHash(theKey) % (aDict->size));
  289.         node = aDict->hashtable[index];
  290.         
  291.         if(node)
  292.         {
  293.             if(node->key && (0 == strcmp(theKey,node->key)))
  294.             {
  295.                 aDict->hashtable[index] = node->next;
  296.                 returnValue = node->value;
  297.                 
  298.                 free(node->key);
  299.                 node->key = 0;
  300.                 
  301.                 free(node);
  302.                 
  303.                 aDict->used--;
  304.             }
  305.             else
  306.             {
  307.                 while( returnValue && node)
  308.                 {
  309.                 
  310.                     if(node->key && (0 == strcmp(theKey,node->key)))
  311.                     {
  312.                         prevNode->next = node->next;
  313.                         returnValue = node->value;
  314.                         
  315.                         free(node->key);
  316.                         node->key = 0;
  317.                         
  318.                         free(node);
  319.                         
  320.                         aDict->used--;
  321.                     }
  322.                     else
  323.                     {
  324.                         prevNode = node;
  325.                         node = node->next;
  326.                     }
  327.                 }
  328.             }
  329.         }
  330.     }
  331.     
  332.     return returnValue;
  333. }
  334.  
  335. DictState dict_initState(Dictionary aDict)
  336. {
  337.     DictState retVal;
  338.     
  339.     retVal.curIndex = -1;
  340.     retVal.curNode = (struct listnode *) 0;
  341.     retVal.bumpedCurNode = 0;
  342.     retVal.dict = aDict;
  343.     
  344.     return retVal;
  345. }
  346.  
  347.  
  348. int dict_nextState(DictState *aState)
  349. {
  350.     int foundAnotherNode = 0;
  351.     struct listnode *nextNode;
  352.     
  353.     if(aState->curNode){
  354.     
  355.         if(aState->bumpedCurNode)
  356.         {
  357.             foundAnotherNode = 1;
  358.         }
  359.         else/* we have a node, try to find the next one at that slot */
  360.         {
  361.             nextNode = aState->curNode->next;
  362.             
  363.             if(nextNode)/* found one in this slot */
  364.             {
  365.                 aState->curNode = nextNode;
  366.                 foundAnotherNode = 1;
  367.             }
  368.             else/* move to the next slot */
  369.             {
  370.                 aState->curIndex++;
  371.             }
  372.         }
  373.     }
  374.     
  375.     if(!foundAnotherNode)
  376.     {
  377.     
  378.         if(aState->curIndex == -1) aState->curIndex = 0;
  379.         
  380.         while(aState->curIndex < aState->dict->size)
  381.         {
  382.             nextNode = aState->dict->hashtable[aState->curIndex];
  383.             
  384.             if(nextNode)
  385.             {
  386.                 aState->curNode = nextNode;
  387.                 foundAnotherNode = 1;
  388.                 break;
  389.             }
  390.             else
  391.             {
  392.                     aState->curIndex++;
  393.             }
  394.     
  395.         }
  396.     
  397.     }
  398.     
  399.     aState->bumpedCurNode = 0;
  400.      
  401.     return foundAnotherNode;
  402. }
  403.  
  404. void dict_printToStdout(Dictionary theDict)
  405. {
  406.     DictState state;
  407.     
  408.     /* Create a dictionary state */
  409.     state = dict_initState(theDict);
  410.  
  411.     while(dict_nextState(&state))
  412.     {
  413.         printf("%s = %s\n",state.curNode->key,(char *)state.curNode->value);
  414.     }
  415. }
  416.