Author: liuxin, senior engineer at huawei
Container classes, as the name implies, are storage classes that store elements of various data types and have a set of methods for handling data elements. In ark development framework, container classes are implemented in a statically like language and provided externally through NAPI framework. By limiting storage locations and attributes, each type of data can complete its own functions and cut off redundant branches, ensuring efficient data access and improving application performance. In this issue, we will introduce you to the various types of container classes in the Ark development framework and the use of related apis.
Introduction to container API
In ark development framework, there are 14 types of linear and nonlinear containers, each of which has its own characteristics and application scenarios. Here, we’ll tell you all about it.
1. Linear container classes
The bottom layer of linear container class is mainly realized through arrays, including ArrayList, Vector, List, LinkedList, Deque, Queue and Stack. Linear container API, fully consider the speed of data access, realize the Runtime can be added, deleted, changed and checked by a single command.
1. ArrayList
An ArrayList is a dynamic array that can be used to construct a global array object. Based on the generic definition, ArrayList requires that the storage location is a contiguous piece of memory with an initial capacity of 10 and dynamic expansion. Each expansion is 1.5 times the original capacity. ArrayList adds, deletes, changes, and searches the following apis:
2. Vector
A Vector is a contiguous storage structure that can be used to construct array objects globally. Vector is defined by generics to be a contiguous area of memory with an initial size of 10. It supports dynamic scaling up to twice its original size.
Because Vector expands faster than ArrayList, it is suitable for scenarios where data is frequently added. In addition to operator access, Vector also adds get/ SET interfaces to provide a more complete verification and fault tolerance mechanism to meet users’ requirements in different scenarios. Vector provides the following apis for adding, deleting, modifying, and querying operations:
3. List
List can be used to construct a one-way linked List object that can only be accessed from the head node to the tail node. By generic definition, lists can be stored discontiguously in memory.
You can modify the stored elements through interfaces such as GET /set. Apis for adding, deleting, modifying, and querying a List are as follows:
4. LinkedList
LinkedList can be used to construct a bidirectional LinkedList object that traverses the List forward or backward on a node. LinkedList can be stored discontiguously in memory by generic definition.
You can modify stored elements through get/set and other interfaces. Apis for adding, deleting, modifying, and searching LinkedList are as follows:
5. Queue
A Queue can be used to construct Queue objects, storing elements on a first-in, first-out basis. According to the generic definition, the storage location of Queue is a contiguous piece of memory, the initial capacity is 8, and dynamic capacity expansion is supported. Each capacity expansion is twice the original capacity. The bottom layer of Queue is realized by circular Queue, and the operation efficiency of Queue entry and Queue exit is relatively high. The apis for adding, deleting, modifying, and querying a Queue are as follows:
6. Deque
A Deque can be used to construct a two-endian queue object, where the storage elements follow a first-in, first-out rule, and the two-endian queue can be accessed from the head or the tail, respectively. According to the generic definition, the storage location of a Deque is required to be a contiguous piece of memory space. Its initial capacity is 8 and dynamic capacity expansion is supported. Each capacity expansion is twice the original capacity. The bottom layer of Deque adopts circular queue to achieve high operation efficiency of queue entry and queue exit. The API for adding, deleting, modifying, and querying Deque is as follows:
7. Stack
A Stack can be used to construct Stack objects, storing elements on a last-in, first-out basis. Stack According to the generic definition, the storage space must be a contiguous piece of memory, the initial capacity is 8, and dynamic capacity expansion is supported. Each capacity expansion is 1.5 times the original capacity. The bottom layer of Stack is implemented based on an array, and the operation of loading and unloading the Stack is performed at one end of the array. The related APIS of Stack adding, deleting, changing and checking are as follows:
2. Nonlinear container classes
The bottom layer of nonlinear container class is implemented through hash or red-black tree, including HashMap, HashSet, TreeMap, TreeSet, LightWeightMap, LightWeightSet, and PlainArray. The key and value types in nonlinear container classes meet ECMA standards.
1. HashMap
A HashMap can be used to store a collection of key-value pairs that have associative relationships. The store element contains a unique key, and each key corresponds to a value. A HashMap is defined by a generic definition, in which the hash value of a key is used to determine where it is stored to quickly find key-value pairs. The initial capacity of a HashMap is 16, and dynamic capacity expansion is supported. Each capacity expansion is twice the original capacity. The underlying implementation of HashMap is based on HashTable, and the conflict policy adopts the chain address method. Add, delete, modify, and query HashMap apis are as follows:
2. HashSet
A HashSet can be used to store a collection of values, of which value is unique. By generic definition. The hash value of a value is used to determine the storage location of the value in the collection, so that the value can be quickly found. The initial capacity of a HashSet is 16. Dynamic capacity expansion is supported. Each capacity expansion is twice the original capacity. The value type must meet the REQUIREMENTS of the ECMA standard. The underlying implementation of HashSet is based on HashTable, and the conflict policy adopts the chain address method. Add, delete, modify, query HashSet
3. TreeMap
TreeMap can be used to store a set of associated key-value pairs. The key is unique in the storage element, and each key corresponds to a value. TreeMap According to the generic definition, the key values in the set are ordered. The bottom layer of TreeMap is a binary tree, which can be used to quickly find the key-value pairs. The type of the key meets the requirements of the ECMA standard. The key values in TreeMap are stored in order. TreeMap is implemented based on red-black trees and can be quickly inserted and deleted. TreeMap provides the following apis for adding, deleting, modifying, and querying data:
TreeSet can be used to store a collection of values, of which value is unique. TreeSet according to the generic definition, the values in the set are ordered. The bottom layer of TreeSet is a binary tree, and the value can be quickly found through the binary search of the tree. The value type meets the requirements of ECMA standard. Values in TreeSet are stored in order. TreeSet’s underlying implementation is based on red-black trees, allowing for quick inserts and deletions. TreeSet adds, deletes, modifies, and searches the following apis:
5. LightWeightMap
The LigthWeightMap can be used to store a set of key-value pairs that are associated with each other. The key is unique and each key corresponds to a value. The LigthWeightMap adopts a more lightweight structure based on the generic definition. The key lookup in the collection depends on the hash value and binary lookup algorithm. The hash value is stored in one array and then mapped to the key value and value value in other arrays.
The default capacity is 8. Each capacity expansion is twice the original capacity. The LigthWeightMap is implemented with hash as the underlying unique identifier key. The conflict strategy is linear detection and the search strategy is based on binary search. The LigthWeightMap API for add, delete, change, and query operations is as follows:
6. LightWeightSet
The LigthWeightSet can be used to store a collection of values, of which value is unique. LigthWeightSet is a more lightweight structure based on the generic definition, with an initial default capacity of 8 and each expansion capacity of twice the original capacity. The search for values in the collection relies on hash and binary search algorithms. Hash values are stored in one array and then mapped to values in other arrays whose types meet the requirements of the ECMA standard.
The underlying identity unique value of LigthWeightSet is implemented based on hash, and its conflict strategy is linear detection and search strategy is based on binary search. The LigthWeightSet API for add, delete, change, and query is as follows:
7. PlainArray
PlainArray can be used to store collections of key-value pairs that have associated relationships, where the key is unique, and for PlainArray, its key is of type number. Each key corresponds to a value. The type is defined by generics. PlainArray has a more lightweight structure.
The default capacity is 16. Each capacity expansion is twice the original capacity. PlainArray’s search strategy is based on binary search. PlainArray provides the following apis for add, delete, change, and query operations:
Implementation of container class
We will use ArrayList as an example to introduce the implementation of container classes. It includes initialization of container classes, interface invocation of container classes, construction of container class object model, and interceptor handling.
1. Initialize the container class
In the Ark development framework, container classes are provided to the outer layer through the unified framework of NAPI. Next, we’ll use ArrayList as an example to show you how to load a container class based on NAPI. The following figure shows the container class initialization process. During the NAPI loading process, the corresponding container class will be loaded through the arkprivate. Load interface. ArrayList initializes Constructor and Prototype in the engine and returns the container class to the application side for use.
Figure 1 Container class initialization process
2. Container class interface call
In the ark development framework, the call process of container API is shown in Figure 2. Users first enter the engine through New ArrayList to get the corresponding ArrayList object, and then add elements to the object through the Add interface, which will eventually be added to the memory space bound to the ArrayList. Elements can be retrieved using the [] operator, and in the case of container classes, the engine returns the value by directly accessing the element location via a fast path.
Figure 2. Call flow of container class API
3. Container class object model
In the ark development framework, the process of constructing the container-class object model is shown in the figure below. It is forbidden to add Properties Properties to objects at runtime, and ArrayList borrokes elements from the object model to store elements.
Figure 3. Construction flow of container class object model
The Length is the number of elements in the array. The Capatity array can be obtained by the Length of elements.
Capacity expansion policy: ArrayList – > 1.5 times
Initial allocated capacity: ArrayList -> 10
(Note: implementation in TS, capacity expansion policy and initial capacity allocation are not aware)
4. Interceptor processing
Interceptor handling means maintaining an efficient container-like object at Runtime by disabling operations that affect the object’s behavior, such as DELETE and setPrototype. As shown in Figure 4, using ArrayList as an example, The internal intercepted operations of ArkCompiler mainly involve DeleteProperty, DefineProperty, GetProperty, SetPrototype, GetOwnPropertyKeys, HasProperty and other operations to restrict the holy addition of array Add, and change attributes to ensure that JSArray does not have to do holy, writable, and other necessary operations.
Figure 4. The interceptor handles ****
Use of container API
Through the introduction above, I believe you have a deep understanding of the container class. So, how do we use the container class API? This article lists typical container usage examples, including importing modules, adding elements, accessing elements, and modifying them:
// ArrayListimport ArrayList from '@ohos.util.ArrayList' let ArrayList = new ArrayList(); arrayList.add("a"); arrayList.add(1); Print (arrayList[0]); ArrayList [0] = one"; Print (arrayList[0]); Vectorimport Vector from '@ohos.util.Vector' let Vector = new Vector(); vector.add("a"); let b = [1, 2, 3]; vector.add(b); vector.add(false); Print (vector[0]); Print (vector.getFirstElement()); // Dequeimport Deque from '@ohos.util.Deque' // import Deque module let Deque = new Deque; deque.insertFront("a"); deque.insertFront(1); Print (deque[0]); // Access element deque[0] = "one"; Print (deque[0]); // Stackimport Stack from '@ohos.util.Stack' // let Stack = new Stack(); stack.push("a"); stack.push(1); Print (stack[0]); // Access the element stack.pop(); Print (stack.length); // Listimport List from '@ohos.util.List' let List = new List; list.add("a"); list.add(1); let b = [1, 2, 3]; list.add(b); Print (list[0]); Print (list.get(0)); // Import HashMap from '@ohos.util.hashmap' // Import HashMap module let HashMap = new HashMap(); hashMap.set("a", 123); hashMap.set(4, 123); Print (hashmap.haskey (4)); Print (hashmap.get ("a")); TreeMapimport TreeMap from '@ohos.util.TreeMap' let TreeMap = new TreeMap(); treeMap.set("a", 123); treeMap.set("6", 356); Print (treemap.get ("a")); Print (treemap.getFirstKey ("a")); Print (treemap.getlastKey ("a")); LightWeightMap Import LightWeightMap from '@ohos.util.LightWeightMap' LightWeightMapimport LightWeightMap from '@ohos.util.LightWeightMap' LightWeightMapimport LightWeightMap from '@ohos.util.LightWeightMap' LightWeightMapimport LightWeightMap = new LightWeightMap(); lightWeightMap.set("x", 123); lightWeightMap.set("8", 356); Print (lightweightmap.get ("a")); Print (lightweightmap.get ("x")); / print/access elements (lightWeightMap getIndexOfKey (" 8 ")); PlainArrayimport PlainArray from '@ohos.util.PlainArray' let PlainArray = new PlainArray(); plainArray.add(1, "sdd"); plainArray.add(2, "sff"); Print (plainarray.get (1)); Print (plainarray.getKeyat (1)); // Access elementsCopy the codeSo far, that’s all for this issue. We look forward to developers developing more high-performance applications through the container class of ark development framework.