chxmapstringtoob.h
上传用户:zhongxx05
上传日期:2007-06-06
资源大小:33641k
文件大小:11k
源码类别:

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. #ifndef _CHXMAPSTRINGTOOB_H_
  36. #define _CHXMAPSTRINGTOOB_H_
  37. // Notes...
  38. //
  39. // Since we aren't using templates, we get to copy the same basic code all
  40. // over the place.  So, if you change something in this class, chances are
  41. // that the other CHXMap*To* classes may need the change as well.
  42. // XXXSAB: Need to better abstract out the common code...
  43. //
  44. // This implementation has a few dynamically resized vectors - their
  45. // "chunk sizes" (number of elements added to size when a new element
  46. // addition requires a reallocation) can be adjusted via the following
  47. // accessors.
  48. //
  49. //    m_items - This is the vector of actual key/value pairs (along with a
  50. //        boolean "free" flag) where the data for the map is stored.  It's
  51. //        chunk size is controlled via the optional argument to the map
  52. //        ctor.  And the default value for that is controlled by the
  53. //        static SetDefaultChunkSize() method.
  54. //
  55. //    m_buckets - This is the vector of hash buckets.  Each hash bucket is
  56. //        a vector of int indices into the m_items vector.  The number of
  57. //        buckets doesn't change over time and is controlled via the
  58. //        InitHashTable() method (which has the effect of resetting the
  59. //        map) and it defaults to z_defaultNumBuckets (101 at the moment).
  60. //        The chunk size of the individual hash buckets is set by the
  61. //        SetBucketChunkSize() method and the default for that is set by
  62. //        the SetDefaultBucketChunkSize() method.
  63. //
  64. #include "hxtypes.h"
  65. #include "carray.h"
  66. #include "hxstring.h"
  67. #include "hxmaputils.h"
  68. #include "chxmapbuckets.h"
  69. #include "hlxclib/string.h"     // strcasecmp()
  70. class CHXMapStringToOb
  71. {
  72. public:
  73.     typedef const char* key_type;
  74.     typedef const char* key_arg_type;
  75.     typedef const char* key_ref_type;
  76.     inline static CHXString& key_nil() { return (CHXString&)HXEmptyString; }
  77.     typedef void* value_type;
  78.     typedef void* value_arg_type;
  79.     typedef void*& value_ref_type;
  80.     typedef void* value_const_ref_type;
  81.     inline static value_ref_type val_nil() { static const value_type p = 0; return (value_ref_type)p; }
  82.     struct Item
  83.     {
  84.         Item (key_arg_type key_ = key_nil(),
  85.               value_arg_type val_ = val_nil(),
  86.               bool bFree_ = true) :
  87.             key(key_), val(val_), bFree(bFree_)
  88.         {}
  89.         CHXString  key;
  90.         value_type val;
  91.         bool  bFree;
  92.     };
  93.     DECLARE_ITEMVEC(ItemVec_t,Item,Item(),0,0);
  94.     class Iterator
  95.     {
  96.     public:
  97.         typedef key_type iter_key_type;
  98.         friend class CHXMapStringToOb;
  99.         // NOTE: (item == -1) is used to mean "set to end of pItems".
  100.         Iterator(ItemVec_t* pItems = NULL,
  101.                  int item = -1);
  102.         // NOTE: Values of 'next' copied into iterator...since this
  103.         //       iterator is caching key/value and doesn't return a
  104.         //       value_type&, it can't be used to modify the values in the
  105.         //       map.
  106.         Iterator& operator++();
  107.         Iterator  operator++(int); // XXXSAB: tested?
  108.         BOOL operator==(const Iterator&) const;
  109.         BOOL operator!=(const Iterator&) const;
  110.         value_type operator*(); // returns the 'value'
  111.         iter_key_type get_key  ();   // returns the 'key'
  112.     private:
  113.         void GotoValid();
  114.         ItemVec_t*      m_pItems;
  115.         int             m_item;
  116.         // cached key/value
  117.         CHXString       m_key;
  118.         value_type      m_val;
  119.     };
  120. private:
  121. #if defined(HELIX_CONFIG_NOSTATICS)
  122.     static const ULONG32 z_defaultNumBuckets;
  123.     static const ULONG32 z_defaultChunkSize;
  124.     static const ULONG32 z_defaultBucketChunkSize;
  125. #else
  126.     static ULONG32 z_defaultNumBuckets;
  127.     static ULONG32 z_defaultChunkSize;
  128.     static ULONG32 z_defaultBucketChunkSize;
  129. #endif
  130.     
  131. public:
  132.     // Construction
  133.     // NOTE: Chunk size is the number of key/value pairs to grow by each
  134.     //       time one of the hash buckets needs to be grown.
  135.     CHXMapStringToOb(int chunkSize = z_defaultChunkSize);
  136.     ~CHXMapStringToOb();
  137.     // Attributes
  138.     inline int GetCount() const;
  139.     inline BOOL IsEmpty() const;
  140.     BOOL Lookup(key_arg_type key, value_arg_type& value) const;
  141.     POSITION Lookup(key_arg_type key) const;
  142.     // XXXSAB: I added GetKeyAt() and GetAt() since there was previously
  143.     //         no easy way to get those data without advancing the
  144.     //         POSITION.
  145.     key_ref_type GetKeyAt(POSITION pos) const;
  146.     value_const_ref_type GetAt(POSITION pos) const;
  147.     value_ref_type GetAt(POSITION pos);
  148.     // Lookup & add if not there
  149.     value_ref_type operator[](key_arg_type key);
  150.     // add a new (key, value) pair
  151.     POSITION SetAt(key_arg_type key, value_arg_type value);
  152.     // remove existing (key, ?) pair
  153.     POSITION Remove(key_arg_type key);
  154.     BOOL RemoveKey(key_arg_type key);
  155.     void RemoveAll();
  156.     // Iteration
  157.     POSITION GetStartPosition() const;
  158.     void GetNextAssoc (POSITION& pos, key_arg_type& key, value_arg_type& value) const;
  159.     // CHXString Helper...
  160.     void GetNextAssoc (POSITION& pos, CHXString& key, value_arg_type& value) const
  161.     {
  162.         const char* sz = NULL;
  163.         GetNextAssoc (pos, sz, value);
  164.         if (sz) key = sz;
  165.     }
  166.     Iterator Begin();
  167.     Iterator End();
  168.     Iterator Erase(Iterator it);
  169.     // XXXSAB: Added Find() command to parallel STL style method
  170.     Iterator Find(key_arg_type key);
  171.     // Returns the number of hash buckets
  172.     inline ULONG32 GetHashTableSize() const;
  173.     // This will reset the internal storage so that any the map will be
  174.     // empty when this returns.
  175.     // NOTE: This function always allocates some data - the bAlloc flag is
  176.     //       for compatibility with an old interface and is ignored.
  177.     HX_RESULT InitHashTable(ULONG32 numBuckets = z_defaultNumBuckets,
  178.                        BOOL bAlloc = TRUE);
  179.     // defaults to on. Set this before you add anything! And make sure
  180.     // that if you set a hash function that it's behavior matches the case
  181.     // sensitivity flag.
  182.     void SetCaseSensitive(BOOL bCaseSens) { m_bCaseSens = bCaseSens ? true : false; }
  183.     typedef ULONG32 (*HashFunc_t) (key_arg_type key);
  184.     static ULONG32 DefaultHashFunc (key_arg_type key)
  185.     {
  186.         return HlxMap::StrHashFunc(key, true);
  187.     }
  188.     static ULONG32 DefaultNoCaseHashFunc (key_arg_type key)
  189.     {
  190.         return HlxMap::StrHashFunc(key, false);
  191.     }
  192.     inline HashFunc_t SetHashFunc (HashFunc_t hf = DefaultHashFunc); // XXXSAB: tested???
  193.     // Overrideables: special non-virtual (XXXSAB: Huh?)
  194.     inline ULONG32 HashKey(key_arg_type key) const;
  195.     inline static void SetDefaultNumBuckets (ULONG32 numBuckets);
  196.     inline static void SetDefaultChunkSize (ULONG32 chunkSize);
  197.     inline static void SetDefaultBucketChunkSize (ULONG32 chunkSize);
  198.     inline void SetBucketChunkSize (ULONG32 chunkSize);
  199.     // In _DEBUG mode, this does a bunch of DPRINTF's...
  200.     void Dump() const;
  201. private:
  202.     inline BOOL Lookup(key_arg_type key, int& retItem) const;
  203.     BOOL LookupInBucket(ULONG32 bucket, key_arg_type key, int& retItem) const;
  204.     Item* LookupItem(ULONG32 bucket, key_arg_type key);
  205.     inline const Item* LookupItem(ULONG32 bucket, key_arg_type key) const
  206.     {
  207.         return ((CHXMapStringToOb*)this)->LookupItem(bucket, key);
  208.     }
  209.     // Internal function - key already verified not to exist
  210.     BOOL AddToBucket(ULONG32 bucket, key_arg_type key, value_arg_type value, int& retItem);
  211.     inline POSITION Item2Pos(int item) const;
  212.     inline int Pos2Item(POSITION pos) const;
  213. private:
  214.     HashFunc_t          m_hf;
  215.     ItemVec_t           m_items;
  216.     HlxMap::IntVec_t    m_free;
  217.     CHlxMapBuckets      m_buckets;
  218.     ULONG32             m_numBuckets;
  219.     ULONG32             m_chunkSize;
  220.     ULONG32             m_bucketChunkSize;
  221.     // Members specific to the type of key and/or value goes below here.
  222.     void ConstructTypeSpecifics();
  223.     inline BOOL IsKeyMatch (key_arg_type k1, key_arg_type k2) const
  224.     {
  225.         BOOL bRet;
  226.         if (m_bCaseSens) bRet = (strcmp(k1, k2) == 0);
  227.         else bRet = (strcasecmp(k1, k2) == 0);
  228. #ifdef XXXSAB
  229.         printf ("IsKeyMatch("%s", "%s") -> %sn",
  230.                 k1, k2,
  231.                 bRet ? "true" : "false");
  232. #endif /* XXXSAB */
  233.         return bRet;
  234.     }
  235.     bool                m_bCaseSens;
  236. };
  237. int CHXMapStringToOb::GetCount() const
  238. {
  239.     return m_items.size() - m_free.size();
  240. }
  241. BOOL CHXMapStringToOb::IsEmpty() const
  242. {
  243.     return GetCount() == 0;
  244. }
  245. ULONG32 CHXMapStringToOb::GetHashTableSize() const
  246. {
  247.     return m_numBuckets;
  248. }
  249. CHXMapStringToOb::HashFunc_t CHXMapStringToOb::SetHashFunc (
  250.     CHXMapStringToOb::HashFunc_t hf)
  251. {
  252.     HashFunc_t old = m_hf;
  253.     m_hf = hf;
  254.     return old;
  255. }
  256. ULONG32 CHXMapStringToOb::HashKey (key_arg_type key) const
  257. {
  258.     if (m_hf) return m_hf(key);
  259.     return m_bCaseSens ? DefaultHashFunc(key) : DefaultNoCaseHashFunc(key);
  260. }
  261. void CHXMapStringToOb::SetDefaultNumBuckets (ULONG32 numBuckets)
  262. {
  263. #if !defined(HELIX_CONFIG_NOSTATICS)
  264.     z_defaultNumBuckets = numBuckets;
  265. #endif
  266. }
  267. void CHXMapStringToOb::SetDefaultChunkSize (ULONG32 chunkSize)
  268. {
  269. #if !defined(HELIX_CONFIG_NOSTATICS)
  270.     z_defaultChunkSize = chunkSize;
  271. #endif
  272. }
  273. void CHXMapStringToOb::SetDefaultBucketChunkSize (ULONG32 chunkSize)
  274. {
  275. #if !defined(HELIX_CONFIG_NOSTATICS)
  276.     z_defaultBucketChunkSize = chunkSize;
  277. #endif
  278. }
  279. void CHXMapStringToOb::SetBucketChunkSize (ULONG32 chunkSize)
  280. {
  281.     m_bucketChunkSize = chunkSize;
  282. }
  283. #endif // _CHXMAPSTRINGTOOB_H_