QRScanner/mobile/jni/thirdparty/mujs/jsproperty.c

   1 #include "jsi.h"
   2 #include "jsvalue.h"
   3
   4 /*
   5         Use an AA-tree to quickly look up properties in objects:
   6
   7         The level of every leaf node is one.
   8         The level of every left child is one less than its parent.
   9         The level of every right child is equal or one less than its parent.
  10         The level of every right grandchild is less than its grandparent.
  11         Every node of level greater than one has two children.
  12
  13         A link where the child's level is equal to that of its parent is called a horizontal link.
  14         Individual right horizontal links are allowed, but consecutive ones are forbidden.
  15         Left horizontal links are forbidden.
  16
  17         skew() fixes left horizontal links.
  18         split() fixes consecutive right horizontal links.
  19 */
  20
  21 static js_Property sentinel = {
  22         "",
  23         &sentinel, &sentinel,
  24         NULL, NULL,
  25         0, 0,
  26         { {0}, {0}, JS_TUNDEFINED },
  27         NULL, NULL
  28 };
  29
  30 static js_Property *newproperty(js_State *J, js_Object *obj, const char *name)
  31 {
  32         js_Property *node = js_malloc(J, sizeof *node);
  33         node->name = js_intern(J, name);
  34         node->left = node->right = &sentinel;
  35         node->prevp = NULL;
  36         node->next = NULL;
  37         node->level = 1;
  38         node->atts = 0;
  39         node->value.type = JS_TUNDEFINED;
  40         node->value.u.number = 0;
  41         node->getter = NULL;
  42         node->setter = NULL;
  43         ++obj->count;
  44         return node;
  45 }
  46
  47 static js_Property *lookup(js_Property *node, const char *name)
  48 {
  49         while (node != &sentinel) {
  50                 int c = strcmp(name, node->name);
  51                 if (c == 0)
  52                         return node;
  53                 else if (c < 0)
  54                         node = node->left;
  55                 else
  56                         node = node->right;
  57         }
  58         return NULL;
  59 }
  60
  61 static js_Property *skew(js_Property *node)
  62 {
  63         if (node->left->level == node->level) {
  64                 js_Property *temp = node;
  65                 node = node->left;
  66                 temp->left = node->right;
  67                 node->right = temp;
  68         }
  69         return node;
  70 }
  71
  72 static js_Property *split(js_Property *node)
  73 {
  74         if (node->right->right->level == node->level) {
  75                 js_Property *temp = node;
  76                 node = node->right;
  77                 temp->right = node->left;
  78                 node->left = temp;
  79                 ++node->level;
  80         }
  81         return node;
  82 }
  83
  84 static js_Property *insert(js_State *J, js_Object *obj, js_Property *node, const char *name, js_Property **result)
  85 {
  86         if (node != &sentinel) {
  87                 int c = strcmp(name, node->name);
  88                 if (c < 0)
  89                         node->left = insert(J, obj, node->left, name, result);
  90                 else if (c > 0)
  91                         node->right = insert(J, obj, node->right, name, result);
  92                 else
  93                         return *result = node;
  94                 node = skew(node);
  95                 node = split(node);
  96                 return node;
  97         }
  98         return *result = newproperty(J, obj, name);
  99 }
 100
 101 static void freeproperty(js_State *J, js_Object *obj, js_Property *node)
 102 {
 103         if (node->next)
 104                 node->next->prevp = node->prevp;
 105         else
 106                 obj->tailp = node->prevp;
 107         *node->prevp = node->next;
 108         js_free(J, node);
 109         --obj->count;
 110 }
 111
 112 static js_Property *delete(js_State *J, js_Object *obj, js_Property *node, const char *name)
 113 {
 114         js_Property *temp, *succ;
 115
 116         if (node != &sentinel) {
 117                 int c = strcmp(name, node->name);
 118                 if (c < 0) {
 119                         node->left = delete(J, obj, node->left, name);
 120                 } else if (c > 0) {
 121                         node->right = delete(J, obj, node->right, name);
 122                 } else {
 123                         if (node->left == &sentinel) {
 124                                 temp = node;
 125                                 node = node->right;
 126                                 freeproperty(J, obj, temp);
 127                         } else if (node->right == &sentinel) {
 128                                 temp = node;
 129                                 node = node->left;
 130                                 freeproperty(J, obj, temp);
 131                         } else {
 132                                 succ = node->right;
 133                                 while (succ->left != &sentinel)
 134                                         succ = succ->left;
 135                                 node->name = succ->name;
 136                                 node->atts = succ->atts;
 137                                 node->value = succ->value;
 138                                 node->right = delete(J, obj, node->right, succ->name);
 139                         }
 140                 }
 141
 142                 if (node->left->level < node->level - 1 ||
 143                         node->right->level < node->level - 1)
 144                 {
 145                         if (node->right->level > --node->level)
 146                                 node->right->level = node->level;
 147                         node = skew(node);
 148                         node->right = skew(node->right);
 149                         node->right->right = skew(node->right->right);
 150                         node = split(node);
 151                         node->right = split(node->right);
 152                 }
 153         }
 154         return node;
 155 }
 156
 157
 158 js_Object *jsV_newobject(js_State *J, enum js_Class type, js_Object *prototype)
 159 {
 160         js_Object *obj = js_malloc(J, sizeof *obj);
 161         memset(obj, 0, sizeof *obj);
 162         obj->gcmark = 0;
 163         obj->gcnext = J->gcobj;
 164         J->gcobj = obj;
 165         ++J->gccounter;
 166
 167         obj->type = type;
 168         obj->properties = &sentinel;
 169         obj->head = NULL;
 170         obj->tailp = &obj->head;
 171         obj->prototype = prototype;
 172         obj->extensible = 1;
 173         return obj;
 174 }
 175
 176 js_Property *jsV_getownproperty(js_State *J, js_Object *obj, const char *name)
 177 {
 178         return lookup(obj->properties, name);
 179 }
 180
 181 js_Property *jsV_getpropertyx(js_State *J, js_Object *obj, const char *name, int *own)
 182 {
 183         *own = 1;
 184         do {
 185                 js_Property *ref = lookup(obj->properties, name);
 186                 if (ref)
 187                         return ref;
 188                 obj = obj->prototype;
 189                 *own = 0;
 190         } while (obj);
 191         return NULL;
 192 }
 193
 194 js_Property *jsV_getproperty(js_State *J, js_Object *obj, const char *name)
 195 {
 196         do {
 197                 js_Property *ref = lookup(obj->properties, name);
 198                 if (ref)
 199                         return ref;
 200                 obj = obj->prototype;
 201         } while (obj);
 202         return NULL;
 203 }
 204
 205 js_Property *jsV_setproperty(js_State *J, js_Object *obj, const char *name)
 206 {
 207         js_Property *result;
 208
 209         if (!obj->extensible) {
 210                 result = lookup(obj->properties, name);
 211                 if (J->strict && !result)
 212                         js_typeerror(J, "object is non-extensible");
 213                 return result;
 214         }
 215
 216         obj->properties = insert(J, obj, obj->properties, name, &result);
 217         if (!result->prevp) {
 218                 result->prevp = obj->tailp;
 219                 *obj->tailp = result;
 220                 obj->tailp = &result->next;
 221         }
 222         return result;
 223 }
 224
 225 void jsV_delproperty(js_State *J, js_Object *obj, const char *name)
 226 {
 227         obj->properties = delete(J, obj, obj->properties, name);
 228 }
 229
 230 /* Flatten hierarchy of enumerable properties into an iterator object */
 231
 232 static int itshadow(js_State *J, js_Object *top, js_Object *bot, const char *name)
 233 {
 234         unsigned int k;
 235         while (top != bot) {
 236                 js_Property *prop = lookup(top->properties, name);
 237                 if (prop && !(prop->atts & JS_DONTENUM))
 238                         return 1;
 239                 if (top->type == JS_CSTRING)
 240                         if (js_isarrayindex(J, name, &k) && k < top->u.s.length)
 241                                 return 1;
 242                 top = top->prototype;
 243         }
 244         return 0;
 245 }
 246
 247 static void itwalk(js_State *J, js_Object *io, js_Object *top, int own)
 248 {
 249         js_Object *obj = top;
 250         js_Iterator *tail = NULL;
 251         char buf[32];
 252         unsigned int k;
 253
 254 #define ITADD(x) \
 255         js_Iterator *node = js_malloc(J, sizeof *node); \
 256         node->name = x; \
 257         node->next = NULL; \
 258         if (!tail) { \
 259                 io->u.iter.head = tail = node; \
 260         } else { \
 261                 tail->next = node; \
 262                 tail = node; \
 263         }
 264
 265         while (obj) {
 266                 js_Property *prop = obj->head;
 267                 while (prop) {
 268                         if (!(prop->atts & JS_DONTENUM) && !itshadow(J, top, obj, prop->name)) {
 269                                 ITADD(prop->name);
 270                         }
 271                         prop = prop->next;
 272                 }
 273
 274                 if (obj->type == JS_CSTRING) {
 275                         for (k = 0; k < obj->u.s.length; ++k) {
 276                                 js_itoa(buf, k);
 277                                 if (!itshadow(J, top, obj, buf)) {
 278                                         ITADD(js_intern(J, buf));
 279                                 }
 280                         }
 281                 }
 282
 283                 if (own)
 284                         break;
 285                 obj = obj->prototype;
 286         }
 287 }
 288
 289 js_Object *jsV_newiterator(js_State *J, js_Object *obj, int own)
 290 {
 291         js_Object *io = jsV_newobject(J, JS_CITERATOR, NULL);
 292         io->u.iter.target = obj;
 293         io->u.iter.head = NULL;
 294         itwalk(J, io, obj, own);
 295         return io;
 296 }
 297
 298 const char *jsV_nextiterator(js_State *J, js_Object *io)
 299 {
 300         unsigned int k;
 301         if (io->type != JS_CITERATOR)
 302                 js_typeerror(J, "not an iterator");
 303         while (io->u.iter.head) {
 304                 js_Iterator *next = io->u.iter.head->next;
 305                 const char *name = io->u.iter.head->name;
 306                 js_free(J, io->u.iter.head);
 307                 io->u.iter.head = next;
 308                 if (jsV_getproperty(J, io->u.iter.target, name))
 309                         return name;
 310                 if (io->u.iter.target->type == JS_CSTRING)
 311                         if (js_isarrayindex(J, name, &k) && k < io->u.iter.target->u.s.length)
 312                                 return name;
 313         }
 314         return NULL;
 315 }
 316
 317 /* Walk all the properties and delete them one by one for arrays */
 318
 319 void jsV_resizearray(js_State *J, js_Object *obj, unsigned int newlen)
 320 {
 321         char buf[32];
 322         const char *s;
 323         unsigned int k;
 324         if (newlen < obj->u.a.length) {
 325                 if (obj->u.a.length > obj->count * 2) {
 326                         js_Object *it = jsV_newiterator(J, obj, 1);
 327                         while ((s = jsV_nextiterator(J, it))) {
 328                                 k = jsV_numbertouint32(jsV_stringtonumber(J, s));
 329                                 if (k >= newlen && !strcmp(s, jsV_numbertostring(J, buf, k)))
 330                                         jsV_delproperty(J, obj, s);
 331                         }
 332                 } else {
 333                         for (k = newlen; k < obj->u.a.length; ++k) {
 334                                 jsV_delproperty(J, obj, js_itoa(buf, k));
 335                         }
 336                 }
 337         }
 338         obj->u.a.length = newlen;
 339 }