home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 3 / AACD03.BIN / AACD / Programming / sofa / archive / exml.lha / exml / expat / xmlparse / hashtable.c next >
C/C++ Source or Header  |  1999-04-13  |  3KB  |  135 lines
  1. /*
  2. The contents of this file are subject to the Mozilla Public License
  3. Version 1.0 (the "License"); you may not use this file except in
  4. csompliance with the License. You may obtain a copy of the License at
  5. http://www.mozilla.org/MPL/
  6.  
  7. Software distributed under the License is distributed on an "AS IS"
  8. basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
  9. License for the specific language governing rights and limitations
  10. under the License.
  11.  
  12. The Original Code is expat.
  13.  
  14. The Initial Developer of the Original Code is James Clark.
  15. Portions created by James Clark are Copyright (C) 1998
  16. James Clark. All Rights Reserved.
  17.  
  18. Contributor(s):
  19. */
  20.  
  21. #include <stdlib.h>
  22. #include <string.h>
  23.  
  24. #include "xmldef.h"
  25. #include "hashtable.h"
  26.  
  27. #ifdef XML_UNICODE
  28. #define keycmp wcscmp
  29. #else
  30. #define keycmp strcmp
  31. #endif
  32.  
  33. #define INIT_SIZE 64
  34.  
  35. static
  36. unsigned long hash(KEY s)
  37. {
  38.   unsigned long h = 0;
  39.   while (*s)
  40.     h = (h << 5) + h + (unsigned char)*s++;
  41.   return h;
  42. }
  43.  
  44. NAMED *lookup(HASH_TABLE *table, KEY name, size_t createSize)
  45. {
  46.   size_t i;
  47.   if (table->size == 0) {
  48.     if (!createSize)
  49.       return 0;
  50.     table->v = calloc(INIT_SIZE, sizeof(NAMED *));
  51.     if (!table->v)
  52.       return 0;
  53.     table->size = INIT_SIZE;
  54.     table->usedLim = INIT_SIZE / 2;
  55.     i = hash(name) & (table->size - 1);
  56.   }
  57.   else {
  58.     unsigned long h = hash(name);
  59.     for (i = h & (table->size - 1);
  60.          table->v[i];
  61.          i == 0 ? i = table->size - 1 : --i) {
  62.       if (keycmp(name, table->v[i]->name) == 0)
  63.     return table->v[i];
  64.     }
  65.     if (!createSize)
  66.       return 0;
  67.     if (table->used == table->usedLim) {
  68.       /* check for overflow */
  69.       size_t newSize = table->size * 2;
  70.       NAMED **newV = calloc(newSize, sizeof(NAMED *));
  71.       if (!newV)
  72.     return 0;
  73.       for (i = 0; i < table->size; i++)
  74.     if (table->v[i]) {
  75.       size_t j;
  76.       for (j = hash(table->v[i]->name) & (newSize - 1);
  77.            newV[j];
  78.            j == 0 ? j = newSize - 1 : --j)
  79.         ;
  80.       newV[j] = table->v[i];
  81.     }
  82.       free(table->v);
  83.       table->v = newV;
  84.       table->size = newSize;
  85.       table->usedLim = newSize/2;
  86.       for (i = h & (table->size - 1);
  87.        table->v[i];
  88.        i == 0 ? i = table->size - 1 : --i)
  89.     ;
  90.     }
  91.   }
  92.   table->v[i] = calloc(1, createSize);
  93.   if (!table->v[i])
  94.     return 0;
  95.   table->v[i]->name = name;
  96.   (table->used)++;
  97.   return table->v[i];
  98. }
  99.  
  100. void hashTableDestroy(HASH_TABLE *table)
  101. {
  102.   size_t i;
  103.   for (i = 0; i < table->size; i++) {
  104.     NAMED *p = table->v[i];
  105.     if (p)
  106.       free(p);
  107.   }
  108.   free(table->v);
  109. }
  110.  
  111. void hashTableInit(HASH_TABLE *p)
  112. {
  113.   p->size = 0;
  114.   p->usedLim = 0;
  115.   p->used = 0;
  116.   p->v = 0;
  117. }
  118.  
  119. void hashTableIterInit(HASH_TABLE_ITER *iter, const HASH_TABLE *table)
  120. {
  121.   iter->p = table->v;
  122.   iter->end = iter->p + table->size;
  123. }
  124.  
  125. NAMED *hashTableIterNext(HASH_TABLE_ITER *iter)
  126. {
  127.   while (iter->p != iter->end) {
  128.     NAMED *tem = *(iter->p)++;
  129.     if (tem)
  130.       return tem;
  131.   }
  132.   return 0;
  133. }
  134.  
  135.