ReactOS 0.4.15-dev-7788-g1ad9096
jsstr.c
Go to the documentation of this file.
1/*
2 * Copyright 2012 Jacek Caban for CodeWeavers
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
17 */
18
19#include <assert.h>
20
21#include "jscript.h"
22
23#include "wine/debug.h"
24
25/*
26 * This is the length of a string that is considered to be long enough to be
27 * worth the rope to avoid copy.
28 * This probably could be tuned, but keep it low for a while to better test rope's code.
29 */
30#define JSSTR_SHORT_STRING_LENGTH 8
31
32/*
33 * This is the max rope depth. While faster to allocate, ropes may become slow at access.
34 */
35#define JSSTR_MAX_ROPE_DEPTH 100
36
38{
42}
43
45{
46 switch(jsstr_tag(str)) {
47 case JSSTR_HEAP:
49 break;
50 case JSSTR_ROPE: {
52 jsstr_release(rope->left);
53 jsstr_release(rope->right);
54 break;
55 }
56 case JSSTR_INLINE:
57 break;
58 }
59
61}
62
63static inline void jsstr_init(jsstr_t *str, unsigned len, jsstr_tag_t tag)
64{
65 str->length_flags = len << JSSTR_LENGTH_SHIFT | tag;
66 str->ref = 1;
67}
68
70{
72
74 return NULL;
75
77 if(!ret)
78 return NULL;
79
81 ret->buf[len] = 0;
82 *buf = ret->buf;
83 return &ret->str;
84}
85
87{
88 jsstr_t *ret;
89 WCHAR *ptr;
90
92 if(ret)
93 memcpy(ptr, buf, len*sizeof(WCHAR));
94
95 return ret;
96}
97
98static void jsstr_rope_extract(jsstr_rope_t *str, unsigned off, unsigned len, WCHAR *buf)
99{
100 unsigned left_len = jsstr_length(str->left);
101
102 if(left_len <= off) {
103 jsstr_extract(str->right, off-left_len, len, buf);
104 }else if(left_len >= len+off) {
105 jsstr_extract(str->left, off, len, buf);
106 }else {
107 left_len -= off;
108 jsstr_extract(str->left, off, left_len, buf);
109 jsstr_extract(str->right, 0, len-left_len, buf+left_len);
110 }
111}
112
113void jsstr_extract(jsstr_t *str, unsigned off, unsigned len, WCHAR *buf)
114{
115 switch(jsstr_tag(str)) {
116 case JSSTR_INLINE:
117 memcpy(buf, jsstr_as_inline(str)->buf+off, len*sizeof(WCHAR));
118 return;
119 case JSSTR_HEAP:
120 memcpy(buf, jsstr_as_heap(str)->buf+off, len*sizeof(WCHAR));
121 return;
122 case JSSTR_ROPE:
124 return;
125 }
126}
127
128static int jsstr_cmp_str(jsstr_t *jsstr, const WCHAR *str, unsigned len)
129{
130 int ret;
131
132 switch(jsstr_tag(jsstr)) {
133 case JSSTR_INLINE:
134 ret = memcmp(jsstr_as_inline(jsstr)->buf, str, len*sizeof(WCHAR));
135 return ret || jsstr_length(jsstr) == len ? ret : 1;
136 case JSSTR_HEAP:
137 ret = memcmp(jsstr_as_heap(jsstr)->buf, str, len*sizeof(WCHAR));
138 return ret || jsstr_length(jsstr) == len ? ret : 1;
139 case JSSTR_ROPE: {
141 unsigned left_len = jsstr_length(rope->left);
142
143 ret = jsstr_cmp_str(rope->left, str, min(len, left_len));
144 if(ret || len <= left_len)
145 return ret;
146 return jsstr_cmp_str(rope->right, str+left_len, len-left_len);
147 }
148 }
149
150 assert(0);
151 return 0;
152}
153
154#define TMP_BUF_SIZE 256
155
157{
158 WCHAR left_buf[TMP_BUF_SIZE], right_buf[TMP_BUF_SIZE];
159 unsigned left_len = jsstr_length(&left->str);
160 unsigned right_len = jsstr_length(&right->str);
161 unsigned cmp_off = 0, cmp_size;
162 int ret;
163
164 /* FIXME: We can avoid temporary buffers here. */
165 while(cmp_off < min(left_len, right_len)) {
166 cmp_size = min(left_len, right_len) - cmp_off;
167 if(cmp_size > TMP_BUF_SIZE)
168 cmp_size = TMP_BUF_SIZE;
169
170 jsstr_rope_extract(left, cmp_off, cmp_size, left_buf);
171 jsstr_rope_extract(right, cmp_off, cmp_size, right_buf);
172 ret = memcmp(left_buf, right_buf, cmp_size);
173 if(ret)
174 return ret;
175
176 cmp_off += cmp_size;
177 }
178
179 return left_len - right_len;
180}
181
182static inline const WCHAR *jsstr_try_flat(jsstr_t *str)
183{
186 : NULL;
187}
188
189int jsstr_cmp(jsstr_t *str1, jsstr_t *str2)
190{
191 unsigned len1 = jsstr_length(str1);
192 unsigned len2 = jsstr_length(str2);
193 const WCHAR *str;
194 int ret;
195
196 str = jsstr_try_flat(str2);
197 if(str) {
198 ret = jsstr_cmp_str(str1, str, min(len1, len2));
199 return ret || len1 == len2 ? ret : -1;
200 }
201
202 str = jsstr_try_flat(str1);
203 if(str) {
204 ret = jsstr_cmp_str(str2, str, min(len1, len2));
205 return ret || len1 == len2 ? -ret : 1;
206 }
207
208 return ropes_cmp(jsstr_as_rope(str1), jsstr_as_rope(str2));
209}
210
212{
213 unsigned len1, len2;
214 jsstr_t *ret;
215 WCHAR *ptr;
216
217 len1 = jsstr_length(str1);
218 if(!len1)
219 return jsstr_addref(str2);
220
221 len2 = jsstr_length(str2);
222 if(!len2)
223 return jsstr_addref(str1);
224
225 if(len1 + len2 >= JSSTR_SHORT_STRING_LENGTH) {
226 unsigned depth, depth2;
228
229 depth = jsstr_is_rope(str1) ? jsstr_as_rope(str1)->depth : 0;
230 depth2 = jsstr_is_rope(str2) ? jsstr_as_rope(str2)->depth : 0;
231 if(depth2 > depth)
232 depth = depth2;
233
235 if(len1+len2 > JSSTR_MAX_LENGTH)
236 return NULL;
237
238 rope = heap_alloc(sizeof(*rope));
239 if(!rope)
240 return NULL;
241
242 jsstr_init(&rope->str, len1+len2, JSSTR_ROPE);
243 rope->left = jsstr_addref(str1);
244 rope->right = jsstr_addref(str2);
245 rope->depth = depth;
246 return &rope->str;
247 }
248 }
249
250 ret = jsstr_alloc_buf(len1+len2, &ptr);
251 if(!ret)
252 return NULL;
253
254 jsstr_flush(str1, ptr);
255 jsstr_flush(str2, ptr+len1);
256 return ret;
257
258}
259
261
263{
264 WCHAR *buf;
265
266 buf = heap_alloc((jsstr_length(&str->str)+1) * sizeof(WCHAR));
267 if(!buf)
268 return NULL;
269
270 jsstr_flush(str->left, buf);
271 jsstr_flush(str->right, buf+jsstr_length(str->left));
272 buf[jsstr_length(&str->str)] = 0;
273
274 /* Trasform to heap string */
275 jsstr_release(str->left);
276 jsstr_release(str->right);
277 str->str.length_flags |= JSSTR_FLAG_FLAT;
278 return jsstr_as_heap(&str->str)->buf = buf;
279}
280
282
284{
285 return jsstr_addref(nan_str);
286}
287
289{
290 return jsstr_addref(empty_str);
291}
292
294{
296}
297
299{
301}
302
304{
305 return str == null_bstr_str;
306}
307
309{
310 static const WCHAR NaNW[] = { 'N','a','N',0 };
311 static const WCHAR undefinedW[] = {'u','n','d','e','f','i','n','e','d',0};
312 WCHAR *ptr;
313
314 if(!(empty_str = jsstr_alloc_buf(0, &ptr)))
315 return FALSE;
316 if(!(nan_str = jsstr_alloc(NaNW)))
317 return FALSE;
319 return FALSE;
320 if(!(null_bstr_str = jsstr_alloc_buf(0, &ptr)))
321 return FALSE;
322 return TRUE;
323}
324
325void free_strings(void)
326{
327 if(empty_str)
329 if(nan_str)
331 if(undefined_str)
333 if(null_bstr_str)
335}
int memcmp(void *Buffer1, void *Buffer2, ACPI_SIZE Count)
Definition: utclib.c:112
static void * heap_alloc(size_t len)
Definition: appwiz.h:66
static BOOL heap_free(void *mem)
Definition: appwiz.h:76
Definition: _rope.h:1087
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
const char * wine_dbg_sprintf(const char *format,...)
Definition: compat.c:296
#define assert(x)
Definition: debug.h:53
static const WCHAR undefinedW[]
Definition: engine.c:39
unsigned int BOOL
Definition: ntddk_ex.h:94
GLint GLint GLsizei GLsizei GLsizei depth
Definition: gl.h:1546
GLdouble GLdouble right
Definition: glext.h:10859
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
GLint left
Definition: glext.h:7726
GLenum GLsizei len
Definition: glext.h:6722
#define C_ASSERT(e)
Definition: intsafe.h:73
static const WCHAR NaNW[]
Definition: global.c:34
BOOL init_strings(void)
Definition: jsstr.c:308
static int ropes_cmp(jsstr_rope_t *left, jsstr_rope_t *right)
Definition: jsstr.c:156
void free_strings(void)
Definition: jsstr.c:325
#define TMP_BUF_SIZE
Definition: jsstr.c:154
jsstr_t * jsstr_null_bstr(void)
Definition: jsstr.c:298
static void jsstr_init(jsstr_t *str, unsigned len, jsstr_tag_t tag)
Definition: jsstr.c:63
static int jsstr_cmp_str(jsstr_t *jsstr, const WCHAR *str, unsigned len)
Definition: jsstr.c:128
jsstr_t * jsstr_alloc_len(const WCHAR *buf, unsigned len)
Definition: jsstr.c:86
static const WCHAR * jsstr_try_flat(jsstr_t *str)
Definition: jsstr.c:182
jsstr_t * jsstr_nan(void)
Definition: jsstr.c:283
const WCHAR * jsstr_rope_flatten(jsstr_rope_t *str)
Definition: jsstr.c:262
#define JSSTR_SHORT_STRING_LENGTH
Definition: jsstr.c:30
void jsstr_free(jsstr_t *str)
Definition: jsstr.c:44
BOOL is_null_bstr(jsstr_t *str)
Definition: jsstr.c:303
static jsstr_t * undefined_str
Definition: jsstr.c:281
static jsstr_t * null_bstr_str
Definition: jsstr.c:281
static void jsstr_rope_extract(jsstr_rope_t *str, unsigned off, unsigned len, WCHAR *buf)
Definition: jsstr.c:98
static jsstr_t * empty_str
Definition: jsstr.c:281
int jsstr_cmp(jsstr_t *str1, jsstr_t *str2)
Definition: jsstr.c:189
jsstr_t * jsstr_undefined(void)
Definition: jsstr.c:293
jsstr_t * jsstr_empty(void)
Definition: jsstr.c:288
jsstr_t * jsstr_concat(jsstr_t *str1, jsstr_t *str2)
Definition: jsstr.c:211
const char * debugstr_jsstr(jsstr_t *str)
Definition: jsstr.c:37
static jsstr_t * nan_str
Definition: jsstr.c:281
void jsstr_extract(jsstr_t *str, unsigned off, unsigned len, WCHAR *buf)
Definition: jsstr.c:113
#define JSSTR_MAX_ROPE_DEPTH
Definition: jsstr.c:35
jsstr_t * jsstr_alloc_buf(unsigned len, WCHAR **buf)
Definition: jsstr.c:69
#define JSSTR_MAX_LENGTH
Definition: jsstr.h:45
static jsstr_t * jsstr_addref(jsstr_t *str)
Definition: jsstr.h:116
static void jsstr_release(jsstr_t *str)
Definition: jsstr.h:110
static jsstr_inline_t * jsstr_as_inline(jsstr_t *str)
Definition: jsstr.h:122
static unsigned jsstr_length(jsstr_t *str)
Definition: jsstr.h:58
#define JSSTR_LENGTH_SHIFT
Definition: jsstr.h:44
#define JSSTR_FLAG_FLAT
Definition: jsstr.h:49
static BOOL jsstr_is_rope(jsstr_t *str)
Definition: jsstr.h:78
static jsstr_tag_t jsstr_tag(jsstr_t *str)
Definition: jsstr.h:63
static jsstr_heap_t * jsstr_as_heap(jsstr_t *str)
Definition: jsstr.h:127
static BOOL jsstr_is_heap(jsstr_t *str)
Definition: jsstr.h:73
static unsigned jsstr_flush(jsstr_t *str, WCHAR *buf)
Definition: jsstr.h:148
static jsstr_t * jsstr_alloc(const WCHAR *str)
Definition: jsstr.h:103
static BOOL jsstr_is_inline(jsstr_t *str)
Definition: jsstr.h:68
static jsstr_rope_t * jsstr_as_rope(jsstr_t *str)
Definition: jsstr.h:132
jsstr_tag_t
Definition: jsstr.h:52
@ JSSTR_INLINE
Definition: jsstr.h:53
@ JSSTR_HEAP
Definition: jsstr.h:54
@ JSSTR_ROPE
Definition: jsstr.h:55
#define debugstr_wn
Definition: kernel32.h:33
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
static PVOID ptr
Definition: dispmode.c:27
#define min(a, b)
Definition: monoChain.cc:55
const WCHAR * str
Definition: jsstr.h:39
WCHAR * buf
Definition: jsstr.h:90
WCHAR buf[1]
Definition: jsstr.h:85
unsigned depth
Definition: jsstr.h:97
Definition: ecma_167.h:138
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:255
int ret
__wchar_t WCHAR
Definition: xmlstorage.h:180