dlls/jscript/jsstr.c

   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         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     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 = malloc(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         return jsstr_rope_extract(jsstr_as_rope(str), off, len, buf);
 124     }
 125 }
 126
 127 static int jsstr_cmp_str(jsstr_t *jsstr, const WCHAR *str, unsigned len)
 128 {
 129     int ret;
 130
 131     switch(jsstr_tag(jsstr)) {
 132     case JSSTR_INLINE:
 133         ret = memcmp(jsstr_as_inline(jsstr)->buf, str, len*sizeof(WCHAR));
 134         return ret || jsstr_length(jsstr) == len ? ret : 1;
 135     case JSSTR_HEAP:
 136         ret = memcmp(jsstr_as_heap(jsstr)->buf, str, len*sizeof(WCHAR));
 137         return ret || jsstr_length(jsstr) == len ? ret : 1;
 138     case JSSTR_ROPE: {
 139         jsstr_rope_t *rope = jsstr_as_rope(jsstr);
 140         unsigned left_len = jsstr_length(rope->left);
 141
 142         ret = jsstr_cmp_str(rope->left, str, min(len, left_len));
 143         if(ret || len <= left_len)
 144             return ret;
 145         return jsstr_cmp_str(rope->right, str+left_len, len-left_len);
 146     }
 147     }
 148
 149     assert(0);
 150     return 0;
 151 }
 152
 153 #define TMP_BUF_SIZE 256
 154
 155 static int ropes_cmp(jsstr_rope_t *left, jsstr_rope_t *right)
 156 {
 157     WCHAR left_buf[TMP_BUF_SIZE], right_buf[TMP_BUF_SIZE];
 158     unsigned left_len = jsstr_length(&left->str);
 159     unsigned right_len = jsstr_length(&right->str);
 160     unsigned cmp_off = 0, cmp_size;
 161     int ret;
 162
 163     /* FIXME: We can avoid temporary buffers here. */
 164     while(cmp_off < min(left_len, right_len)) {
 165         cmp_size = min(left_len, right_len) - cmp_off;
 166         if(cmp_size > TMP_BUF_SIZE)
 167             cmp_size = TMP_BUF_SIZE;
 168
 169         jsstr_rope_extract(left, cmp_off, cmp_size, left_buf);
 170         jsstr_rope_extract(right, cmp_off, cmp_size, right_buf);
 171         ret = memcmp(left_buf, right_buf, cmp_size);
 172         if(ret)
 173             return ret;
 174
 175         cmp_off += cmp_size;
 176     }
 177
 178     return left_len - right_len;
 179 }
 180
 181 static inline const WCHAR *jsstr_try_flat(jsstr_t *str)
 182 {
 183     return jsstr_is_inline(str) ? jsstr_as_inline(str)->buf
 184         : jsstr_is_heap(str) ? jsstr_as_heap(str)->buf
 185         : NULL;
 186 }
 187
 188 int jsstr_cmp(jsstr_t *str1, jsstr_t *str2)
 189 {
 190     unsigned len1 = jsstr_length(str1);
 191     unsigned len2 = jsstr_length(str2);
 192     const WCHAR *str;
 193     int ret;
 194
 195     str = jsstr_try_flat(str2);
 196     if(str) {
 197         ret = jsstr_cmp_str(str1, str, min(len1, len2));
 198         return ret || len1 == len2 ? ret : -1;
 199     }
 200
 201     str = jsstr_try_flat(str1);
 202     if(str) {
 203         ret = jsstr_cmp_str(str2, str, min(len1, len2));
 204         return ret || len1 == len2 ? -ret : 1;
 205     }
 206
 207     return ropes_cmp(jsstr_as_rope(str1), jsstr_as_rope(str2));
 208 }
 209
 210 jsstr_t *jsstr_concat(jsstr_t *str1, jsstr_t *str2)
 211 {
 212     unsigned len1, len2;
 213     jsstr_t *ret;
 214     WCHAR *ptr;
 215
 216     len1 = jsstr_length(str1);
 217     if(!len1)
 218         return jsstr_addref(str2);
 219
 220     len2 = jsstr_length(str2);
 221     if(!len2)
 222         return jsstr_addref(str1);
 223
 224     if(len1 + len2 >= JSSTR_SHORT_STRING_LENGTH) {
 225         unsigned depth, depth2;
 226         jsstr_rope_t *rope;
 227
 228         depth = jsstr_is_rope(str1) ? jsstr_as_rope(str1)->depth : 0;
 229         depth2 = jsstr_is_rope(str2) ? jsstr_as_rope(str2)->depth : 0;
 230         if(depth2 > depth)
 231             depth = depth2;
 232
 233         if(depth++ < JSSTR_MAX_ROPE_DEPTH) {
 234             if(len1+len2 > JSSTR_MAX_LENGTH)
 235                 return NULL;
 236
 237             rope = malloc(sizeof(*rope));
 238             if(!rope)
 239                 return NULL;
 240
 241             jsstr_init(&rope->str, len1+len2, JSSTR_ROPE);
 242             rope->left = jsstr_addref(str1);
 243             rope->right = jsstr_addref(str2);
 244             rope->depth = depth;
 245             return &rope->str;
 246         }
 247     }
 248
 249     ret = jsstr_alloc_buf(len1+len2, &ptr);
 250     if(!ret)
 251         return NULL;
 252
 253     jsstr_flush(str1, ptr);
 254     jsstr_flush(str2, ptr+len1);
 255     return ret;
 256
 257 }
 258
 259 C_ASSERT(sizeof(jsstr_heap_t) <= sizeof(jsstr_rope_t));
 260
 261 const WCHAR *jsstr_rope_flatten(jsstr_rope_t *str)
 262 {
 263     WCHAR *buf;
 264
 265     buf = malloc((jsstr_length(&str->str)+1) * sizeof(WCHAR));
 266     if(!buf)
 267         return NULL;
 268
 269     jsstr_flush(str->left, buf);
 270     jsstr_flush(str->right, buf+jsstr_length(str->left));
 271     buf[jsstr_length(&str->str)] = 0;
 272
 273     /* Trasform to heap string */
 274     jsstr_release(str->left);
 275     jsstr_release(str->right);
 276     str->str.length_flags |= JSSTR_FLAG_FLAT;
 277     return jsstr_as_heap(&str->str)->buf = buf;
 278 }
 279
 280 static jsstr_t *empty_str, *nan_str, *undefined_str, *null_bstr_str;
 281
 282 jsstr_t *jsstr_nan(void)
 283 {
 284     return jsstr_addref(nan_str);
 285 }
 286
 287 jsstr_t *jsstr_empty(void)
 288 {
 289     return jsstr_addref(empty_str);
 290 }
 291
 292 jsstr_t *jsstr_undefined(void)
 293 {
 294     return jsstr_addref(undefined_str);
 295 }
 296
 297 jsstr_t *jsstr_null_bstr(void)
 298 {
 299     return jsstr_addref(null_bstr_str);
 300 }
 301
 302 HRESULT jsstr_to_bstr(jsstr_t *str, BSTR *r)
 303 {
 304     if(str == null_bstr_str) {
 305         *r = NULL;
 306         return S_OK;
 307     }
 308
 309     if(!(*r = SysAllocStringLen(NULL, jsstr_length(str))))
 310         return E_OUTOFMEMORY;
 311
 312     jsstr_flush(str, *r);
 313     return S_OK;
 314 }
 315
 316 BOOL init_strings(void)
 317 {
 318     WCHAR *ptr;
 319
 320     if(!(empty_str = jsstr_alloc_buf(0, &ptr)))
 321         return FALSE;
 322     if(!(nan_str = jsstr_alloc(L"NaN")))
 323         return FALSE;
 324     if(!(undefined_str = jsstr_alloc(L"undefined")))
 325         return FALSE;
 326     if(!(null_bstr_str = jsstr_alloc_buf(0, &ptr)))
 327         return FALSE;
 328      return TRUE;
 329 }
 330
 331 void free_strings(void)
 332 {
 333     if(empty_str)
 334         jsstr_release(empty_str);
 335     if(nan_str)
 336         jsstr_release(nan_str);
 337     if(undefined_str)
 338         jsstr_release(undefined_str);
 339     if(null_bstr_str)
 340         jsstr_release(null_bstr_str);
 341 }