home *** CD-ROM | disk | FTP | other *** search
/ PC Professionell 2006 December / PCpro_2006_12.ISO / ossdvd / server / Perl2 / lib / core / hv.h < prev    next >
Encoding:
C/C++ Source or Header  |  2002-06-19  |  10.4 KB  |  269 lines
  1. /*    hv.h
  2.  *
  3.  *    Copyright (c) 1991-2002, Larry Wall
  4.  *
  5.  *    You may distribute under the terms of either the GNU General Public
  6.  *    License or the Artistic License, as specified in the README file.
  7.  *
  8.  */
  9.  
  10. /* typedefs to eliminate some typing */
  11. typedef struct he HE;
  12. typedef struct hek HEK;
  13.  
  14. /* entry in hash value chain */
  15. struct he {
  16.     HE        *hent_next;    /* next entry in chain */
  17.     HEK        *hent_hek;    /* hash key */
  18.     SV        *hent_val;    /* scalar value that was hashed */
  19. };
  20.  
  21. /* hash key -- defined separately for use as shared pointer */
  22. struct hek {
  23.     U32        hek_hash;    /* hash of key */
  24.     I32        hek_len;    /* length of hash key */
  25.     char    hek_key[1];    /* variable-length hash key */
  26.     /* the hash-key is \0-terminated */
  27.     /* after the \0 there is a byte for flags, such as whether the key is
  28.        UTF8 */
  29. };
  30.  
  31. /* hash structure: */
  32. /* This structure must match the beginning of struct xpvmg in sv.h. */
  33. struct xpvhv {
  34.     char *    xhv_array;    /* pointer to malloced string */
  35.     STRLEN    xhv_fill;    /* how full xhv_array currently is */
  36.     STRLEN    xhv_max;    /* subscript of last element of xhv_array */
  37.     IV        xhv_keys;    /* how many elements in the array */
  38.     NV        xnv_nv;        /* numeric value, if any */
  39. #define xhv_placeholders xnv_nv
  40.     MAGIC*    xmg_magic;    /* magic for scalar array */
  41.     HV*        xmg_stash;    /* class package */
  42.  
  43.     I32        xhv_riter;    /* current root of iterator */
  44.     HE        *xhv_eiter;    /* current entry of iterator */
  45.     PMOP    *xhv_pmroot;    /* list of pm's for this package */
  46.     char    *xhv_name;    /* name, if a symbol table */
  47. };
  48.  
  49. /* hash a key */
  50. /* FYI: This is the "One-at-a-Time" algorithm by Bob Jenkins
  51.  * from requirements by Colin Plumb.
  52.  * (http://burtleburtle.net/bob/hash/doobs.html) */
  53. /* The use of a temporary pointer and the casting games
  54.  * is needed to serve the dual purposes of
  55.  * (a) the hashed data being interpreted as "unsigned char" (new since 5.8,
  56.  *     a "char" can be either signed or signed, depending on the compiler)
  57.  * (b) catering for old code that uses a "char"
  58.  */
  59. #define PERL_HASH(hash,str,len) \
  60.      STMT_START    { \
  61.     register const char *s_PeRlHaSh_tmp = str; \
  62.     register const unsigned char *s_PeRlHaSh = (const unsigned char *)s_PeRlHaSh_tmp; \
  63.     register I32 i_PeRlHaSh = len; \
  64.     register U32 hash_PeRlHaSh = 0; \
  65.     while (i_PeRlHaSh--) { \
  66.         hash_PeRlHaSh += *s_PeRlHaSh++; \
  67.         hash_PeRlHaSh += (hash_PeRlHaSh << 10); \
  68.         hash_PeRlHaSh ^= (hash_PeRlHaSh >> 6); \
  69.     } \
  70.     hash_PeRlHaSh += (hash_PeRlHaSh << 3); \
  71.     hash_PeRlHaSh ^= (hash_PeRlHaSh >> 11); \
  72.     (hash) = (hash_PeRlHaSh + (hash_PeRlHaSh << 15)); \
  73.     } STMT_END
  74.  
  75. /*
  76. =head1 Hash Manipulation Functions
  77.  
  78. =for apidoc AmU||HEf_SVKEY
  79. This flag, used in the length slot of hash entries and magic structures,
  80. specifies the structure contains an C<SV*> pointer where a C<char*> pointer
  81. is to be expected. (For information only--not to be used).
  82.  
  83. =head1 Handy Values
  84.  
  85. =for apidoc AmU||Nullhv
  86. Null HV pointer.
  87.  
  88. =head1 Hash Manipulation Functions
  89.  
  90. =for apidoc Am|char*|HvNAME|HV* stash
  91. Returns the package name of a stash.  See C<SvSTASH>, C<CvSTASH>.
  92.  
  93. =for apidoc Am|void*|HeKEY|HE* he
  94. Returns the actual pointer stored in the key slot of the hash entry. The
  95. pointer may be either C<char*> or C<SV*>, depending on the value of
  96. C<HeKLEN()>.  Can be assigned to.  The C<HePV()> or C<HeSVKEY()> macros are
  97. usually preferable for finding the value of a key.
  98.  
  99. =for apidoc Am|STRLEN|HeKLEN|HE* he
  100. If this is negative, and amounts to C<HEf_SVKEY>, it indicates the entry
  101. holds an C<SV*> key.  Otherwise, holds the actual length of the key.  Can
  102. be assigned to. The C<HePV()> macro is usually preferable for finding key
  103. lengths.
  104.  
  105. =for apidoc Am|SV*|HeVAL|HE* he
  106. Returns the value slot (type C<SV*>) stored in the hash entry.
  107.  
  108. =for apidoc Am|U32|HeHASH|HE* he
  109. Returns the computed hash stored in the hash entry.
  110.  
  111. =for apidoc Am|char*|HePV|HE* he|STRLEN len
  112. Returns the key slot of the hash entry as a C<char*> value, doing any
  113. necessary dereferencing of possibly C<SV*> keys.  The length of the string
  114. is placed in C<len> (this is a macro, so do I<not> use C<&len>).  If you do
  115. not care about what the length of the key is, you may use the global
  116. variable C<PL_na>, though this is rather less efficient than using a local
  117. variable.  Remember though, that hash keys in perl are free to contain
  118. embedded nulls, so using C<strlen()> or similar is not a good way to find
  119. the length of hash keys. This is very similar to the C<SvPV()> macro
  120. described elsewhere in this document.
  121.  
  122. =for apidoc Am|SV*|HeSVKEY|HE* he
  123. Returns the key as an C<SV*>, or C<Nullsv> if the hash entry does not
  124. contain an C<SV*> key.
  125.  
  126. =for apidoc Am|SV*|HeSVKEY_force|HE* he
  127. Returns the key as an C<SV*>.  Will create and return a temporary mortal
  128. C<SV*> if the hash entry contains only a C<char*> key.
  129.  
  130. =for apidoc Am|SV*|HeSVKEY_set|HE* he|SV* sv
  131. Sets the key to a given C<SV*>, taking care to set the appropriate flags to
  132. indicate the presence of an C<SV*> key, and returns the same
  133. C<SV*>.
  134.  
  135. =cut
  136. */
  137.  
  138. /* these hash entry flags ride on hent_klen (for use only in magic/tied HVs) */
  139. #define HEf_SVKEY    -2    /* hent_key is an SV* */
  140.  
  141.  
  142. #define Nullhv Null(HV*)
  143. #define HvARRAY(hv)    (*(HE***)&((XPVHV*)  SvANY(hv))->xhv_array)
  144. #define HvFILL(hv)    ((XPVHV*)  SvANY(hv))->xhv_fill
  145. #define HvMAX(hv)    ((XPVHV*)  SvANY(hv))->xhv_max
  146. #define HvRITER(hv)    ((XPVHV*)  SvANY(hv))->xhv_riter
  147. #define HvEITER(hv)    ((XPVHV*)  SvANY(hv))->xhv_eiter
  148. #define HvPMROOT(hv)    ((XPVHV*)  SvANY(hv))->xhv_pmroot
  149. #define HvNAME(hv)    ((XPVHV*)  SvANY(hv))->xhv_name
  150.  
  151. /* the number of keys (including any placeholers) */
  152. #define XHvTOTALKEYS(xhv)    ((xhv)->xhv_keys)
  153.  
  154. /* The number of placeholders in the enumerated-keys hash */
  155. #define XHvPLACEHOLDERS(xhv)    ((xhv)->xhv_placeholders)
  156.  
  157. /* the number of keys that exist() (i.e. excluding placeholders) */
  158. #define XHvUSEDKEYS(xhv)      (XHvTOTALKEYS(xhv) - (IV)XHvPLACEHOLDERS(xhv))
  159.  
  160. /*
  161.  * HvKEYS gets the number of keys that actually exist(), and is provided
  162.  * for backwards compatibility with old XS code. The core uses HvUSEDKEYS
  163.  * (keys, excluding placeholdes) and HvTOTALKEYS (including placeholders)
  164.  */
  165. #define HvKEYS(hv)        XHvUSEDKEYS((XPVHV*)  SvANY(hv))
  166. #define HvUSEDKEYS(hv)        XHvUSEDKEYS((XPVHV*)  SvANY(hv))
  167. #define HvTOTALKEYS(hv)        XHvTOTALKEYS((XPVHV*)  SvANY(hv))
  168. #define HvPLACEHOLDERS(hv)    XHvPLACEHOLDERS((XPVHV*)  SvANY(hv))
  169.  
  170. #define HvSHAREKEYS(hv)        (SvFLAGS(hv) & SVphv_SHAREKEYS)
  171. #define HvSHAREKEYS_on(hv)    (SvFLAGS(hv) |= SVphv_SHAREKEYS)
  172. #define HvSHAREKEYS_off(hv)    (SvFLAGS(hv) &= ~SVphv_SHAREKEYS)
  173.  
  174. /* This is an optimisation flag. It won't be set if all hash keys have a 0
  175.  * flag. Currently the only flags relate to utf8.
  176.  * Hence it won't be set if all keys are 8 bit only. It will be set if any key
  177.  * is utf8 (including 8 bit keys that were entered as utf8, and need upgrading
  178.  * when retrieved during iteration. It may still be set when there are no longer
  179.  * any utf8 keys.
  180.  */
  181. #define HvHASKFLAGS(hv)        (SvFLAGS(hv) & SVphv_HASKFLAGS)
  182. #define HvHASKFLAGS_on(hv)    (SvFLAGS(hv) |= SVphv_HASKFLAGS)
  183. #define HvHASKFLAGS_off(hv)    (SvFLAGS(hv) &= ~SVphv_HASKFLAGS)
  184.  
  185. #define HvLAZYDEL(hv)        (SvFLAGS(hv) & SVphv_LAZYDEL)
  186. #define HvLAZYDEL_on(hv)    (SvFLAGS(hv) |= SVphv_LAZYDEL)
  187. #define HvLAZYDEL_off(hv)    (SvFLAGS(hv) &= ~SVphv_LAZYDEL)
  188.  
  189. /* Maybe amagical: */
  190. /* #define HV_AMAGICmb(hv)      (SvFLAGS(hv) & (SVpgv_badAM | SVpgv_AM)) */
  191.  
  192. #define HV_AMAGIC(hv)        (SvFLAGS(hv) &   SVpgv_AM)
  193. #define HV_AMAGIC_on(hv)     (SvFLAGS(hv) |=  SVpgv_AM)
  194. #define HV_AMAGIC_off(hv)    (SvFLAGS(hv) &= ~SVpgv_AM)
  195.  
  196. /*
  197. #define HV_AMAGICbad(hv)     (SvFLAGS(hv) & SVpgv_badAM)
  198. #define HV_badAMAGIC_on(hv)  (SvFLAGS(hv) |= SVpgv_badAM)
  199. #define HV_badAMAGIC_off(hv) (SvFLAGS(hv) &= ~SVpgv_badAM)
  200. */
  201.  
  202. #define Nullhe Null(HE*)
  203. #define HeNEXT(he)        (he)->hent_next
  204. #define HeKEY_hek(he)        (he)->hent_hek
  205. #define HeKEY(he)        HEK_KEY(HeKEY_hek(he))
  206. #define HeKEY_sv(he)        (*(SV**)HeKEY(he))
  207. #define HeKLEN(he)        HEK_LEN(HeKEY_hek(he))
  208. #define HeKUTF8(he)  HEK_UTF8(HeKEY_hek(he))
  209. #define HeKWASUTF8(he)  HEK_WASUTF8(HeKEY_hek(he))
  210. #define HeKLEN_UTF8(he)  (HeKUTF8(he) ? -HeKLEN(he) : HeKLEN(he))
  211. #define HeKFLAGS(he)  HEK_FLAGS(HeKEY_hek(he))
  212. #define HeVAL(he)        (he)->hent_val
  213. #define HeHASH(he)        HEK_HASH(HeKEY_hek(he))
  214. #define HePV(he,lp)        ((HeKLEN(he) == HEf_SVKEY) ?        \
  215.                  SvPV(HeKEY_sv(he),lp) :        \
  216.                  (((lp = HeKLEN(he)) >= 0) ?        \
  217.                   HeKEY(he) : Nullch))
  218.  
  219. #define HeSVKEY(he)        ((HeKEY(he) &&                 \
  220.                   HeKLEN(he) == HEf_SVKEY) ?        \
  221.                  HeKEY_sv(he) : Nullsv)
  222.  
  223. #define HeSVKEY_force(he)    (HeKEY(he) ?                \
  224.                  ((HeKLEN(he) == HEf_SVKEY) ?        \
  225.                   HeKEY_sv(he) :            \
  226.                   sv_2mortal(newSVpvn(HeKEY(he),    \
  227.                              HeKLEN(he)))) :    \
  228.                  &PL_sv_undef)
  229. #define HeSVKEY_set(he,sv)    ((HeKLEN(he) = HEf_SVKEY), (HeKEY_sv(he) = sv))
  230.  
  231. #define Nullhek Null(HEK*)
  232. #define HEK_BASESIZE        STRUCT_OFFSET(HEK, hek_key[0])
  233. #define HEK_HASH(hek)        (hek)->hek_hash
  234. #define HEK_LEN(hek)        (hek)->hek_len
  235. #define HEK_KEY(hek)        (hek)->hek_key
  236. #define HEK_FLAGS(hek)    (*((unsigned char *)(HEK_KEY(hek))+HEK_LEN(hek)+1))
  237.  
  238. #define HVhek_UTF8    0x01 /* Key is utf8 encoded. */
  239. #define HVhek_WASUTF8    0x02 /* Key is bytes here, but was supplied as utf8. */
  240. #define HVhek_FREEKEY    0x100 /* Internal flag to say key is malloc()ed.  */
  241. #define HVhek_PLACEHOLD    0x200 /* Internal flag to create placeholder.
  242.                                * (may change, but Storable is a core module) */
  243. #define HVhek_MASK    0xFF
  244.  
  245. #define HEK_UTF8(hek)        (HEK_FLAGS(hek) & HVhek_UTF8)
  246. #define HEK_UTF8_on(hek)    (HEK_FLAGS(hek) |= HVhek_UTF8)
  247. #define HEK_UTF8_off(hek)    (HEK_FLAGS(hek) &= ~HVhek_UTF8)
  248. #define HEK_WASUTF8(hek)    (HEK_FLAGS(hek) & HVhek_WASUTF8)
  249. #define HEK_WASUTF8_on(hek)    (HEK_FLAGS(hek) |= HVhek_WASUTF8)
  250. #define HEK_WASUTF8_off(hek)    (HEK_FLAGS(hek) &= ~HVhek_WASUTF8)
  251.  
  252. /* calculate HV array allocation */
  253. #if defined(STRANGE_MALLOC) || defined(MYMALLOC)
  254. #  define PERL_HV_ARRAY_ALLOC_BYTES(size) ((size) * sizeof(HE*))
  255. #else
  256. #  define MALLOC_OVERHEAD 16
  257. #  define PERL_HV_ARRAY_ALLOC_BYTES(size) \
  258.             (((size) < 64)                    \
  259.              ? (size) * sizeof(HE*)                \
  260.              : (size) * sizeof(HE*) * 2 - MALLOC_OVERHEAD)
  261. #endif
  262.  
  263. /* Flags for hv_iternext_flags.  */
  264. #define HV_ITERNEXT_WANTPLACEHOLDERS    0x01    /* Don't skip placeholders.  */
  265.  
  266. /* available as a function in hv.c */
  267. #define Perl_sharepvn(sv, len, hash) HEK_KEY(share_hek(sv, len, hash))
  268. #define sharepvn(sv, len, hash)         Perl_sharepvn(sv, len, hash)
  269.