This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
Teach buildtoc about README.openbsd, and regenerate various makefiles.
[perl5.git] / hv.h
CommitLineData
a0d0e21e 1/* hv.h
79072805 2 *
4bb101f2 3 * Copyright (C) 1991, 1992, 1993, 1996, 1997, 1998, 1999,
1d325971 4 * 2000, 2001, 2002, 2005, by Larry Wall and others
79072805
LW
5 *
6 * You may distribute under the terms of either the GNU General Public
7 * License or the Artistic License, as specified in the README file.
8 *
79072805
LW
9 */
10
5cbe4eec 11/* typedefs to eliminate some typing */
79072805 12typedef struct he HE;
ff68c719 13typedef struct hek HEK;
79072805 14
5cbe4eec 15/* entry in hash value chain */
79072805 16struct he {
5cbe4eec
MF
17 HE *hent_next; /* next entry in chain */
18 HEK *hent_hek; /* hash key */
19 SV *hent_val; /* scalar value that was hashed */
bbce6d69
PP
20};
21
5cbe4eec 22/* hash key -- defined separately for use as shared pointer */
ff68c719 23struct hek {
5cbe4eec
MF
24 U32 hek_hash; /* hash of key */
25 I32 hek_len; /* length of hash key */
26 char hek_key[1]; /* variable-length hash key */
e05949c7 27 /* the hash-key is \0-terminated */
1e54db1a
JH
28 /* after the \0 there is a byte for flags, such as whether the key
29 is UTF-8 */
79072805
LW
30};
31
bfcb3514
NC
32
33/* Subject to change.
34 Don't access this directly.
35*/
36struct xpvhv_aux {
7423f6db 37 HEK *xhv_name; /* name, if a symbol table */
bfcb3514
NC
38 HE *xhv_eiter; /* current entry of iterator */
39 I32 xhv_riter; /* current root of iterator */
40};
41
5cbe4eec 42/* hash structure: */
6ee623d5 43/* This structure must match the beginning of struct xpvmg in sv.h. */
79072805 44struct xpvhv {
102d3b8a 45 IV for_rent;
463ee0b2
LW
46 STRLEN xhv_fill; /* how full xhv_array currently is */
47 STRLEN xhv_max; /* subscript of last element of xhv_array */
e4305a63 48 union {
e4305a63
NC
49 struct {
50 void *xnv_p1;
51 union {
52 void *xnv_p2;
53 IV xnv_i2; /* how many elements in the array */
54 } xnv_u2;
55 } xnv_s;
199f3245 56 NV xnvu_nv; /* numeric value, if any */
e4305a63 57 } xnv_u;
79072805
LW
58 MAGIC* xmg_magic; /* magic for scalar array */
59 HV* xmg_stash; /* class package */
8d2f4536 60 /* list of pm's for this package is now stored in symtab magic. */
79072805
LW
61};
62
e4305a63
NC
63#define xhv_aux xnv_u.xnv_s.xnv_p1
64#define xhv_keys xnv_u.xnv_s.xnv_u2.xnv_i2
65
209b62a3 66#if !defined(PERL_EXPERIMENTAL_LAYOUT)
59813432 67typedef struct xpvhv xpvhv_allocated;
9f1501b2
NC
68#else
69typedef struct {
70 STRLEN xhv_fill; /* how full xhv_array currently is */
71 STRLEN xhv_max; /* subscript of last element of xhv_array */
72 union {
73 NV xnvu_nv; /* numeric value, if any */
74 struct {
75 void *xnv_p1;
76 union {
77 void *xnv_p2;
78 IV xnv_i2; /* how many elements in the array */
79 } xnv_u2;
80 } xnv_s;
81 } xnv_u;
82 MAGIC* xmg_magic; /* magic for scalar array */
83 HV* xmg_stash; /* class package */
84} xpvhv_allocated;
85#endif
e4305a63 86
5cbe4eec 87/* hash a key */
5afd6d42
JH
88/* FYI: This is the "One-at-a-Time" algorithm by Bob Jenkins
89 * from requirements by Colin Plumb.
90 * (http://burtleburtle.net/bob/hash/doobs.html) */
91/* The use of a temporary pointer and the casting games
92 * is needed to serve the dual purposes of
93 * (a) the hashed data being interpreted as "unsigned char" (new since 5.8,
94 * a "char" can be either signed or signed, depending on the compiler)
95 * (b) catering for old code that uses a "char"
830b38bd 96 *
504f80c1
JH
97 * The "hash seed" feature was added in Perl 5.8.1 to perturb the results
98 * to avoid "algorithmic complexity attacks".
830b38bd
JH
99 *
100 * If USE_HASH_SEED is defined, hash randomisation is done by default
101 * If USE_HASH_SEED_EXPLICIT is defined, hash randomisation is done
102 * only if the environment variable PERL_HASH_SEED is set.
103 * For maximal control, one can define PERL_HASH_SEED.
90ce55a1 104 * (see also perl.c:perl_parse()).
5afd6d42 105 */
830b38bd
JH
106#ifndef PERL_HASH_SEED
107# if defined(USE_HASH_SEED) || defined(USE_HASH_SEED_EXPLICIT)
108# define PERL_HASH_SEED PL_hash_seed
109# else
110# define PERL_HASH_SEED 0
111# endif
504f80c1 112#endif
bf6bd887
PP
113#define PERL_HASH(hash,str,len) \
114 STMT_START { \
5afd6d42
JH
115 register const char *s_PeRlHaSh_tmp = str; \
116 register const unsigned char *s_PeRlHaSh = (const unsigned char *)s_PeRlHaSh_tmp; \
bf6bd887 117 register I32 i_PeRlHaSh = len; \
504f80c1 118 register U32 hash_PeRlHaSh = PERL_HASH_SEED; \
a6fe520e
MF
119 while (i_PeRlHaSh--) { \
120 hash_PeRlHaSh += *s_PeRlHaSh++; \
121 hash_PeRlHaSh += (hash_PeRlHaSh << 10); \
122 hash_PeRlHaSh ^= (hash_PeRlHaSh >> 6); \
123 } \
124 hash_PeRlHaSh += (hash_PeRlHaSh << 3); \
125 hash_PeRlHaSh ^= (hash_PeRlHaSh >> 11); \
4fee5c71 126 (hash) = (hash_PeRlHaSh + (hash_PeRlHaSh << 15)); \
bf6bd887
PP
127 } STMT_END
128
3d78eb94
NC
129/* Only hv.c and mod_perl should be doing this. */
130#ifdef PERL_HASH_INTERNAL_ACCESS
4b5190b5
NC
131#define PERL_HASH_INTERNAL(hash,str,len) \
132 STMT_START { \
133 register const char *s_PeRlHaSh_tmp = str; \
134 register const unsigned char *s_PeRlHaSh = (const unsigned char *)s_PeRlHaSh_tmp; \
135 register I32 i_PeRlHaSh = len; \
008fb0c0 136 register U32 hash_PeRlHaSh = PL_rehash_seed; \
4b5190b5
NC
137 while (i_PeRlHaSh--) { \
138 hash_PeRlHaSh += *s_PeRlHaSh++; \
139 hash_PeRlHaSh += (hash_PeRlHaSh << 10); \
140 hash_PeRlHaSh ^= (hash_PeRlHaSh >> 6); \
141 } \
142 hash_PeRlHaSh += (hash_PeRlHaSh << 3); \
143 hash_PeRlHaSh ^= (hash_PeRlHaSh >> 11); \
144 (hash) = (hash_PeRlHaSh + (hash_PeRlHaSh << 15)); \
145 } STMT_END
146#endif
147
954c1994 148/*
ccfc67b7
JH
149=head1 Hash Manipulation Functions
150
954c1994
GS
151=for apidoc AmU||HEf_SVKEY
152This flag, used in the length slot of hash entries and magic structures,
d1be9408 153specifies the structure contains an C<SV*> pointer where a C<char*> pointer
954c1994
GS
154is to be expected. (For information only--not to be used).
155
ccfc67b7
JH
156=head1 Handy Values
157
954c1994
GS
158=for apidoc AmU||Nullhv
159Null HV pointer.
160
ccfc67b7
JH
161=head1 Hash Manipulation Functions
162
954c1994
GS
163=for apidoc Am|char*|HvNAME|HV* stash
164Returns the package name of a stash. See C<SvSTASH>, C<CvSTASH>.
165
166=for apidoc Am|void*|HeKEY|HE* he
167Returns the actual pointer stored in the key slot of the hash entry. The
168pointer may be either C<char*> or C<SV*>, depending on the value of
169C<HeKLEN()>. Can be assigned to. The C<HePV()> or C<HeSVKEY()> macros are
170usually preferable for finding the value of a key.
171
172=for apidoc Am|STRLEN|HeKLEN|HE* he
173If this is negative, and amounts to C<HEf_SVKEY>, it indicates the entry
174holds an C<SV*> key. Otherwise, holds the actual length of the key. Can
175be assigned to. The C<HePV()> macro is usually preferable for finding key
176lengths.
177
178=for apidoc Am|SV*|HeVAL|HE* he
179Returns the value slot (type C<SV*>) stored in the hash entry.
180
181=for apidoc Am|U32|HeHASH|HE* he
182Returns the computed hash stored in the hash entry.
183
184=for apidoc Am|char*|HePV|HE* he|STRLEN len
185Returns the key slot of the hash entry as a C<char*> value, doing any
186necessary dereferencing of possibly C<SV*> keys. The length of the string
187is placed in C<len> (this is a macro, so do I<not> use C<&len>). If you do
188not care about what the length of the key is, you may use the global
189variable C<PL_na>, though this is rather less efficient than using a local
190variable. Remember though, that hash keys in perl are free to contain
191embedded nulls, so using C<strlen()> or similar is not a good way to find
192the length of hash keys. This is very similar to the C<SvPV()> macro
193described elsewhere in this document.
194
195=for apidoc Am|SV*|HeSVKEY|HE* he
196Returns the key as an C<SV*>, or C<Nullsv> if the hash entry does not
197contain an C<SV*> key.
198
199=for apidoc Am|SV*|HeSVKEY_force|HE* he
200Returns the key as an C<SV*>. Will create and return a temporary mortal
201C<SV*> if the hash entry contains only a C<char*> key.
202
203=for apidoc Am|SV*|HeSVKEY_set|HE* he|SV* sv
204Sets the key to a given C<SV*>, taking care to set the appropriate flags to
205indicate the presence of an C<SV*> key, and returns the same
206C<SV*>.
207
208=cut
209*/
bf6bd887 210
bf5b86ae 211/* these hash entry flags ride on hent_klen (for use only in magic/tied HVs) */
d1be9408 212#define HEf_SVKEY -2 /* hent_key is an SV* */
bf6bd887
PP
213
214
79072805 215#define Nullhv Null(HV*)
339049b0 216#define HvARRAY(hv) (*(HE***)&((hv)->sv_u.svu_array))
79072805 217#define HvFILL(hv) ((XPVHV*) SvANY(hv))->xhv_fill
463ee0b2 218#define HvMAX(hv) ((XPVHV*) SvANY(hv))->xhv_max
bfcb3514
NC
219#define HvRITER(hv) (*Perl_hv_riter_p(aTHX_ (HV*)(hv)))
220#define HvEITER(hv) (*Perl_hv_eiter_p(aTHX_ (HV*)(hv)))
221#define HvRITER_set(hv,r) Perl_hv_riter_set(aTHX_ (HV*)(hv), r)
222#define HvEITER_set(hv,e) Perl_hv_eiter_set(aTHX_ (HV*)(hv), e)
223#define HvRITER_get(hv) (((XPVHV *)SvANY(hv))->xhv_aux ? \
224 ((struct xpvhv_aux*)((XPVHV *)SvANY(hv))->xhv_aux)->xhv_riter : -1)
225#define HvEITER_get(hv) (((XPVHV *)SvANY(hv))->xhv_aux ? \
226 ((struct xpvhv_aux *)((XPVHV *)SvANY(hv))->xhv_aux)->xhv_eiter : 0)
7423f6db 227#define HvNAME(hv) HvNAME_get(hv)
bfcb3514
NC
228/* FIXME - all of these should use a UTF8 aware API, which should also involve
229 getting the length. */
9b9d0b15
NC
230/* This macro may go away without notice. */
231#define HvNAME_HEK(hv) (((XPVHV *)SvANY(hv))->xhv_aux && (((struct xpvhv_aux *)((XPVHV *)SvANY(hv))->xhv_aux)->xhv_name) ? ((struct xpvhv_aux *)((XPVHV *)SvANY(hv))->xhv_aux)->xhv_name: 0)
bfcb3514 232#define HvNAME_get(hv) (((XPVHV *)SvANY(hv))->xhv_aux ? \
7423f6db
NC
233 (((struct xpvhv_aux *)((XPVHV *)SvANY(hv))->xhv_aux)->xhv_name) ? HEK_KEY(((struct xpvhv_aux *)((XPVHV *)SvANY(hv))->xhv_aux)->xhv_name) : 0 : 0)
234#define HvNAMELEN_get(hv) (((XPVHV *)SvANY(hv))->xhv_aux ? \
235 (((struct xpvhv_aux *)((XPVHV *)SvANY(hv))->xhv_aux)->xhv_name) ? HEK_LEN(((struct xpvhv_aux *)((XPVHV *)SvANY(hv))->xhv_aux)->xhv_name) : 0 : 0)
a0d0e21e 236
8aacddc1
NIS
237/* the number of keys (including any placeholers) */
238#define XHvTOTALKEYS(xhv) ((xhv)->xhv_keys)
239
8aacddc1
NIS
240/*
241 * HvKEYS gets the number of keys that actually exist(), and is provided
242 * for backwards compatibility with old XS code. The core uses HvUSEDKEYS
243 * (keys, excluding placeholdes) and HvTOTALKEYS (including placeholders)
244 */
ca732855
NC
245#define HvKEYS(hv) HvUSEDKEYS(hv)
246#define HvUSEDKEYS(hv) (HvTOTALKEYS(hv) - HvPLACEHOLDERS_get(hv))
8aacddc1 247#define HvTOTALKEYS(hv) XHvTOTALKEYS((XPVHV*) SvANY(hv))
ca732855
NC
248#define HvPLACEHOLDERS(hv) (*Perl_hv_placeholders_p(aTHX_ (HV*)hv))
249#define HvPLACEHOLDERS_get(hv) (SvMAGIC(hv) ? Perl_hv_placeholders_get(aTHX_ (HV*)hv) : 0)
250#define HvPLACEHOLDERS_set(hv,p) Perl_hv_placeholders_set(aTHX_ (HV*)hv, p)
8aacddc1 251
bf6bd887
PP
252#define HvSHAREKEYS(hv) (SvFLAGS(hv) & SVphv_SHAREKEYS)
253#define HvSHAREKEYS_on(hv) (SvFLAGS(hv) |= SVphv_SHAREKEYS)
254#define HvSHAREKEYS_off(hv) (SvFLAGS(hv) &= ~SVphv_SHAREKEYS)
255
19692e8d
NC
256/* This is an optimisation flag. It won't be set if all hash keys have a 0
257 * flag. Currently the only flags relate to utf8.
258 * Hence it won't be set if all keys are 8 bit only. It will be set if any key
259 * is utf8 (including 8 bit keys that were entered as utf8, and need upgrading
260 * when retrieved during iteration. It may still be set when there are no longer
261 * any utf8 keys.
fdcd69b6 262 * See HVhek_ENABLEHVKFLAGS for the trigger.
19692e8d
NC
263 */
264#define HvHASKFLAGS(hv) (SvFLAGS(hv) & SVphv_HASKFLAGS)
265#define HvHASKFLAGS_on(hv) (SvFLAGS(hv) |= SVphv_HASKFLAGS)
266#define HvHASKFLAGS_off(hv) (SvFLAGS(hv) &= ~SVphv_HASKFLAGS)
574c8022 267
bf5b86ae
GS
268#define HvLAZYDEL(hv) (SvFLAGS(hv) & SVphv_LAZYDEL)
269#define HvLAZYDEL_on(hv) (SvFLAGS(hv) |= SVphv_LAZYDEL)
270#define HvLAZYDEL_off(hv) (SvFLAGS(hv) &= ~SVphv_LAZYDEL)
271
4b5190b5
NC
272#define HvREHASH(hv) (SvFLAGS(hv) & SVphv_REHASH)
273#define HvREHASH_on(hv) (SvFLAGS(hv) |= SVphv_REHASH)
274#define HvREHASH_off(hv) (SvFLAGS(hv) &= ~SVphv_REHASH)
275
a0d0e21e
LW
276/* Maybe amagical: */
277/* #define HV_AMAGICmb(hv) (SvFLAGS(hv) & (SVpgv_badAM | SVpgv_AM)) */
278
279#define HV_AMAGIC(hv) (SvFLAGS(hv) & SVpgv_AM)
280#define HV_AMAGIC_on(hv) (SvFLAGS(hv) |= SVpgv_AM)
281#define HV_AMAGIC_off(hv) (SvFLAGS(hv) &= ~SVpgv_AM)
282
283/*
284#define HV_AMAGICbad(hv) (SvFLAGS(hv) & SVpgv_badAM)
285#define HV_badAMAGIC_on(hv) (SvFLAGS(hv) |= SVpgv_badAM)
286#define HV_badAMAGIC_off(hv) (SvFLAGS(hv) &= ~SVpgv_badAM)
287*/
bf6bd887
PP
288
289#define Nullhe Null(HE*)
290#define HeNEXT(he) (he)->hent_next
ff68c719
PP
291#define HeKEY_hek(he) (he)->hent_hek
292#define HeKEY(he) HEK_KEY(HeKEY_hek(he))
bbce6d69 293#define HeKEY_sv(he) (*(SV**)HeKEY(he))
ff68c719 294#define HeKLEN(he) HEK_LEN(HeKEY_hek(he))
da58a35d 295#define HeKUTF8(he) HEK_UTF8(HeKEY_hek(he))
19692e8d 296#define HeKWASUTF8(he) HEK_WASUTF8(HeKEY_hek(he))
4b5190b5 297#define HeKREHASH(he) HEK_REHASH(HeKEY_hek(he))
da58a35d 298#define HeKLEN_UTF8(he) (HeKUTF8(he) ? -HeKLEN(he) : HeKLEN(he))
19692e8d 299#define HeKFLAGS(he) HEK_FLAGS(HeKEY_hek(he))
bf6bd887 300#define HeVAL(he) (he)->hent_val
ff68c719 301#define HeHASH(he) HEK_HASH(HeKEY_hek(he))
1e422769
PP
302#define HePV(he,lp) ((HeKLEN(he) == HEf_SVKEY) ? \
303 SvPV(HeKEY_sv(he),lp) : \
304 (((lp = HeKLEN(he)) >= 0) ? \
305 HeKEY(he) : Nullch))
306
bbce6d69
PP
307#define HeSVKEY(he) ((HeKEY(he) && \
308 HeKLEN(he) == HEf_SVKEY) ? \
309 HeKEY_sv(he) : Nullsv)
310
311#define HeSVKEY_force(he) (HeKEY(he) ? \
312 ((HeKLEN(he) == HEf_SVKEY) ? \
313 HeKEY_sv(he) : \
79cb57f6 314 sv_2mortal(newSVpvn(HeKEY(he), \
bbce6d69 315 HeKLEN(he)))) : \
3280af22 316 &PL_sv_undef)
1e422769 317#define HeSVKEY_set(he,sv) ((HeKLEN(he) = HEf_SVKEY), (HeKEY_sv(he) = sv))
bbce6d69 318
ff68c719 319#define Nullhek Null(HEK*)
71be2cbc 320#define HEK_BASESIZE STRUCT_OFFSET(HEK, hek_key[0])
ff68c719
PP
321#define HEK_HASH(hek) (hek)->hek_hash
322#define HEK_LEN(hek) (hek)->hek_len
323#define HEK_KEY(hek) (hek)->hek_key
19692e8d
NC
324#define HEK_FLAGS(hek) (*((unsigned char *)(HEK_KEY(hek))+HEK_LEN(hek)+1))
325
326#define HVhek_UTF8 0x01 /* Key is utf8 encoded. */
327#define HVhek_WASUTF8 0x02 /* Key is bytes here, but was supplied as utf8. */
4b5190b5 328#define HVhek_REHASH 0x04 /* This key is in an hv using a custom HASH . */
19692e8d 329#define HVhek_FREEKEY 0x100 /* Internal flag to say key is malloc()ed. */
e16e2ff8
NC
330#define HVhek_PLACEHOLD 0x200 /* Internal flag to create placeholder.
331 * (may change, but Storable is a core module) */
19692e8d
NC
332#define HVhek_MASK 0xFF
333
fdcd69b6
NC
334/* Which flags enable HvHASKFLAGS? Somewhat a hack on a hack, as
335 HVhek_REHASH is only needed because the rehash flag has to be duplicated
336 into all keys as hv_iternext has no access to the hash flags. At this
337 point Storable's tests get upset, because sometimes hashes are "keyed"
338 and sometimes not, depending on the order of data insertion, and whether
339 it triggered rehashing. So currently HVhek_REHAS is exempt.
340*/
341
342#define HVhek_ENABLEHVKFLAGS (HVhek_MASK - HVhek_REHASH)
343
19692e8d
NC
344#define HEK_UTF8(hek) (HEK_FLAGS(hek) & HVhek_UTF8)
345#define HEK_UTF8_on(hek) (HEK_FLAGS(hek) |= HVhek_UTF8)
346#define HEK_UTF8_off(hek) (HEK_FLAGS(hek) &= ~HVhek_UTF8)
347#define HEK_WASUTF8(hek) (HEK_FLAGS(hek) & HVhek_WASUTF8)
348#define HEK_WASUTF8_on(hek) (HEK_FLAGS(hek) |= HVhek_WASUTF8)
349#define HEK_WASUTF8_off(hek) (HEK_FLAGS(hek) &= ~HVhek_WASUTF8)
4b5190b5
NC
350#define HEK_REHASH(hek) (HEK_FLAGS(hek) & HVhek_REHASH)
351#define HEK_REHASH_on(hek) (HEK_FLAGS(hek) |= HVhek_REHASH)
d18c6117 352
5cbe4eec 353/* calculate HV array allocation */
36768cf4
NC
354#ifndef PERL_USE_LARGE_HV_ALLOC
355/* Default to allocating the correct size - default to assuming that malloc()
356 is not broken and is efficient at allocating blocks sized at powers-of-two.
357*/
d18c6117
GS
358# define PERL_HV_ARRAY_ALLOC_BYTES(size) ((size) * sizeof(HE*))
359#else
360# define MALLOC_OVERHEAD 16
361# define PERL_HV_ARRAY_ALLOC_BYTES(size) \
362 (((size) < 64) \
363 ? (size) * sizeof(HE*) \
364 : (size) * sizeof(HE*) * 2 - MALLOC_OVERHEAD)
365#endif
37d85e3a 366
e16e2ff8
NC
367/* Flags for hv_iternext_flags. */
368#define HV_ITERNEXT_WANTPLACEHOLDERS 0x01 /* Don't skip placeholders. */
369
37d85e3a
JH
370/* available as a function in hv.c */
371#define Perl_sharepvn(sv, len, hash) HEK_KEY(share_hek(sv, len, hash))
372#define sharepvn(sv, len, hash) Perl_sharepvn(sv, len, hash)
bfcb3514
NC
373
374/*
375 * Local variables:
376 * c-indentation-style: bsd
377 * c-basic-offset: 4
378 * indent-tabs-mode: t
379 * End:
380 *
381 * ex: set ts=8 sts=4 sw=4 noet:
382 */