dll/win32/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 "jscript.h"
  20
  21 /*
  22  * This is the length of a string that is considered to be long enough to be
  23  * worth the rope to avoid copy.
  24  * This probably could be tuned, but keep it low for a while to better test rope's code.
  25  */
  26 #define JSSTR_SHORT_STRING_LENGTH 8
  27
  28 /*
  29  * This is the max rope depth. While faster to allocate, ropes may become slow at access.
  30  */
  31 #define JSSTR_MAX_ROPE_DEPTH 100
  32
  33 const char *debugstr_jsstr(jsstr_t *str)
  34 {
  35     return jsstr_is_inline(str) ? debugstr_wn(jsstr_as_inline(str)->buf, jsstr_length(str))
  36         : jsstr_is_heap(str) ? debugstr_wn(jsstr_as_heap(str)->buf, jsstr_length(str))
  37         : wine_dbg_sprintf("%s...", debugstr_jsstr(jsstr_as_rope(str)->left));
  38 }
  39
  40 void jsstr_free(jsstr_t *str)
  41 {
  42     switch(jsstr_tag(str)) {
  43     case JSSTR_HEAP:
  44         heap_free(jsstr_as_heap(str)->buf);
  45         break;
  46     case JSSTR_ROPE: {
  47         jsstr_rope_t *rope = jsstr_as_rope(str);
  48         jsstr_release(rope->left);
  49         jsstr_release(rope->right);
  50         break;
  51     }
  52     case JSSTR_INLINE:
  53         break;
  54     }
  55
  56     heap_free(str);
  57 }
  58
  59 static inline void jsstr_init(jsstr_t *str, unsigned len, jsstr_tag_t tag)
  60 {
  61     str->length_flags = len << JSSTR_LENGTH_SHIFT | tag;
  62     str->ref = 1;
  63 }
  64
  65 WCHAR *jsstr_alloc_buf(unsigned len, jsstr_t **r)
  66 {
  67     jsstr_inline_t *ret;
  68
  69     if(len > JSSTR_MAX_LENGTH)
  70         return NULL;
  71
  72     ret = heap_alloc(FIELD_OFFSET(jsstr_inline_t, buf[len+1]));
  73     if(!ret)
  74         return NULL;
  75
  76     jsstr_init(&ret->str, len, JSSTR_INLINE);
  77     ret->buf[len] = 0;
  78     *r = &ret->str;
  79     return ret->buf;
  80 }
  81
  82 jsstr_t *jsstr_alloc_len(const WCHAR *buf, unsigned len)
  83 {
  84     jsstr_t *ret;
  85     WCHAR *ptr;
  86
  87     ptr = jsstr_alloc_buf(len, &ret);
  88     if(ptr)
  89         memcpy(ptr, buf, len*sizeof(WCHAR));
  90
  91     return ret;
  92 }
  93
  94 static void jsstr_rope_extract(jsstr_rope_t *str, unsigned off, unsigned len, WCHAR *buf)
  95 {
  96     unsigned left_len = jsstr_length(str->left);
  97
  98     if(left_len <= off) {
  99         jsstr_extract(str->right, off-left_len, len, buf);
 100     }else if(left_len >= len+off) {
 101         jsstr_extract(str->left, off, len, buf);
 102     }else {
 103         left_len -= off;
 104         jsstr_extract(str->left, off, left_len, buf);
 105         jsstr_extract(str->right, 0, len-left_len, buf+left_len);
 106     }
 107 }
 108
 109 void jsstr_extract(jsstr_t *str, unsigned off, unsigned len, WCHAR *buf)
 110 {
 111     switch(jsstr_tag(str)) {
 112     case JSSTR_INLINE:
 113         memcpy(buf, jsstr_as_inline(str)->buf+off, len*sizeof(WCHAR));
 114         return;
 115     case JSSTR_HEAP:
 116         memcpy(buf, jsstr_as_heap(str)->buf+off, len*sizeof(WCHAR));
 117         return;
 118     case JSSTR_ROPE:
 119         jsstr_rope_extract(jsstr_as_rope(str), off, len, buf);
 120         return;
 121     }
 122 }
 123
 124 static int jsstr_cmp_str(jsstr_t *jsstr, const WCHAR *str, unsigned len)
 125 {
 126     int ret;
 127
 128     switch(jsstr_tag(jsstr)) {
 129     case JSSTR_INLINE:
 130         ret = memcmp(jsstr_as_inline(jsstr)->buf, str, len*sizeof(WCHAR));
 131         return ret || jsstr_length(jsstr) == len ? ret : 1;
 132     case JSSTR_HEAP:
 133         ret = memcmp(jsstr_as_heap(jsstr)->buf, str, len*sizeof(WCHAR));
 134         return ret || jsstr_length(jsstr) == len ? ret : 1;
 135     case JSSTR_ROPE: {
 136         jsstr_rope_t *rope = jsstr_as_rope(jsstr);
 137         unsigned left_len = jsstr_length(rope->left);
 138
 139         ret = jsstr_cmp_str(rope->left, str, min(len, left_len));
 140         if(ret || len <= left_len)
 141             return ret;
 142         return jsstr_cmp_str(rope->right, str+left_len, len-left_len);
 143     }
 144     }
 145
 146     assert(0);
 147     return 0;
 148 }
 149
 150 #define TMP_BUF_SIZE 256
 151
 152 static int ropes_cmp(jsstr_rope_t *left, jsstr_rope_t *right)
 153 {
 154     WCHAR left_buf[TMP_BUF_SIZE], right_buf[TMP_BUF_SIZE];
 155     unsigned left_len = jsstr_length(&left->str);
 156     unsigned right_len = jsstr_length(&right->str);
 157     unsigned cmp_off = 0, cmp_size;
 158     int ret;
 159
 160     /* FIXME: We can avoid temporary buffers here. */
 161     while(cmp_off < min(left_len, right_len)) {
 162         cmp_size = min(left_len, right_len) - cmp_off;
 163         if(cmp_size > TMP_BUF_SIZE)
 164             cmp_size = TMP_BUF_SIZE;
 165
 166         jsstr_rope_extract(left, cmp_off, cmp_size, left_buf);
 167         jsstr_rope_extract(right, cmp_off, cmp_size, right_buf);
 168         ret = memcmp(left_buf, right_buf, cmp_size);
 169         if(ret)
 170             return ret;
 171
 172         cmp_off += cmp_size;
 173     }
 174
 175     return left_len - right_len;
 176 }
 177
 178 static inline const WCHAR *jsstr_try_flat(jsstr_t *str)
 179 {
 180     return jsstr_is_inline(str) ? jsstr_as_inline(str)->buf
 181         : jsstr_is_heap(str) ? jsstr_as_heap(str)->buf
 182         : NULL;
 183 }
 184
 185 int jsstr_cmp(jsstr_t *str1, jsstr_t *str2)
 186 {
 187     unsigned len1 = jsstr_length(str1);
 188     unsigned len2 = jsstr_length(str2);
 189     const WCHAR *str;
 190     int ret;
 191
 192     str = jsstr_try_flat(str2);
 193     if(str) {
 194         ret = jsstr_cmp_str(str1, str, min(len1, len2));
 195         return ret || len1 == len2 ? ret : -1;
 196     }
 197
 198     str = jsstr_try_flat(str1);
 199     if(str) {
 200         ret = jsstr_cmp_str(str2, str, min(len1, len2));
 201         return ret || len1 == len2 ? -ret : 1;
 202     }
 203
 204     return ropes_cmp(jsstr_as_rope(str1), jsstr_as_rope(str2));
 205 }
 206
 207 jsstr_t *jsstr_concat(jsstr_t *str1, jsstr_t *str2)
 208 {
 209     unsigned len1, len2;
 210     jsstr_t *ret;
 211     WCHAR *ptr;
 212
 213     len1 = jsstr_length(str1);
 214     if(!len1)
 215         return jsstr_addref(str2);
 216
 217     len2 = jsstr_length(str2);
 218     if(!len2)
 219         return jsstr_addref(str1);
 220
 221     if(len1 + len2 >= JSSTR_SHORT_STRING_LENGTH) {
 222         unsigned depth, depth2;
 223         jsstr_rope_t *rope;
 224
 225         depth = jsstr_is_rope(str1) ? jsstr_as_rope(str1)->depth : 0;
 226         depth2 = jsstr_is_rope(str2) ? jsstr_as_rope(str2)->depth : 0;
 227         if(depth2 > depth)
 228             depth = depth2;
 229
 230         if(depth++ < JSSTR_MAX_ROPE_DEPTH) {
 231             if(len1+len2 > JSSTR_MAX_LENGTH)
 232                 return NULL;
 233
 234             rope = heap_alloc(sizeof(*rope));
 235             if(!rope)
 236                 return NULL;
 237
 238             jsstr_init(&rope->str, len1+len2, JSSTR_ROPE);
 239             rope->left = jsstr_addref(str1);
 240             rope->right = jsstr_addref(str2);
 241             rope->depth = depth;
 242             return &rope->str;
 243         }
 244     }
 245
 246     ptr = jsstr_alloc_buf(len1+len2, &ret);
 247     if(!ret)
 248         return NULL;
 249
 250     jsstr_flush(str1, ptr);
 251     jsstr_flush(str2, ptr+len1);
 252     return ret;
 253
 254 }
 255
 256 C_ASSERT(sizeof(jsstr_heap_t) <= sizeof(jsstr_rope_t));
 257
 258 const WCHAR *jsstr_rope_flatten(jsstr_rope_t *str)
 259 {
 260     WCHAR *buf;
 261
 262     buf = heap_alloc((jsstr_length(&str->str)+1) * sizeof(WCHAR));
 263     if(!buf)
 264         return NULL;
 265
 266     jsstr_flush(str->left, buf);
 267     jsstr_flush(str->right, buf+jsstr_length(str->left));
 268     buf[jsstr_length(&str->str)] = 0;
 269
 270     /* Trasform to heap string */
 271     jsstr_release(str->left);
 272     jsstr_release(str->right);
 273     str->str.length_flags |= JSSTR_FLAG_FLAT;
 274     return jsstr_as_heap(&str->str)->buf = buf;
 275 }
 276
 277 static jsstr_t *empty_str, *nan_str, *undefined_str, *null_bstr_str;
 278
 279 jsstr_t *jsstr_nan(void)
 280 {
 281     return jsstr_addref(nan_str);
 282 }
 283
 284 jsstr_t *jsstr_empty(void)
 285 {
 286     return jsstr_addref(empty_str);
 287 }
 288
 289 jsstr_t *jsstr_undefined(void)
 290 {
 291     return jsstr_addref(undefined_str);
 292 }
 293
 294 jsstr_t *jsstr_null_bstr(void)
 295 {
 296     return jsstr_addref(null_bstr_str);
 297 }
 298
 299 BOOL is_null_bstr(jsstr_t *str)
 300 {
 301     return str == null_bstr_str;
 302 }
 303
 304 BOOL init_strings(void)
 305 {
 306     static const WCHAR NaNW[] = { 'N','a','N',0 };
 307     static const WCHAR undefinedW[] = {'u','n','d','e','f','i','n','e','d',0};
 308
 309     if(!jsstr_alloc_buf(0, &empty_str))
 310         return FALSE;
 311     if(!(nan_str = jsstr_alloc(NaNW)))
 312         return FALSE;
 313     if(!(undefined_str = jsstr_alloc(undefinedW)))
 314         return FALSE;
 315     if(!jsstr_alloc_buf(0, &null_bstr_str))
 316         return FALSE;
 317      return TRUE;
 318 }
 319
 320 void free_strings(void)
 321 {
 322     if(empty_str)
 323         jsstr_release(empty_str);
 324     if(nan_str)
 325         jsstr_release(nan_str);
 326     if(undefined_str)
 327         jsstr_release(undefined_str);
 328     if(null_bstr_str)
 329         jsstr_release(null_bstr_str);
 330 }