OpenAccess 2.2 API

00001 // *****************************************************************************
00002 // *****************************************************************************
00003 // oaHashTbl.h
00004 //
00005 // This file contains the definitions of the oaHashTbl class.
00006 //
00007 //  oaHashTbl
00008 //      This class implements a base class that can be used for all types of
00009 //      hash tables.
00010 //
00011 //  oaHashIter
00012 //      This class implements an iterator over all objects in a hash table.
00013 //
00014 // *****************************************************************************
00015 // Except as specified in the OpenAccess terms of use of Cadence or Silicon
00016 // Integration Initiative, this material may not be copied, modified,
00017 // re-published, uploaded, executed, or distributed in any way, in any medium,
00018 // in whole or in part, without prior written permission from Cadence.
00019 //
00020 //                Copyright 2002-2005 Cadence Design Systems, Inc.
00021 //                           All Rights Reserved.
00022 //
00023 //  $Author: icftcm $
00024 //  $Revision: #1 $
00025 //  $Date: 2010/08/09 $
00026 //  $State: Exp $
00027 // *****************************************************************************
00028 // *****************************************************************************
00029 
00030 
00031 
00032 #if !defined(oaHashTbl_P)
00033 #define oaHashTbl_P
00034 
00035 
00036 
00037 // *****************************************************************************
00038 // Nested includes
00039 // *****************************************************************************
00040 #include "oaCommonTypes.h"
00041 #include <ctype.h>
00042 
00043 
00044 
00045 // *****************************************************************************
00046 // Declare and define types in the OpenAccess namespace.
00047 // *****************************************************************************
00048 BEGIN_OA_NAMESPACE
00049 
00050 
00051 
00052 // *****************************************************************************
00053 // Forward Class Declarations
00054 // *****************************************************************************
00055 template <class T>
00056 class oaHashTbl;
00057 template <class T>
00058 class oaHashIter;
00059 
00060 
00061 
00062 // *****************************************************************************
00063 // oaHashTblSlotId<>
00064 // *****************************************************************************
00065 template <class T>
00066 class oaHashTblSlotId {
00067 public:
00068                             oaHashTblSlotId();
00069 
00070     oaBoolean               isValid();
00071 
00072 protected:
00073     oaUInt4                 loc;
00074     friend class oaHashTbl<T>;
00075 };
00076 
00077 
00078 // *****************************************************************************
00079 // oaHashTbl
00080 // *****************************************************************************
00081 template <class T>
00082 class oaHashTbl {
00083 public:
00084     oaUInt4                 getNumEntries() const;
00085 
00086     oaUInt4                 add(T obj);
00087     void                    addAtSlot(T                     obj,
00088                                       oaHashTblSlotId<T>    &slot);
00089     void                    remove(T obj);
00090     void                    removeFromSlot(oaHashTblSlotId<T> &slot);
00091 
00092     virtual oaUInt8         calcVMSize() const;
00093 
00094     void                    genHash(const char  *str,
00095                                     oaUInt4     &start,
00096                                     oaUInt4     &stride) const;
00097     void                    genHash(oaUInt4 value,
00098                                     oaUInt4 &start,
00099                                     oaUInt4 &stride) const;
00100     void                    genHash(oaUInt8 value,
00101                                     oaUInt4 &start,
00102                                     oaUInt4 &stride) const;
00103     void                    genHash(void    *ptr,
00104                                     oaUInt4 &start,
00105                                     oaUInt4 &stride) const;
00106     void                    genHash(oaUInt4  scope,
00107                                     oaUInt4  index,
00108                                     oaUInt4  &start,
00109                                     oaUInt4  &stride) const;
00110 
00111     void                    beginHash(oaUInt4   &start,
00112                                       oaUInt4   &stride) const;
00113     void                    updateHash(const char   *str,
00114                                        oaUInt4      &start,
00115                                        oaUInt4      &stride,
00116                                        oaBoolean    toLower = false) const;
00117     void                    updateHash(const char   c,
00118                                        oaUInt4      &start,
00119                                        oaUInt4      &stride,
00120                                        oaBoolean    toLower = false) const;
00121     void                    updateHash(oaInt4   x,
00122                                        oaUInt4  &start,
00123                                        oaUInt4  &stride) const;
00124     void                    updateHash(oaUInt4  value,
00125                                        oaUInt4  &start,
00126                                        oaUInt4  &stride) const;
00127     void                    endHash(oaUInt4 &start,
00128                                     oaUInt4 &stride) const;
00129 
00130 protected:
00131                             oaHashTbl(oaUInt4 sizeIn = 32);
00132     virtual                 ~oaHashTbl();
00133 
00134     oaUInt4                 find(oaUInt4    loc,
00135                                  oaUInt4    stride,
00136                                  const void *data) const;
00137     oaUInt4                 findSlot(oaUInt4            start,
00138                                      oaUInt4            stride,
00139                                      const void         *data,
00140                                      oaHashTblSlotId<T> &slot);
00141 
00142     virtual void            resize(oaUInt4 newSize);
00143 
00144     virtual void            hash(T          obj,
00145                                  oaUInt4    &start,
00146                                  oaUInt4    &stride) const = 0;
00147     virtual oaBoolean       compare(T           obj,
00148                                     const void  *data) const = 0;
00149 
00150     void                    getLocation(T       obj,
00151                                         oaUInt4 &loc,
00152                                         oaUInt4 &deletedKeyLoc) const;
00153 
00154     void                    getNextLoc(oaUInt4  &loc,
00155                                        oaUInt4  stride,
00156                                        oaUInt4  &start) const;
00157 
00158     oaUInt4                 size;
00159     oaUInt4                 numEntries;
00160     oaUInt4                 numDeleted;
00161     T                       *keys;
00162 
00163     static oaUInt4          hashArray[];
00164 
00165     friend class oaHashIter<T>;
00166 };
00167 
00168 
00169 
00170 #if defined(OA_BASE_DLL_EXTERN)
00171 OA_BASE_DLL_EXTERN template
00172  class OA_BASE_DLL_PVT oaHashTbl<oaUInt4>;
00173 #endif
00174 
00175 
00176 
00177 // *****************************************************************************
00178 // oaHashIter
00179 // *****************************************************************************
00180 template <class T>
00181 class oaHashIter {
00182 public:
00183     void                    reset();
00184 
00185     oaUInt4                 getNext();
00186 
00187 protected:
00188                             oaHashIter(oaHashTbl<T> &tblIn);
00189 
00190     oaHashTbl<T>            &tbl;
00191     oaUInt4                 index;
00192 };
00193 
00194 
00195 
00196 // *****************************************************************************
00197 // Initialize Static Members
00198 // *****************************************************************************
00199 template <class T>
00200 oaUInt4 oaHashTbl<T>::hashArray[] = {
00201     0x7be9c1bd,
00202     0x88aa102,
00203     0x3d38509b,
00204     0x746b9fbe,
00205     0x2d04417f,
00206     0x775d4351,
00207     0x53c48d96,
00208     0x2b26e0b,
00209     0x418fedcf,
00210     0x19dbc19e,
00211     0x78512adb,
00212     0x1a1f5e2b,
00213     0x307d7761,
00214     0x6584c1f0,
00215     0x24e3c36f,
00216     0x2232310f,
00217     0x2dac5ceb,
00218     0x106e8b5a,
00219     0x5a05a938,
00220     0x5e6392b6,
00221     0x66b90348,
00222     0x75264901,
00223     0x4174f402,
00224     0x618b18a4,
00225     0x3a6ab4bf,
00226     0x3c4bc289,
00227     0x2657a9a9,
00228     0x4e68589b,
00229     0x9648aa6,
00230     0x3fc489bb,
00231     0x1c1b715c,
00232     0x54e4c63,
00233     0x484f2abd,
00234     0x5953c1f8,
00235     0x79b9ec22,
00236     0x75536c3d,
00237     0x50b10549,
00238     0x4d7e79b8,
00239     0x7805da48,
00240     0x1240f318,
00241     0x675a3b56,
00242     0x70570523,
00243     0x2c605143,
00244     0x17d7b2b7,
00245     0x55dbc713,
00246     0x514414b2,
00247     0x3a09e3c7,
00248     0x38823ff,
00249     0x61b2a00c,
00250     0x140f8cff,
00251     0x61ebb6b5,
00252     0x486ba354,
00253     0x935d600,
00254     0x2360aab8,
00255     0x29f6bbf8,
00256     0x43a08abf,
00257     0x5fac6d41,
00258     0x504e65a2,
00259     0x1208e35b,
00260     0x6910f7e7,
00261     0x1012ef5d,
00262     0x2e2454b7,
00263     0x6e5f444b,
00264     0x58621a1b,
00265     0x77816af,
00266     0x6819306d,
00267     0x4db58658,
00268     0x58291bf8,
00269     0x3597aa25,
00270     0x45bb60a0,
00271     0x6a6a0f11,
00272     0x1cf1e57c,
00273     0x361265c4,
00274     0x16ca6054,
00275     0x34c99833,
00276     0xbee2cd7,
00277     0x680e7507,
00278     0x6ed37bfa,
00279     0xf7650d6,
00280     0x49c11513,
00281     0x2e308f9,
00282     0x7162078c,
00283     0x122cb868,
00284     0xc18defa,
00285     0x14c2b244,
00286     0x3c237460,
00287     0x4fb969b9,
00288     0x746f1f85,
00289     0xc71da02,
00290     0x61c24d14,
00291     0x5d80176d,
00292     0x1c84c960,
00293     0xfe6a1cc,
00294     0x4bdf5bb8,
00295     0x74e6e37b,
00296     0x175eb87b,
00297     0x33f88c25,
00298     0x429c69d3,
00299     0x6f87d474,
00300     0x6990364a,
00301     0x857ca73,
00302     0x59f1e385,
00303     0x6821bc6,
00304     0x3e6a3037,
00305     0x70bc43d9,
00306     0x3b4bb3fa,
00307     0x4a585d0f,
00308     0x58cab8e0,
00309     0x2a1f2ff4,
00310     0x59ceade5,
00311     0x228bcdf4,
00312     0x2d0238ee,
00313     0x4b30b571,
00314     0x34b8865c,
00315     0x391b17e8,
00316     0x5ff367b5,
00317     0x70dbfabc,
00318     0x8d481a1,
00319     0x5462873b,
00320     0x7d4dd4bf,
00321     0x6a96ceb6,
00322     0x31e29ea8,
00323     0x19d29e1f,
00324     0x7a7d7082,
00325     0x7dc1fa60,
00326     0xeb9819a,
00327     0x11dc28fd,
00328     0x31ba8685,
00329     0x5155eb6d,
00330     0x163fd71,
00331     0x1b4abccf,
00332     0x59adb5e0,
00333     0x5b55e0f6,
00334     0x21ccd896,
00335     0x1817e618,
00336     0x4c1224d0,
00337     0x5d188c90,
00338     0x62704327,
00339     0x24dcddb0,
00340     0x737bc84,
00341     0x3c3ef10c,
00342     0x4768aba4,
00343     0x3439f572,
00344     0x76fa67e,
00345     0x7c213200,
00346     0x6d550d5a,
00347     0x67630e33,
00348     0x6cfd2cbd,
00349     0x76298efc,
00350     0x3bc5956e,
00351     0x6a4b017c,
00352     0x60c05db2,
00353     0x6da83416,
00354     0x41d9f9b,
00355     0x5b3dce34,
00356     0x6b6a2e76,
00357     0x12d72135,
00358     0x6d19f731,
00359     0x1d24b4fb,
00360     0x642d0ca2,
00361     0x6e7df4a3,
00362     0x386f71cb,
00363     0x3ddac282,
00364     0x49d3d599,
00365     0x5a3c4a61,
00366     0x55f2a89a,
00367     0x15e5fa69,
00368     0x3754d6f1,
00369     0x3862ebc1,
00370     0x3ac2d81a,
00371     0x3e8c9375,
00372     0x74a1dcce,
00373     0x22b83be,
00374     0x72c688e8,
00375     0x7c11834c,
00376     0x7e4cb5bf,
00377     0x601b9642,
00378     0x6374917f,
00379     0x6b49e27c,
00380     0x5645253e,
00381     0x1f3a26ee,
00382     0x5594e3f8,
00383     0x370582f0,
00384     0xce25b04,
00385     0x59b28393,
00386     0x12435124,
00387     0x784c897b,
00388     0x6c89a4c8,
00389     0x7f5d4856,
00390     0x15713e76,
00391     0x50b6b16a,
00392     0x6ddb3cf9,
00393     0x4de0b041,
00394     0xe9173ec,
00395     0x37af1292,
00396     0x281cfaa2,
00397     0x64841c87,
00398     0x4d950cfc,
00399     0x5f71d193,
00400     0x1ce70848,
00401     0x857e516,
00402     0x1dfe6509,
00403     0x1188e516,
00404     0xa8368d4,
00405     0x10c4edf1,
00406     0xd9a6862,
00407     0x8d01e93,
00408     0x70e08433,
00409     0x710ef9e2,
00410     0x741a010f,
00411     0x4725a972,
00412     0x104920d0,
00413     0x49aee507,
00414     0x7e2b2c62,
00415     0x1d2b7bd4,
00416     0x2361689a,
00417     0x106e7d87,
00418     0x1578054f,
00419     0xfeb0d62,
00420     0xfcbc5dd,
00421     0x2ae943c6,
00422     0x60a1becc,
00423     0x7da702d6,
00424     0x78c9f407,
00425     0x6f3332b9,
00426     0x35561568,
00427     0x20e6eeaa,
00428     0x53b74f40,
00429     0x2eb2264,
00430     0x58c03d,
00431     0x709e5788,
00432     0xb43077a,
00433     0x1e572546,
00434     0x2273c9f,
00435     0x15c6704f,
00436     0x2f1c1337,
00437     0xfc1a501,
00438     0x1e968ee2,
00439     0x1ffc976b,
00440     0xd09ee3,
00441     0x12b08ff2,
00442     0x672240dd,
00443     0x1119bfb3,
00444     0x5c5f74f9,
00445     0x654d6d3f,
00446     0x2e453b88,
00447     0x7fc0dd94,
00448     0x75bbeac6,
00449     0x43bd40d7,
00450     0xfabeaf6,
00451     0x587b0a3,
00452     0x6ea6849d,
00453     0x704da9c3,
00454     0x32eb379,
00455     0x677078a5,
00456     0x5f80dc7c
00457 };
00458 
00459 
00460 
00461 END_OA_NAMESPACE
00462 
00463 #endif