home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / modules / xml / expat / xmlparse / hashtable.c next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  2.9 KB  |  128 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. compliance 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 "xmldef.h"
  22. #include "hashtable.h"
  23. #include <stdlib.h>
  24. #include <string.h>
  25.  
  26. #define INIT_SIZE 64
  27.  
  28. static
  29. unsigned long hash(const char *s)
  30. {
  31.   unsigned long h = 0;
  32.   while (*s)
  33.     h = (h << 5) + h + (unsigned char)*s++;
  34.   return h;
  35. }
  36.  
  37. NAMED *lookup(HASH_TABLE *table, const char *name, size_t createSize)
  38. {
  39.   size_t i;
  40.   if (table->size == 0) {
  41.     if (!createSize)
  42.       return 0;
  43.     table->v = calloc(INIT_SIZE, sizeof(NAMED *));
  44.     if (!table->v)
  45.       return 0;
  46.     table->size = INIT_SIZE;
  47.     table->usedLim = INIT_SIZE / 2;
  48.     i = hash(name) & (table->size - 1);
  49.   }
  50.   else {
  51.     unsigned long h = hash(name);
  52.     for (i = h & (table->size - 1);
  53.          table->v[i];
  54.          i == 0 ? i = table->size - 1 : --i) {
  55.       if (strcmp(name, table->v[i]->name) == 0)
  56.     return table->v[i];
  57.     }
  58.     if (!createSize)
  59.       return 0;
  60.     if (table->used == table->usedLim) {
  61.       /* check for overflow */
  62.       size_t newSize = table->size * 2;
  63.       NAMED **newV = calloc(newSize, sizeof(NAMED *));
  64.       if (!newV)
  65.     return 0;
  66.       for (i = 0; i < table->size; i++)
  67.     if (table->v[i]) {
  68.       size_t j;
  69.       for (j = hash(table->v[i]->name) & (newSize - 1);
  70.            newV[j];
  71.            j == 0 ? j = newSize - 1 : --j)
  72.         ;
  73.       newV[j] = table->v[i];
  74.     }
  75.       free(table->v);
  76.       table->v = newV;
  77.       table->size = newSize;
  78.       table->usedLim = newSize/2;
  79.       for (i = h & (table->size - 1);
  80.        table->v[i];
  81.        i == 0 ? i = table->size - 1 : --i)
  82.     ;
  83.     }
  84.   }
  85.   table->v[i] = calloc(1, createSize);
  86.   if (!table->v[i])
  87.     return 0;
  88.   table->v[i]->name = name;
  89.   (table->used)++;
  90.   return table->v[i];
  91. }
  92.  
  93. void hashTableDestroy(HASH_TABLE *table)
  94. {
  95.   size_t i;
  96.   for (i = 0; i < table->size; i++) {
  97.     NAMED *p = table->v[i];
  98.     if (p)
  99.       free(p);
  100.   }
  101.   free(table->v);
  102. }
  103.  
  104. void hashTableInit(HASH_TABLE *p)
  105. {
  106.   p->size = 0;
  107.   p->usedLim = 0;
  108.   p->used = 0;
  109.   p->v = 0;
  110. }
  111.  
  112. void hashTableIterInit(HASH_TABLE_ITER *iter, const HASH_TABLE *table)
  113. {
  114.   iter->p = table->v;
  115.   iter->end = iter->p + table->size;
  116. }
  117.  
  118. NAMED *hashTableIterNext(HASH_TABLE_ITER *iter)
  119. {
  120.   while (iter->p != iter->end) {
  121.     NAMED *tem = *(iter->p)++;
  122.     if (tem)
  123.       return tem;
  124.   }
  125.   return 0;
  126. }
  127.  
  128.