Dictionary.c++
上传用户:weiyuanprp
上传日期:2020-05-20
资源大小:1169k
文件大小:8k
源码类别:

传真(Fax)编程

开发平台:

C/C++

  1. /* $Id: Dictionary.c++,v 1.1.1.1 2005/11/11 21:32:03 faxguy Exp $ */
  2. /*
  3.  * Copyright (c) 1990-1996 Sam Leffler
  4.  * Copyright (c) 1991-1996 Silicon Graphics, Inc.
  5.  * HylaFAX is a trademark of Silicon Graphics
  6.  *
  7.  * Permission to use, copy, modify, distribute, and sell this software and 
  8.  * its documentation for any purpose is hereby granted without fee, provided
  9.  * that (i) the above copyright notices and this permission notice appear in
  10.  * all copies of the software and related documentation, and (ii) the names of
  11.  * Sam Leffler and Silicon Graphics may not be used in any advertising or
  12.  * publicity relating to the software without the specific, prior written
  13.  * permission of Sam Leffler and Silicon Graphics.
  14.  * 
  15.  * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, 
  16.  * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY 
  17.  * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.  
  18.  * 
  19.  * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
  20.  * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
  21.  * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  22.  * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF 
  23.  * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE 
  24.  * OF THIS SOFTWARE.
  25.  */
  26. #include "Dictionary.h"
  27. #define DEFAULTSIZE 31
  28. fxIMPLEMENT_PtrArray(fxDictBuckets,fxDictBucket *)
  29. fxIMPLEMENT_PtrArray(fxDictIters, fxDictIter *)
  30. #define KEYAT(base) (base)
  31. #define VALUEAT(base) (void*)(((char*)base) + keysize)
  32. #define KEY(b) KEYAT((b)->kvmem)
  33. #define VALUE(b) VALUEAT((b)->kvmem)
  34. fxDictionary::fxDictionary(u_int ksize, u_int vsize,u_int initsize)
  35. {
  36.     if (initsize == 0) initsize = DEFAULTSIZE;
  37.     buckets.resize(initsize);
  38.     keysize = ksize;
  39.     valuesize = vsize;
  40.     numItems = 0;
  41. }
  42. fxDictionary::fxDictionary(const fxDictionary& a)
  43. {
  44.     for (u_int i = 0; i < a.buckets.length(); i++) {
  45. const fxDictBucket* sb = a.buckets[i];
  46. while (sb) {
  47.     addInternal(KEY(sb),VALUE(sb));
  48.     sb = sb->next;
  49. }
  50.     }
  51. }
  52. fxDictionary::~fxDictionary()
  53. {
  54. }
  55. void fxDictionary::cleanup()
  56. {
  57.     u_int i;
  58.     u_int l = buckets.length();
  59.     for (i=0; i < l; i++) {
  60. fxDictBucket* bucket = buckets[i];
  61. while (bucket) {
  62.     fxDictBucket* bucket2 = bucket->next;
  63.     destroyKey(KEY(bucket));
  64.     destroyValue(VALUE(bucket));
  65.     delete bucket;
  66.     bucket = bucket2;
  67. }
  68. buckets[i] = 0;
  69.     }
  70.     l = iters.length();
  71.     for (i=0; i < l; i++) {
  72. iters[i]->dict = 0;
  73. iters[i]->node = 0;
  74. iters[i]->invalid = true;
  75.     }
  76. }
  77. fxDictBucket::~fxDictBucket()
  78. {
  79.     if (kvmem) free(kvmem);
  80. }
  81. void
  82. fxDictionary::operator=(const fxDictionary &a)
  83. {
  84.     assert(keysize == a.getKeySize());
  85.     assert(valuesize == a.getValueSize());
  86.     if (this == &a) return;
  87.     this->fxDictionary::~fxDictionary(); // NB: need this for HP C++ 3.4
  88.     for (u_int i = 0; i < a.buckets.length(); i++) {
  89. const fxDictBucket* db = a.buckets[i];
  90. while (db) {
  91.     addInternal(KEY(db), VALUE(db));
  92.     db = db->next;
  93. }
  94.     }
  95. }
  96. void
  97. fxDictionary::addInternal(const void* key, const void* value)
  98. {
  99.     u_int index = (u_int)(hashKey(key) % buckets.length());
  100.     fxDictBucket* bucket = buckets[index];
  101.     while (bucket && compareKeys(key,KEY(bucket))) {
  102. bucket = bucket->next;
  103.     }
  104.     if (bucket) {  // just change the value
  105. destroyValue(VALUE(bucket));
  106. copyValue(value,VALUE(bucket));
  107. return;
  108.     } else {
  109. void * kvmem = malloc(keysize + valuesize);
  110. copyKey(key,KEYAT(kvmem));
  111. copyValue(value,VALUEAT(kvmem));
  112. fxDictBucket* newbucket = new fxDictBucket(kvmem,buckets[index]);
  113. buckets[index] = newbucket;
  114. numItems++;
  115.     }
  116. }
  117. const void*
  118. fxDictionary::find(const void* key, const void **keyp) const
  119. {
  120.     u_int index = (u_int)(hashKey(key) % buckets.length());
  121.     const fxDictBucket* bucket = buckets[index];
  122.     while (bucket && compareKeys(key,KEY(bucket))) bucket = bucket->next;
  123.     if (bucket) {
  124. if (keyp != 0) *keyp = &KEY(bucket);
  125. return VALUE(bucket);
  126.     } else {
  127. if (keyp != 0) *keyp = 0;
  128. return 0;
  129.     }
  130. }
  131. void*
  132. fxDictionary::findCreate(const void* key)
  133. {
  134.     u_int index = (u_int)(hashKey(key) % buckets.length());
  135.     fxDictBucket* bucket = buckets[index];
  136.     while (bucket && compareKeys(key,KEY(bucket))) bucket = bucket->next;
  137.     if (bucket)
  138. return VALUE(bucket);
  139.     else {
  140. char* kvmem = (char*)malloc(keysize + valuesize);
  141. copyKey(key,KEYAT(kvmem));
  142. createValue(VALUEAT(kvmem));
  143. fxDictBucket* bucket = new fxDictBucket(kvmem,buckets[index]);
  144. buckets[index] = bucket;
  145. numItems++;
  146. return VALUEAT(kvmem);
  147.     }
  148. }
  149. void
  150. fxDictionary::remove(const void* key)
  151. {
  152.     u_int index = (u_int)(hashKey(key) % buckets.length());
  153.     fxDictBucket* bucket = buckets[index];
  154.     fxDictBucket** prev = &buckets[index];
  155.     while (bucket && compareKeys(key,KEY(bucket))) {
  156. prev = &bucket->next;
  157. bucket = bucket->next;
  158.     }
  159.     if (bucket) {
  160. *prev = bucket->next;
  161. destroyKey(KEY(bucket));
  162. destroyValue(VALUE(bucket));
  163. invalidateIters(bucket);
  164. delete bucket;
  165. numItems--;
  166.     }
  167. }
  168. void *
  169. fxDictionary::cut(const void* key)
  170. {
  171.     u_int index = (u_int)(hashKey(key) % buckets.length());
  172.     fxDictBucket* bucket = buckets[index];
  173.     fxDictBucket** prev = &buckets[index];
  174.     while (bucket && compareKeys(key,KEY(bucket))) {
  175. prev = &bucket->next;
  176. bucket = bucket->next;
  177.     }
  178.     if (bucket) {
  179. *prev = bucket->next;
  180. void * v = malloc(valuesize);
  181. memcpy(v,VALUE(bucket),valuesize);
  182. destroyKey(KEY(bucket));
  183. // no need to destroy value because it has moved to *v
  184. invalidateIters(bucket);
  185. delete bucket;
  186. numItems--;
  187. return v;
  188.     } else {
  189. return 0;
  190.     }
  191. }
  192. u_long
  193. fxDictionary::hashKey(const void* key) const
  194. {
  195.     u_long u = 0;
  196.     const u_long* p = (const u_long*)key;
  197.     u_int l = keysize;
  198.     while (l>=sizeof (u_long)) {
  199. u ^= *p++;
  200. l -= sizeof (u_long);
  201.     }
  202.     return u;
  203. }
  204. void fxDictionary::destroyKey(void *) const { }
  205. void fxDictionary::destroyValue(void *) const { }
  206. void
  207. fxDictionary::addIter(fxDictIter* i)
  208. {
  209.     iters.append(i);
  210. }
  211. void
  212. fxDictionary::removeIter(fxDictIter* i)
  213. {
  214.     iters.remove(iters.find(i));
  215. }
  216. void
  217. fxDictionary::invalidateIters(const fxDictBucket *db)
  218. {
  219.     u_int l = iters.length();
  220.     for (u_int i = 0; i<l; i++) {
  221. fxDictIter* di = iters[i];
  222. if (di->node == db) {
  223.     (*di)++;
  224.     if (di->dict) di->invalid = true;
  225. }
  226.     }
  227. }
  228. //----------------------------------------------------------------------
  229. fxDictIter::fxDictIter()
  230. {
  231.     invalid = false;
  232.     dict = 0;
  233.     bucket = 0;
  234.     node = 0;
  235. }
  236. fxDictIter::fxDictIter(fxDictionary& d)
  237. {
  238.     invalid = false;
  239.     dict = &d;
  240.     bucket = 0;
  241.     node = d.buckets[bucket];
  242.     d.addIter(this);
  243.     if (!node) advanceToValid();
  244. }
  245. fxDictIter::~fxDictIter()
  246. {
  247.     if (dict) dict->removeIter(this);
  248. }
  249. void
  250. fxDictIter::operator=(fxDictionary& d)
  251. {
  252.     if (dict) dict->removeIter(this);
  253.     dict = &d;
  254.     bucket = 0;
  255.     node = d.buckets[bucket];
  256.     invalid = false;
  257.     d.addIter(this);
  258.     if (!node) advanceToValid();
  259. }
  260. void *
  261. fxDictIter::getKey() const
  262. {
  263.     if (invalid) return 0;
  264.     else return KEY(node);
  265. }
  266. void *
  267. fxDictIter::getValue() const
  268. {
  269.     if (invalid) return 0;
  270.     else return (char *)node->kvmem + dict->keysize;
  271. }
  272. void
  273. fxDictIter::increment()
  274. {
  275.     if (!dict) return;
  276.     if (invalid) {
  277. invalid = false;
  278. return;
  279.     }
  280.     node = node->next;
  281.     if (node) return;
  282.     // otherwise, find another node!
  283.     advanceToValid();
  284. }
  285. void
  286. fxDictIter::advanceToValid()
  287. {
  288.     u_int len = dict->buckets.length();
  289.     fxDictBucket * n;
  290.     for(;;) {
  291. bucket++;
  292. assert(bucket<=len);
  293. if (bucket == len) {
  294.     dict->removeIter(this); // it's done with us
  295.     dict = 0;
  296.     invalid = true;
  297.     break;
  298. }
  299. if ((n = dict->buckets[bucket])) { // NB: intentional =
  300.     node = n;
  301.     invalid = false;
  302.     break;
  303. }
  304.     }
  305. }