1/* Copyright JS Foundation and other contributors, http://js.foundation
2 *
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 *     http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16#include "ecma-globals.h"
17#include "ecma-helpers.h"
18#include "ecma-property-hashmap.h"
19#include "jrt-libc-includes.h"
20#include "jcontext.h"
21
22/** \addtogroup ecma ECMA
23 * @{
24 *
25 * \addtogroup ecmapropertyhashmap Property hashmap
26 * @{
27 */
28
29#if ENABLED (JERRY_PROPRETY_HASHMAP)
30
31/**
32 * Compute the total size of the property hashmap.
33 */
34#define ECMA_PROPERTY_HASHMAP_GET_TOTAL_SIZE(max_property_count) \
35  (sizeof (ecma_property_hashmap_t) + (max_property_count * sizeof (jmem_cpointer_t)) + (max_property_count >> 3))
36
37/**
38 * Number of items in the stepping table.
39 */
40#define ECMA_PROPERTY_HASHMAP_NUMBER_OF_STEPS 8
41
42/**
43 * Stepping values for searching items in the hashmap.
44 */
45static const uint8_t ecma_property_hashmap_steps[ECMA_PROPERTY_HASHMAP_NUMBER_OF_STEPS] JERRY_ATTR_CONST_DATA =
46{
47  3, 5, 7, 11, 13, 17, 19, 23
48};
49
50/**
51 * Get the value of a bit in a bitmap.
52 */
53#define ECMA_PROPERTY_HASHMAP_GET_BIT(byte_p, index) \
54  ((byte_p)[(index) >> 3] & (1 << ((index) & 0x7)))
55
56/**
57 * Clear the value of a bit in a bitmap.
58 */
59#define ECMA_PROPERTY_HASHMAP_CLEAR_BIT(byte_p, index) \
60  ((byte_p)[(index) >> 3] = (uint8_t) ((byte_p)[(index) >> 3] & ~(1 << ((index) & 0x7))))
61
62/**
63 * Set the value of a bit in a bitmap.
64 */
65#define ECMA_PROPERTY_HASHMAP_SET_BIT(byte_p, index) \
66  ((byte_p)[(index) >> 3] = (uint8_t) ((byte_p)[(index) >> 3] | (1 << ((index) & 0x7))))
67
68/**
69 * Create a new property hashmap for the object.
70 * The object must not have a property hashmap.
71 */
72void
73ecma_property_hashmap_create (ecma_object_t *object_p) /**< object */
74{
75  if (JERRY_CONTEXT (ecma_prop_hashmap_alloc_state) != ECMA_PROP_HASHMAP_ALLOC_ON)
76  {
77    return;
78  }
79
80  jmem_cpointer_t prop_iter_cp = object_p->u1.property_list_cp;
81
82  if (prop_iter_cp == JMEM_CP_NULL)
83  {
84    return;
85  }
86
87  uint32_t named_property_count = 0;
88
89  while (prop_iter_cp != JMEM_CP_NULL)
90  {
91    ecma_property_header_t *prop_iter_p = ECMA_GET_NON_NULL_POINTER (ecma_property_header_t, prop_iter_cp);
92    JERRY_ASSERT (ECMA_PROPERTY_IS_PROPERTY_PAIR (prop_iter_p));
93
94    for (int i = 0; i < ECMA_PROPERTY_PAIR_ITEM_COUNT; i++)
95    {
96      ecma_property_types_t type = ECMA_PROPERTY_GET_TYPE (prop_iter_p->types[i]);
97
98      if (type != ECMA_PROPERTY_TYPE_SPECIAL)
99      {
100        named_property_count++;
101      }
102    }
103    prop_iter_cp = prop_iter_p->next_property_cp;
104  }
105
106  if (named_property_count < (ECMA_PROPERTY_HASMAP_MINIMUM_SIZE / 2))
107  {
108    return;
109  }
110
111  /* The max_property_count must be power of 2. */
112  uint32_t max_property_count = ECMA_PROPERTY_HASMAP_MINIMUM_SIZE;
113
114  /* At least 1/3 items must be NULL. */
115  while (max_property_count < (named_property_count + (named_property_count >> 1)))
116  {
117    max_property_count <<= 1;
118  }
119
120  size_t total_size = ECMA_PROPERTY_HASHMAP_GET_TOTAL_SIZE (max_property_count);
121
122  ecma_property_hashmap_t *hashmap_p = (ecma_property_hashmap_t *) jmem_heap_alloc_block_null_on_error (total_size);
123
124  if (hashmap_p == NULL)
125  {
126    return;
127  }
128
129  memset (hashmap_p, 0, total_size);
130
131  hashmap_p->header.types[0] = ECMA_PROPERTY_TYPE_HASHMAP;
132  hashmap_p->header.next_property_cp = object_p->u1.property_list_cp;
133  hashmap_p->max_property_count = max_property_count;
134  hashmap_p->null_count = max_property_count - named_property_count;
135  hashmap_p->unused_count = max_property_count - named_property_count;
136
137  jmem_cpointer_t *pair_list_p = (jmem_cpointer_t *) (hashmap_p + 1);
138  uint8_t *bits_p = (uint8_t *) (pair_list_p + max_property_count);
139  uint32_t mask = max_property_count - 1;
140
141  prop_iter_cp = object_p->u1.property_list_cp;
142  ECMA_SET_NON_NULL_POINTER (object_p->u1.property_list_cp, hashmap_p);
143
144  while (prop_iter_cp != JMEM_CP_NULL)
145  {
146    ecma_property_header_t *prop_iter_p = ECMA_GET_NON_NULL_POINTER (ecma_property_header_t, prop_iter_cp);
147    JERRY_ASSERT (ECMA_PROPERTY_IS_PROPERTY_PAIR (prop_iter_p));
148
149    for (int i = 0; i < ECMA_PROPERTY_PAIR_ITEM_COUNT; i++)
150    {
151      if (!ECMA_PROPERTY_IS_NAMED_PROPERTY (prop_iter_p->types[i]))
152      {
153        continue;
154      }
155
156      ecma_property_pair_t *property_pair_p = (ecma_property_pair_t *) prop_iter_p;
157
158      uint32_t entry_index = ecma_string_get_property_name_hash (prop_iter_p->types[i],
159                                                                 property_pair_p->names_cp[i]);
160      uint32_t step = ecma_property_hashmap_steps[entry_index & (ECMA_PROPERTY_HASHMAP_NUMBER_OF_STEPS - 1)];
161
162      entry_index &= mask;
163#ifndef JERRY_NDEBUG
164      /* Because max_property_count (power of 2) and step (a prime
165       * number) are relative primes, all entries of the hasmap are
166       * visited exactly once before the start entry index is reached
167       * again. Furthermore because at least one NULL is present in
168       * the hashmap, the while loop must be terminated before the
169       * the starting index is reached again. */
170      uint32_t start_entry_index = entry_index;
171#endif /* !JERRY_NDEBUG */
172
173      while (pair_list_p[entry_index] != ECMA_NULL_POINTER)
174      {
175        entry_index = (entry_index + step) & mask;
176
177#ifndef JERRY_NDEBUG
178        JERRY_ASSERT (entry_index != start_entry_index);
179#endif /* !JERRY_NDEBUG */
180      }
181
182      ECMA_SET_NON_NULL_POINTER (pair_list_p[entry_index], property_pair_p);
183
184      if (i != 0)
185      {
186        ECMA_PROPERTY_HASHMAP_SET_BIT (bits_p, entry_index);
187      }
188    }
189
190    prop_iter_cp = prop_iter_p->next_property_cp;
191  }
192} /* ecma_property_hashmap_create */
193
194/**
195 * Free the hashmap of the object.
196 * The object must have a property hashmap.
197 */
198void
199ecma_property_hashmap_free (ecma_object_t *object_p) /**< object */
200{
201  /* Property hash must be exists and must be the first property. */
202  JERRY_ASSERT (object_p->u1.property_list_cp != JMEM_CP_NULL);
203
204  ecma_property_header_t *property_p = ECMA_GET_NON_NULL_POINTER (ecma_property_header_t,
205                                                                  object_p->u1.property_list_cp);
206
207  JERRY_ASSERT (property_p->types[0] == ECMA_PROPERTY_TYPE_HASHMAP);
208
209  ecma_property_hashmap_t *hashmap_p = (ecma_property_hashmap_t *) property_p;
210
211  object_p->u1.property_list_cp = property_p->next_property_cp;
212
213  jmem_heap_free_block (hashmap_p,
214                        ECMA_PROPERTY_HASHMAP_GET_TOTAL_SIZE (hashmap_p->max_property_count));
215} /* ecma_property_hashmap_free */
216
217/**
218 * Insert named property into the hashmap.
219 */
220void
221ecma_property_hashmap_insert (ecma_object_t *object_p, /**< object */
222                              ecma_string_t *name_p, /**< name of the property */
223                              ecma_property_pair_t *property_pair_p, /**< property pair */
224                              int property_index) /**< property index in the pair (0 or 1) */
225{
226  JERRY_ASSERT (property_pair_p != NULL);
227
228  ecma_property_hashmap_t *hashmap_p = ECMA_GET_NON_NULL_POINTER (ecma_property_hashmap_t,
229                                                                  object_p->u1.property_list_cp);
230
231  JERRY_ASSERT (hashmap_p->header.types[0] == ECMA_PROPERTY_TYPE_HASHMAP);
232
233  /* The NULLs are reduced below 1/8 of the hashmap. */
234  if (hashmap_p->null_count < (hashmap_p->max_property_count >> 3))
235  {
236    ecma_property_hashmap_free (object_p);
237    ecma_property_hashmap_create (object_p);
238    return;
239  }
240
241  JERRY_ASSERT (property_index < ECMA_PROPERTY_PAIR_ITEM_COUNT);
242
243  uint32_t entry_index = ecma_string_hash (name_p);
244  uint32_t step = ecma_property_hashmap_steps[entry_index & (ECMA_PROPERTY_HASHMAP_NUMBER_OF_STEPS - 1)];
245  uint32_t mask = hashmap_p->max_property_count - 1;
246  entry_index &= mask;
247
248#ifndef JERRY_NDEBUG
249  /* See the comment for this variable in ecma_property_hashmap_create. */
250  uint32_t start_entry_index = entry_index;
251#endif /* !JERRY_NDEBUG */
252
253  jmem_cpointer_t *pair_list_p = (jmem_cpointer_t *) (hashmap_p + 1);
254
255  while (pair_list_p[entry_index] != ECMA_NULL_POINTER)
256  {
257    entry_index = (entry_index + step) & mask;
258
259#ifndef JERRY_NDEBUG
260    JERRY_ASSERT (entry_index != start_entry_index);
261#endif /* !JERRY_NDEBUG */
262  }
263
264  ECMA_SET_NON_NULL_POINTER (pair_list_p[entry_index], property_pair_p);
265
266  uint8_t *bits_p = (uint8_t *) (pair_list_p + hashmap_p->max_property_count);
267  bits_p += (entry_index >> 3);
268  mask = (uint32_t) (1 << (entry_index & 0x7));
269
270  if (!(*bits_p & mask))
271  {
272    /* Deleted entries also has ECMA_NULL_POINTER
273     * value, but they are not NULL values. */
274    hashmap_p->null_count--;
275    JERRY_ASSERT (hashmap_p->null_count > 0);
276  }
277
278  hashmap_p->unused_count--;
279  JERRY_ASSERT (hashmap_p->unused_count > 0);
280
281  if (property_index == 0)
282  {
283    *bits_p = (uint8_t) ((*bits_p) & ~mask);
284  }
285  else
286  {
287    *bits_p = (uint8_t) ((*bits_p) | mask);
288  }
289} /* ecma_property_hashmap_insert */
290
291/**
292 * Delete named property from the hashmap.
293 *
294 * @return ECMA_PROPERTY_HASHMAP_DELETE_RECREATE_HASHMAP if hashmap should be recreated
295 *         ECMA_PROPERTY_HASHMAP_DELETE_HAS_HASHMAP otherwise
296 */
297ecma_property_hashmap_delete_status
298ecma_property_hashmap_delete (ecma_object_t *object_p, /**< object */
299                              jmem_cpointer_t name_cp, /**< property name */
300                              ecma_property_t *property_p) /**< property */
301{
302  ecma_property_hashmap_t *hashmap_p = ECMA_GET_NON_NULL_POINTER (ecma_property_hashmap_t,
303                                                                  object_p->u1.property_list_cp);
304
305  JERRY_ASSERT (hashmap_p->header.types[0] == ECMA_PROPERTY_TYPE_HASHMAP);
306
307  hashmap_p->unused_count++;
308
309  /* The NULLs are above 3/4 of the hashmap. */
310  if (hashmap_p->unused_count > ((hashmap_p->max_property_count * 3) >> 2))
311  {
312    return ECMA_PROPERTY_HASHMAP_DELETE_RECREATE_HASHMAP;
313  }
314
315  uint32_t entry_index = ecma_string_get_property_name_hash (*property_p, name_cp);
316  uint32_t step = ecma_property_hashmap_steps[entry_index & (ECMA_PROPERTY_HASHMAP_NUMBER_OF_STEPS - 1)];
317  uint32_t mask = hashmap_p->max_property_count - 1;
318  jmem_cpointer_t *pair_list_p = (jmem_cpointer_t *) (hashmap_p + 1);
319  uint8_t *bits_p = (uint8_t *) (pair_list_p + hashmap_p->max_property_count);
320
321  entry_index &= mask;
322
323#ifndef JERRY_NDEBUG
324  /* See the comment for this variable in ecma_property_hashmap_create. */
325  uint32_t start_entry_index = entry_index;
326#endif /* !JERRY_NDEBUG */
327
328  while (true)
329  {
330    if (pair_list_p[entry_index] != ECMA_NULL_POINTER)
331    {
332      size_t offset = 0;
333
334      if (ECMA_PROPERTY_HASHMAP_GET_BIT (bits_p, entry_index))
335      {
336        offset = 1;
337      }
338
339      ecma_property_pair_t *property_pair_p = ECMA_GET_NON_NULL_POINTER (ecma_property_pair_t,
340                                                                         pair_list_p[entry_index]);
341
342      if ((property_pair_p->header.types + offset) == property_p)
343      {
344        JERRY_ASSERT (property_pair_p->names_cp[offset] == name_cp);
345
346        pair_list_p[entry_index] = ECMA_NULL_POINTER;
347        ECMA_PROPERTY_HASHMAP_SET_BIT (bits_p, entry_index);
348        return ECMA_PROPERTY_HASHMAP_DELETE_HAS_HASHMAP;
349      }
350    }
351    else
352    {
353      /* Must be a deleted entry. */
354      JERRY_ASSERT (ECMA_PROPERTY_HASHMAP_GET_BIT (bits_p, entry_index));
355    }
356
357    entry_index = (entry_index + step) & mask;
358
359#ifndef JERRY_NDEBUG
360    JERRY_ASSERT (entry_index != start_entry_index);
361#endif /* !JERRY_NDEBUG */
362  }
363} /* ecma_property_hashmap_delete */
364
365/**
366 * Find a named property.
367 *
368 * @return pointer to the property if found or NULL otherwise
369 */
370ecma_property_t *
371ecma_property_hashmap_find (ecma_property_hashmap_t *hashmap_p, /**< hashmap */
372                            ecma_string_t *name_p, /**< property name */
373                            jmem_cpointer_t *property_real_name_cp) /**< [out] property real name */
374{
375#ifndef JERRY_NDEBUG
376  /* A sanity check in debug mode: a named property must be present
377   * in both the property hashmap and in the property chain, or missing
378   * from both data collection. The following code checks the property
379   * chain, and sets the property_found variable. */
380  bool property_found = false;
381
382  jmem_cpointer_t prop_iter_cp = hashmap_p->header.next_property_cp;
383
384  while (prop_iter_cp != JMEM_CP_NULL && !property_found)
385  {
386    ecma_property_header_t *prop_iter_p = ECMA_GET_NON_NULL_POINTER (ecma_property_header_t, prop_iter_cp);
387    JERRY_ASSERT (ECMA_PROPERTY_IS_PROPERTY_PAIR (prop_iter_p));
388
389    ecma_property_pair_t *prop_pair_p = (ecma_property_pair_t *) prop_iter_p;
390
391    for (int i = 0; i < ECMA_PROPERTY_PAIR_ITEM_COUNT; i++)
392    {
393      if (ECMA_PROPERTY_IS_NAMED_PROPERTY (prop_iter_p->types[i]))
394      {
395        if (ecma_string_compare_to_property_name (prop_iter_p->types[i],
396                                                  prop_pair_p->names_cp[i],
397                                                  name_p))
398        {
399          /* Property is found */
400          property_found = true;
401          break;
402        }
403      }
404    }
405
406    prop_iter_cp = prop_iter_p->next_property_cp;
407  }
408#endif /* !JERRY_NDEBUG */
409
410  uint32_t entry_index = ecma_string_hash (name_p);
411  uint32_t step = ecma_property_hashmap_steps[entry_index & (ECMA_PROPERTY_HASHMAP_NUMBER_OF_STEPS - 1)];
412  uint32_t mask = hashmap_p->max_property_count - 1;
413  jmem_cpointer_t *pair_list_p = (jmem_cpointer_t *) (hashmap_p + 1);
414  uint8_t *bits_p = (uint8_t *) (pair_list_p + hashmap_p->max_property_count);
415  entry_index &= mask;
416
417#ifndef JERRY_NDEBUG
418  /* See the comment for this variable in ecma_property_hashmap_create. */
419  uint32_t start_entry_index = entry_index;
420#endif /* !JERRY_NDEBUG */
421
422  if (ECMA_IS_DIRECT_STRING (name_p))
423  {
424    ecma_property_t prop_name_type = (ecma_property_t) ECMA_GET_DIRECT_STRING_TYPE (name_p);
425    jmem_cpointer_t property_name_cp = (jmem_cpointer_t) ECMA_GET_DIRECT_STRING_VALUE (name_p);
426
427    JERRY_ASSERT (prop_name_type > 0);
428
429    while (true)
430    {
431      if (pair_list_p[entry_index] != ECMA_NULL_POINTER)
432      {
433        size_t offset = 0;
434        if (ECMA_PROPERTY_HASHMAP_GET_BIT (bits_p, entry_index))
435        {
436          offset = 1;
437        }
438
439        ecma_property_pair_t *property_pair_p = ECMA_GET_NON_NULL_POINTER (ecma_property_pair_t,
440                                                                           pair_list_p[entry_index]);
441
442        ecma_property_t *property_p = property_pair_p->header.types + offset;
443
444        JERRY_ASSERT (ECMA_PROPERTY_IS_NAMED_PROPERTY (*property_p));
445
446        if (property_pair_p->names_cp[offset] == property_name_cp
447            && ECMA_PROPERTY_GET_NAME_TYPE (*property_p) == prop_name_type)
448        {
449#ifndef JERRY_NDEBUG
450          JERRY_ASSERT (property_found);
451#endif /* !JERRY_NDEBUG */
452
453          *property_real_name_cp = property_name_cp;
454          return property_p;
455        }
456      }
457      else
458      {
459        if (!ECMA_PROPERTY_HASHMAP_GET_BIT (bits_p, entry_index))
460        {
461#ifndef JERRY_NDEBUG
462          JERRY_ASSERT (!property_found);
463#endif /* !JERRY_NDEBUG */
464
465          return NULL;
466        }
467        /* Otherwise it is a deleted entry. */
468      }
469
470      entry_index = (entry_index + step) & mask;
471
472#ifndef JERRY_NDEBUG
473      JERRY_ASSERT (entry_index != start_entry_index);
474#endif /* !JERRY_NDEBUG */
475    }
476  }
477
478  while (true)
479  {
480    if (pair_list_p[entry_index] != ECMA_NULL_POINTER)
481    {
482      size_t offset = 0;
483      if (ECMA_PROPERTY_HASHMAP_GET_BIT (bits_p, entry_index))
484      {
485        offset = 1;
486      }
487
488      ecma_property_pair_t *property_pair_p = ECMA_GET_NON_NULL_POINTER (ecma_property_pair_t,
489                                                                         pair_list_p[entry_index]);
490
491      ecma_property_t *property_p = property_pair_p->header.types + offset;
492
493      JERRY_ASSERT (ECMA_PROPERTY_IS_NAMED_PROPERTY (*property_p));
494
495      if (ECMA_PROPERTY_GET_NAME_TYPE (*property_p) == ECMA_DIRECT_STRING_PTR)
496      {
497        ecma_string_t *prop_name_p = ECMA_GET_NON_NULL_POINTER (ecma_string_t, property_pair_p->names_cp[offset]);
498
499        if (ecma_compare_ecma_non_direct_strings (prop_name_p, name_p))
500        {
501#ifndef JERRY_NDEBUG
502          JERRY_ASSERT (property_found);
503#endif /* !JERRY_NDEBUG */
504
505          *property_real_name_cp = property_pair_p->names_cp[offset];
506          return property_p;
507        }
508      }
509    }
510    else
511    {
512      if (!ECMA_PROPERTY_HASHMAP_GET_BIT (bits_p, entry_index))
513      {
514#ifndef JERRY_NDEBUG
515        JERRY_ASSERT (!property_found);
516#endif /* !JERRY_NDEBUG */
517
518        return NULL;
519      }
520      /* Otherwise it is a deleted entry. */
521    }
522
523    entry_index = (entry_index + step) & mask;
524
525#ifndef JERRY_NDEBUG
526    JERRY_ASSERT (entry_index != start_entry_index);
527#endif /* !JERRY_NDEBUG */
528  }
529} /* ecma_property_hashmap_find */
530#endif /* ENABLED (JERRY_PROPRETY_HASHMAP) */
531
532/**
533 * @}
534 * @}
535 */
536