]>
git.proxmox.com Git - ceph.git/blob - ceph/src/civetweb/src/third_party/lua-5.3.1/src/lstring.c
2 ** $Id: lstring.c,v 2.49 2015/06/01 16:34:37 roberto Exp $
3 ** String table (keeps all strings handled by Lua)
4 ** See Copyright Notice in lua.h
25 #define MEMERRMSG "not enough memory"
29 ** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to
32 #if !defined(LUAI_HASHLIMIT)
33 #define LUAI_HASHLIMIT 5
38 ** equality for long strings
40 int luaS_eqlngstr (TString
*a
, TString
*b
) {
41 size_t len
= a
->u
.lnglen
;
42 lua_assert(a
->tt
== LUA_TLNGSTR
&& b
->tt
== LUA_TLNGSTR
);
43 return (a
== b
) || /* same instance or... */
44 ((len
== b
->u
.lnglen
) && /* equal length and ... */
45 (memcmp(getstr(a
), getstr(b
), len
) == 0)); /* equal contents */
49 unsigned int luaS_hash (const char *str
, size_t l
, unsigned int seed
) {
50 unsigned int h
= seed
^ cast(unsigned int, l
);
52 size_t step
= (l
>> LUAI_HASHLIMIT
) + 1;
53 for (l1
= l
; l1
>= step
; l1
-= step
)
54 h
= h
^ ((h
<<5) + (h
>>2) + cast_byte(str
[l1
- 1]));
60 ** resizes the string table
62 void luaS_resize (lua_State
*L
, int newsize
) {
64 stringtable
*tb
= &G(L
)->strt
;
65 if (newsize
> tb
->size
) { /* grow table if needed */
66 luaM_reallocvector(L
, tb
->hash
, tb
->size
, newsize
, TString
*);
67 for (i
= tb
->size
; i
< newsize
; i
++)
70 for (i
= 0; i
< tb
->size
; i
++) { /* rehash */
71 TString
*p
= tb
->hash
[i
];
73 while (p
) { /* for each node in the list */
74 TString
*hnext
= p
->u
.hnext
; /* save next */
75 unsigned int h
= lmod(p
->hash
, newsize
); /* new position */
76 p
->u
.hnext
= tb
->hash
[h
]; /* chain it */
81 if (newsize
< tb
->size
) { /* shrink table if needed */
82 /* vanishing slice should be empty */
83 lua_assert(tb
->hash
[newsize
] == NULL
&& tb
->hash
[tb
->size
- 1] == NULL
);
84 luaM_reallocvector(L
, tb
->hash
, tb
->size
, newsize
, TString
*);
91 ** Clear API string cache. (Entries cannot be empty, so fill them with
92 ** a non-collectable string.)
94 void luaS_clearcache (global_State
*g
) {
96 for (i
= 0; i
< STRCACHE_SIZE
; i
++) {
97 if (iswhite(g
->strcache
[i
][0])) /* will entry be collected? */
98 g
->strcache
[i
][0] = g
->memerrmsg
; /* replace it with something fixed */
104 ** Initialize the string table and the string cache
106 void luaS_init (lua_State
*L
) {
107 global_State
*g
= G(L
);
109 luaS_resize(L
, MINSTRTABSIZE
); /* initial size of string table */
110 /* pre-create memory-error message */
111 g
->memerrmsg
= luaS_newliteral(L
, MEMERRMSG
);
112 luaC_fix(L
, obj2gco(g
->memerrmsg
)); /* it should never be collected */
113 for (i
= 0; i
< STRCACHE_SIZE
; i
++) /* fill cache with valid strings */
114 g
->strcache
[i
][0] = g
->memerrmsg
;
120 ** creates a new string object
122 static TString
*createstrobj (lua_State
*L
, const char *str
, size_t l
,
123 int tag
, unsigned int h
) {
126 size_t totalsize
; /* total size of TString object */
127 totalsize
= sizelstring(l
);
128 o
= luaC_newobj(L
, tag
, totalsize
);
132 memcpy(getaddrstr(ts
), str
, l
* sizeof(char));
133 getaddrstr(ts
)[l
] = '\0'; /* ending 0 */
138 void luaS_remove (lua_State
*L
, TString
*ts
) {
139 stringtable
*tb
= &G(L
)->strt
;
140 TString
**p
= &tb
->hash
[lmod(ts
->hash
, tb
->size
)];
141 while (*p
!= ts
) /* find previous element */
143 *p
= (*p
)->u
.hnext
; /* remove element from its list */
149 ** checks whether short string exists and reuses it or creates a new one
151 static TString
*internshrstr (lua_State
*L
, const char *str
, size_t l
) {
153 global_State
*g
= G(L
);
154 unsigned int h
= luaS_hash(str
, l
, g
->seed
);
155 TString
**list
= &g
->strt
.hash
[lmod(h
, g
->strt
.size
)];
156 for (ts
= *list
; ts
!= NULL
; ts
= ts
->u
.hnext
) {
157 if (l
== ts
->shrlen
&&
158 (memcmp(str
, getstr(ts
), l
* sizeof(char)) == 0)) {
160 if (isdead(g
, ts
)) /* dead (but not collected yet)? */
161 changewhite(ts
); /* resurrect it */
165 if (g
->strt
.nuse
>= g
->strt
.size
&& g
->strt
.size
<= MAX_INT
/2) {
166 luaS_resize(L
, g
->strt
.size
* 2);
167 list
= &g
->strt
.hash
[lmod(h
, g
->strt
.size
)]; /* recompute with new size */
169 ts
= createstrobj(L
, str
, l
, LUA_TSHRSTR
, h
);
170 ts
->shrlen
= cast_byte(l
);
179 ** new string (with explicit length)
181 TString
*luaS_newlstr (lua_State
*L
, const char *str
, size_t l
) {
182 if (l
<= LUAI_MAXSHORTLEN
) /* short string? */
183 return internshrstr(L
, str
, l
);
186 if (l
+ 1 > (MAX_SIZE
- sizeof(TString
))/sizeof(char))
188 ts
= createstrobj(L
, str
, l
, LUA_TLNGSTR
, G(L
)->seed
);
196 ** Create or reuse a zero-terminated string, first checking in the
197 ** cache (using the string address as a key). The cache can contain
198 ** only zero-terminated strings, so it is safe to use 'strcmp' to
201 TString
*luaS_new (lua_State
*L
, const char *str
) {
202 unsigned int i
= point2uint(str
) % STRCACHE_SIZE
; /* hash */
203 TString
**p
= G(L
)->strcache
[i
];
204 if (strcmp(str
, getstr(p
[0])) == 0) /* hit? */
205 return p
[0]; /* that it is */
206 else { /* normal route */
207 TString
*s
= luaS_newlstr(L
, str
, strlen(str
));
214 Udata
*luaS_newudata (lua_State
*L
, size_t s
) {
217 if (s
> MAX_SIZE
- sizeof(Udata
))
219 o
= luaC_newobj(L
, LUA_TUSERDATA
, sizeludata(s
));
223 setuservalue(L
, u
, luaO_nilobject
);