ReactOS  0.4.13-dev-259-g5ca9c9c
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 
37 const char *debugstr_jsstr(jsstr_t *str)
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 
60  heap_free(str);
61 }
62 
63 static 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 
73  if(len > JSSTR_MAX_LENGTH)
74  return NULL;
75 
77  if(!ret)
78  return NULL;
79 
80  jsstr_init(&ret->str, len, JSSTR_INLINE);
81  ret->buf[len] = 0;
82  *buf = ret->buf;
83  return &ret->str;
84 }
85 
86 jsstr_t *jsstr_alloc_len(const WCHAR *buf, unsigned len)
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 
98 static 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 
113 void 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 
128 static 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: {
140  jsstr_rope_t *rope = jsstr_as_rope(jsstr);
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 
182 static inline const WCHAR *jsstr_try_flat(jsstr_t *str)
183 {
186  : NULL;
187 }
188 
189 int 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 
234  if(depth++ < JSSTR_MAX_ROPE_DEPTH) {
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 
260 C_ASSERT(sizeof(jsstr_heap_t) <= sizeof(jsstr_rope_t));
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 {
295  return jsstr_addref(undefined_str);
296 }
297 
299 {
300  return jsstr_addref(null_bstr_str);
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 
325 void free_strings(void)
326 {
327  if(empty_str)
329  if(nan_str)
331  if(undefined_str)
333  if(null_bstr_str)
335 }
jsstr_t * jsstr_alloc_len(const WCHAR *buf, unsigned len)
Definition: jsstr.c:86
Definition: _rope.h:91
static jsstr_t * jsstr_alloc(const WCHAR *str)
Definition: jsstr.h:103
jsstr_t * jsstr_nan(void)
Definition: jsstr.c:283
jsstr_tag_t
Definition: jsstr.h:52
#define TRUE
Definition: types.h:120
static jsstr_t * undefined_str
Definition: jsstr.c:281
int memcmp(void *Buffer1, void *Buffer2, ACPI_SIZE Count)
Definition: utclib.c:112
jsstr_t * jsstr_null_bstr(void)
Definition: jsstr.c:298
jsstr_t * jsstr_concat(jsstr_t *str1, jsstr_t *str2)
Definition: jsstr.c:211
#define TMP_BUF_SIZE
Definition: jsstr.c:154
jsstr_t * jsstr_undefined(void)
Definition: jsstr.c:293
Definition: jsstr.h:39
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
static int jsstr_cmp_str(jsstr_t *jsstr, const WCHAR *str, unsigned len)
Definition: jsstr.c:128
static jsstr_t * jsstr_addref(jsstr_t *str)
Definition: jsstr.h:116
static jsstr_rope_t * jsstr_as_rope(jsstr_t *str)
Definition: jsstr.h:132
static unsigned jsstr_flush(jsstr_t *str, WCHAR *buf)
Definition: jsstr.h:148
#define assert(x)
Definition: debug.h:53
Definition: ecma_167.h:138
#define JSSTR_MAX_LENGTH
Definition: jsstr.h:45
static unsigned jsstr_length(jsstr_t *str)
Definition: jsstr.h:58
static void jsstr_release(jsstr_t *str)
Definition: jsstr.h:110
static void * heap_alloc(size_t len)
Definition: appwiz.h:65
const char * wine_dbg_sprintf(const char *format,...)
Definition: compat.c:271
static int ropes_cmp(jsstr_rope_t *left, jsstr_rope_t *right)
Definition: jsstr.c:156
WCHAR * buf
Definition: jsstr.h:90
int jsstr_cmp(jsstr_t *str1, jsstr_t *str2)
Definition: jsstr.c:189
static const WCHAR undefinedW[]
Definition: engine.c:37
unsigned int BOOL
Definition: ntddk_ex.h:94
static PVOID ptr
Definition: dispmode.c:27
const WCHAR * str
jsstr_t * jsstr_empty(void)
Definition: jsstr.c:288
static jsstr_t * empty_str
Definition: jsstr.c:281
smooth NULL
Definition: ftsmooth.c:416
static jsstr_t * nan_str
Definition: jsstr.c:281
static void jsstr_init(jsstr_t *str, unsigned len, jsstr_tag_t tag)
Definition: jsstr.c:63
static const WCHAR NaNW[]
Definition: global.c:32
#define JSSTR_MAX_ROPE_DEPTH
Definition: jsstr.c:35
WCHAR buf[1]
Definition: jsstr.h:85
const char * debugstr_jsstr(jsstr_t *str)
Definition: jsstr.c:37
__wchar_t WCHAR
Definition: xmlstorage.h:180
C_ASSERT(sizeof(jsstr_heap_t)<=sizeof(jsstr_rope_t))
GLint left
Definition: glext.h:7726
unsigned depth
Definition: jsstr.h:97
GLdouble GLdouble right
Definition: glext.h:10859
GLint GLint GLsizei GLsizei GLsizei depth
Definition: gl.h:1546
int ret
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
GLenum GLsizei len
Definition: glext.h:6722
#define JSSTR_SHORT_STRING_LENGTH
Definition: jsstr.c:30
static jsstr_tag_t jsstr_tag(jsstr_t *str)
Definition: jsstr.h:63
#define JSSTR_FLAG_FLAT
Definition: jsstr.h:49
#define debugstr_wn
Definition: kernel32.h:33
static BOOL jsstr_is_heap(jsstr_t *str)
Definition: jsstr.h:73
static BOOL jsstr_is_rope(jsstr_t *str)
Definition: jsstr.h:78
static void jsstr_rope_extract(jsstr_rope_t *str, unsigned off, unsigned len, WCHAR *buf)
Definition: jsstr.c:98
BOOL is_null_bstr(jsstr_t *str)
Definition: jsstr.c:303
const WCHAR * jsstr_rope_flatten(jsstr_rope_t *str)
Definition: jsstr.c:262
void free_strings(void)
Definition: jsstr.c:325
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:254
#define min(a, b)
Definition: monoChain.cc:55
void jsstr_extract(jsstr_t *str, unsigned off, unsigned len, WCHAR *buf)
Definition: jsstr.c:113
static BOOL jsstr_is_inline(jsstr_t *str)
Definition: jsstr.h:68
jsstr_t * jsstr_alloc_buf(unsigned len, WCHAR **buf)
Definition: jsstr.c:69
static jsstr_t * null_bstr_str
Definition: jsstr.c:281
void jsstr_free(jsstr_t *str)
Definition: jsstr.c:44
static jsstr_heap_t * jsstr_as_heap(jsstr_t *str)
Definition: jsstr.h:127
static const WCHAR * jsstr_try_flat(jsstr_t *str)
Definition: jsstr.c:182
static jsstr_inline_t * jsstr_as_inline(jsstr_t *str)
Definition: jsstr.h:122
BOOL init_strings(void)
Definition: jsstr.c:308
static BOOL heap_free(void *mem)
Definition: appwiz.h:75
#define JSSTR_LENGTH_SHIFT
Definition: jsstr.h:44
off
Definition: i386-dis.c:3909
char * tag
Definition: main.c:59