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 { 39 return jsstr_is_inline(str) ? debugstr_wn(jsstr_as_inline(str)->buf, jsstr_length(str)) 40 : jsstr_is_heap(str) ? debugstr_wn(jsstr_as_heap(str)->buf, jsstr_length(str)) 41 : wine_dbg_sprintf("%s...", debugstr_jsstr(jsstr_as_rope(str)->left)); 42 } 43 44 void jsstr_free(jsstr_t *str) 45 { 46 switch(jsstr_tag(str)) { 47 case JSSTR_HEAP: 48 heap_free(jsstr_as_heap(str)->buf); 49 break; 50 case JSSTR_ROPE: { 51 jsstr_rope_t *rope = jsstr_as_rope(str); 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 69 jsstr_t *jsstr_alloc_buf(unsigned len, WCHAR **buf) 70 { 71 jsstr_inline_t *ret; 72 73 if(len > JSSTR_MAX_LENGTH) 74 return NULL; 75 76 ret = heap_alloc(FIELD_OFFSET(jsstr_inline_t, buf[len+1])); 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 91 ret = jsstr_alloc_buf(len, &ptr); 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: 123 jsstr_rope_extract(jsstr_as_rope(str), off, len, buf); 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 156 static int ropes_cmp(jsstr_rope_t *left, jsstr_rope_t *right) 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 { 184 return jsstr_is_inline(str) ? jsstr_as_inline(str)->buf 185 : jsstr_is_heap(str) ? jsstr_as_heap(str)->buf 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 211 jsstr_t *jsstr_concat(jsstr_t *str1, jsstr_t *str2) 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; 227 jsstr_rope_t *rope; 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 262 const WCHAR *jsstr_rope_flatten(jsstr_rope_t *str) 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 281 static jsstr_t *empty_str, *nan_str, *undefined_str, *null_bstr_str; 282 283 jsstr_t *jsstr_nan(void) 284 { 285 return jsstr_addref(nan_str); 286 } 287 288 jsstr_t *jsstr_empty(void) 289 { 290 return jsstr_addref(empty_str); 291 } 292 293 jsstr_t *jsstr_undefined(void) 294 { 295 return jsstr_addref(undefined_str); 296 } 297 298 jsstr_t *jsstr_null_bstr(void) 299 { 300 return jsstr_addref(null_bstr_str); 301 } 302 303 BOOL is_null_bstr(jsstr_t *str) 304 { 305 return str == null_bstr_str; 306 } 307 308 BOOL init_strings(void) 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; 318 if(!(undefined_str = jsstr_alloc(undefinedW))) 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) 328 jsstr_release(empty_str); 329 if(nan_str) 330 jsstr_release(nan_str); 331 if(undefined_str) 332 jsstr_release(undefined_str); 333 if(null_bstr_str) 334 jsstr_release(null_bstr_str); 335 } 336