dict.cpp
上传用户:zhongxx05
上传日期:2007-06-06
资源大小:33641k
文件大小:6k
源码类别:

Symbian

开发平台:

C/C++

  1. /* ***** BEGIN LICENSE BLOCK ***** 
  2.  * Version: RCSL 1.0/RPSL 1.0 
  3.  *  
  4.  * Portions Copyright (c) 1995-2002 RealNetworks, Inc. All Rights Reserved. 
  5.  *      
  6.  * The contents of this file, and the files included with this file, are 
  7.  * subject to the current version of the RealNetworks Public Source License 
  8.  * Version 1.0 (the "RPSL") available at 
  9.  * http://www.helixcommunity.org/content/rpsl unless you have licensed 
  10.  * the file under the RealNetworks Community Source License Version 1.0 
  11.  * (the "RCSL") available at http://www.helixcommunity.org/content/rcsl, 
  12.  * in which case the RCSL will apply. You may also obtain the license terms 
  13.  * directly from RealNetworks.  You may not use this file except in 
  14.  * compliance with the RPSL or, if you have a valid RCSL with RealNetworks 
  15.  * applicable to this file, the RCSL.  Please see the applicable RPSL or 
  16.  * RCSL for the rights, obligations and limitations governing use of the 
  17.  * contents of the file.  
  18.  *  
  19.  * This file is part of the Helix DNA Technology. RealNetworks is the 
  20.  * developer of the Original Code and owns the copyrights in the portions 
  21.  * it created. 
  22.  *  
  23.  * This file, and the files included with this file, is distributed and made 
  24.  * available on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 
  25.  * EXPRESS OR IMPLIED, AND REALNETWORKS HEREBY DISCLAIMS ALL SUCH WARRANTIES, 
  26.  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS 
  27.  * FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 
  28.  * 
  29.  * Technology Compatibility Kit Test Suite(s) Location: 
  30.  *    http://www.helixcommunity.org/content/tck 
  31.  * 
  32.  * Contributor(s): 
  33.  *  
  34.  * ***** END LICENSE BLOCK ***** */ 
  35. #include "hlxclib/string.h"
  36. #include "hxtypes.h"
  37. #include "dict.h"
  38. #include "hxheap.h"
  39. #ifdef _DEBUG
  40. #undef HX_THIS_FILE
  41. static const char HX_THIS_FILE[] = __FILE__;
  42. #endif
  43. unsigned int
  44. default_strhash(const char *key)
  45. { // Chris Torek's hash function
  46.     unsigned int h = 0x31fe;
  47.     while (*key)
  48. h = h*33 + *key++;
  49.     return h;
  50. }
  51. void
  52. Dict::init()
  53. {
  54.     _table = new Dict_entry*[_nbuckets];
  55.     for (unsigned int i = 0; i < _nbuckets; i++) 
  56. _table[i] = 0;
  57. }
  58. // Do this as a function (in case it's really a macro with args...need a
  59. // function ptr to use in Dict ctor.
  60. static int func_strcasecmp(const char* s1, const char* s2)
  61. {
  62.     return strcasecmp(s1, s2);
  63. }
  64. Dict::Dict(unsigned int nbuckets):
  65.     _count(0), _nbuckets(nbuckets),
  66.     _compare(func_strcasecmp), _hash(default_strhash)
  67. {
  68.     init();
  69. }
  70. Dict::Dict(int (*compare)(const char*, const char*),
  71.    unsigned int (*hash)(const char*), unsigned int nbuckets):
  72.     _count(0), _nbuckets(nbuckets),
  73.     _compare(compare), _hash(default_strhash)
  74. {
  75.     init();
  76. }
  77. Dict::~Dict()
  78. {
  79.     for (unsigned int i = 0; i < _nbuckets; i++)
  80.     {
  81. Dict_entry* nexte;
  82. for (Dict_entry* e = _table[i]; e != 0; e = nexte)
  83. {
  84.     nexte = e->next;
  85.     delete[] e->key;
  86.     delete e;
  87. }
  88.     }
  89.     delete[] _table;
  90. }
  91. Dict_entry*
  92. Dict::enter(Key key, void* obj)
  93. {
  94.     unsigned int h = _hash(key);
  95.     Dict_entry* e, *nexte;
  96.     for (e = _table[h%_nbuckets]; e != 0; e = e->next)
  97. if (_compare(key, e->key) == 0)
  98.     return e;
  99.     _count++;
  100.     // Grow the table if 66% full
  101.     unsigned int nb = _count*3;
  102.     if (nb > _nbuckets*2)
  103.     {
  104. Dict_entry** tab = new Dict_entry*[nb];
  105. unsigned int i;
  106. for (i = 0; i < nb; i++)
  107. {
  108.     tab[i] = 0;
  109. }
  110. #ifdef XXXAAK_AWAITING_CR
  111. memset(tab, 0, nb * sizeof(Dict_entry *));
  112. #endif
  113. for (i = 0; i < _nbuckets; i++)
  114. {
  115.     for (e = _table[i]; e != 0; e = nexte)
  116.     {
  117. nexte = e->next;
  118. e->next = tab[e->hash%nb];
  119. tab[e->hash%nb] = e;
  120.     }
  121. }
  122. delete[] _table;
  123. _table = tab;
  124. _nbuckets = nb;
  125.     }
  126.     e = new Dict_entry;
  127.     e->next = _table[h%_nbuckets];
  128.     e->key = new char[strlen(key)+1];
  129.     e->hash = h;
  130.     strcpy(e->key, key); /* Flawfinder: ignore */
  131.     e->obj = obj;
  132.     _table[h%_nbuckets] = e;
  133.     return e;
  134. }
  135. void*
  136. Dict::remove(Key key)
  137. {
  138.     Dict_entry* e, **ep;
  139.     unsigned int h = _hash(key);
  140.     int h_index = h%_nbuckets;
  141.     for (ep = &_table[h%_nbuckets]; (e = *ep) != 0; ep = &e->next)
  142.     {
  143. if (_compare(key, e->key) != 0)
  144.     continue;
  145. void* obj = e->obj;
  146. *ep = e->next;
  147. delete[] e->key;
  148. delete e;
  149. --_count;
  150. return obj;
  151.     }
  152.     return 0;       
  153. }
  154. Dict_entry*
  155. Dict::find(Key key)
  156. {
  157.     unsigned int h = _hash(key);
  158.     for (Dict_entry* e = _table[h%_nbuckets]; e != 0; e = e->next)
  159. if (strcasecmp(key, e->key) == 0)
  160.     return e;
  161.     return 0;
  162. }
  163. void
  164. Dict::next(unsigned int& h, Dict_entry*& e)
  165. {
  166.     e = e->next;
  167.     if (e)
  168. return;
  169.     for (unsigned int i = h+1; i < _nbuckets; i++)
  170.     {
  171. if (_table[i] == 0)
  172.     continue;
  173. e = _table[i];
  174. h = i;
  175. return;
  176.     }
  177.     e = 0;
  178. }
  179. #ifdef XXXAAK_AWAITING_CR
  180. Dict_entry*
  181. Dict::enter(Key key, void* obj, UINT32& hashId)
  182. {
  183.     unsigned int h = hashId =_hash(key);
  184.     Dict_entry* e, *nexte;
  185.     for (e = _table[h%_nbuckets]; e != 0; e = e->next)
  186. if (h == e->hash)
  187.     return e;
  188.     _count++;
  189.     // Grow the table if 66% full
  190.     unsigned int nb = _count*3;
  191.     if (nb > _nbuckets*2)
  192.     {
  193. Dict_entry** tab = new Dict_entry*[nb];
  194. unsigned int i;
  195. memset(tab, 0, nb * sizeof(Dict_entry *));
  196. for (i = 0; i < _nbuckets; i++)
  197. {
  198.     for (e = _table[i]; e != 0; e = nexte)
  199.     {
  200. nexte = e->next;
  201. e->next = tab[e->hash%nb];
  202. tab[e->hash%nb] = e;
  203.     }
  204. }
  205. delete[] _table;
  206. _table = tab;
  207. _nbuckets = nb;
  208.     }
  209.     e = new Dict_entry;
  210.     e->next = _table[h%_nbuckets];
  211.     e->key = new char[strlen(key)+1];
  212.     e->hash = h;
  213.     strcpy(e->key, key); /* Flawfinder: ignore */
  214.     e->obj = obj;
  215.     _table[h%_nbuckets] = e;
  216.     return e;
  217. }
  218. void*
  219. Dict::remove(UINT32 hashId)
  220. {
  221.     if (!hashId)
  222. return 0;
  223.     Dict_entry* e, **ep;
  224.     int h_index = hashId%_nbuckets;
  225.     for (ep = &_table[hashId%_nbuckets]; (e = *ep) != 0; ep = &e->next)
  226.     {
  227. if (hashId != e->hash)
  228.     continue;
  229. void* obj = e->obj;
  230. *ep = e->next;
  231. delete[] e->key;
  232. delete e;
  233. --_count;
  234. return obj;
  235.     }
  236.     return 0;       
  237. }
  238. Dict_entry*
  239. Dict::find(UINT32 hashId)
  240. {
  241.     if (!hashId)
  242. return 0;
  243.     for (Dict_entry* e = _table[hashId%_nbuckets]; e != 0; e = e->next)
  244. if (hashId == e->hash)
  245.     return e;
  246.     return 0;
  247. }
  248. #endif