Common data structures and algorithms in the iOS standard Library memory pool

📝 Cache Cache

Cache is a form of key-value pair for data storage and retrieval, internal implementation of hash table. Some of the cached key/value pairs are released when the system is under memory stress. IOS provides an advanced cache library NSCache based on OC and a cache library libcache.dylib based on C. NSCache is an advanced class library based on libcache.dylib, and both libraries are thread safe. This paper mainly introduces the VARIOUS API functions of the cache library based on C language.

Header file: #include

, #include < cache_callback. h> Platform: iOS

Create and close the cache object

Function: Create or destroy a cache object. Function signature:

int cache_create(const char *name, cache_attributes_t *attrs, cache_t **cache_out);
int cache_destroy(cache_t *cache);
Copy the code

Parameter: name:[in] Specifies the name of the string used to create the cache. It cannot be empty. Attrs: [in] Sets attributes for the cache. It cannot be empty. Cache_out: [out] Returns the cache object created. Return: [out] Returns 0 on success, otherwise returns a non-0 description: Cache object is a container object, the cached content is a key/value pair, as for the key/value pair is what type of data, how to control the life cycle of key/value pair data, how to determine the two key is the same key, etc. The information cache object itself is not clear, so we need to clear tell the cache object how to operate these key information. This is why you need to specify properties when creating the cache object. The parameter type of the attribute is a cache_Attributes_t structure. Most of the data members of this structure are function Pointers, which are used to implement various strategies for manipulating key values.

struct cache_attributes_s { uint32_t version; Cache_key_hash_cb_t key_hash_cb; // Execute on the keyhashCache_key_is_equal_cb_t key_is_equal_cb; Cache_key_retain_cb_t key_retain_cb; cache_key_retain_cb; // Called when a key is added to the cache to increase the reference count of the key or to make a memory copy. cache_release_cb_t key_release_cb; // Key release handler function, used for key memory management use. cache_release_cb_t value_release_cb; // The value release handler is used for memory management of the value. cache_value_make_nonpurgeable_cb_t value_make_nonpurgeable_cb; // Performs a non-purgeable handler on the value memory when its reference count changes from 0 to 1. cache_value_make_purgeable_cb_t value_make_purgeable_cb; // Purgeable handler for a value when its reference count goes to 0. This function is used to automatically free allocated memory when memory becomes tight. void *user_data; // Attach data to all of these callbacks. // AddedinCACHE_ATTRIBUTES_VERSION_2 cache_value_retain_cb_t value_retain_cb; // value a function that increases the reference count for memory management use of the value. }; typedef struct cache_attributes_s cache_attributes_t;Copy the code

The format of each of the above callbacks is clearly defined in cache.h, so it is not covered here. We usually use strings or integers as keys, so when you use strings or integers as keys, there is a set of default implementation functions that cache object attributes. These functions are declared in the cache_callbacks.h file

CACHE_PUBLIC_API Uintptr_t cache_key_hash_cb_cstring(void *key,  void *unused); CACHE_PUBLIC_API uintptr_t cache_key_hash_cb_integer(void *key, void *unused); CACHE_PUBLIC_API bool cache_key_is_equal_cb_cstring(void *key1, void *key2, void *unused); CACHE_PUBLIC_API bool cache_key_is_equal_cb_integer(void *key1, void *key2, void *unused); By default, this function calls the free function, so if this function is used for free processing, the key will need to be allocated from the heap. CACHE_PUBLIC_API void cache_release_cb_free(void *key_or_value, void *unused); // A preset function that purgeable the value. CACHE_PUBLIC_API void cache_value_make_purgeable_cb(void *value, void *unused); CACHE_PUBLIC_API bool cache_value_make_nonpurgeable_cb(void *value, void *unused);Copy the code

Sample code:

// The following code is used to create a string key cache object in which the member functions in the attributes of the cache object take the default predefined functions.#include <cache.h>
 #include <cache_callbcaks.h>

 cache_t *im_cache;
 cache_attributes_t attrs = {
         .version = CACHE_ATTRIBUTES_VERSION_2,
         .key_hash_cb = cache_key_hash_cb_cstring,
         .key_is_equal_cb = cache_key_is_equal_cb_cstring,
         .key_retain_cb = my_copy_string,
         .key_release_cb = cache_release_cb_free,
         .value_release_cb = cache_release_cb_free,
  };
  cache_create("com.acme.im_cache", &attrs, &im_cache);
Copy the code

Setting, obtaining and deleting key-value pairs in the cache object

Function: Handles adding, fetching, and deleting key-value pairs from the cache. Function signature:

// Add the key-value pair to the cache, or replace the original key-value pair. int cache_set_and_retain(cache_t *cache, void *key, void *value, size_t cost); Int cache_get_and_retain(cache_t *cache, void *key, void **value_out); int cache_get_and_retain(cache_t *cache, void *key, void **value_out); // The value reference count in the cache is reduced by 1. When the reference count is 0, the memory allocated by the value is cleaned up or destroyed. int cache_release_value(cache_t *cache, void *value); // Remove the key from the cache. int cache_remove(cache_t *cache, void *key);Copy the code

Parameter: cache:[in] Cache object. Key :[in] Key for adding or getting or deleting. Cost :[in] The cost of adding the cache. The larger the value, the longer the key stays in the cache. Value :[in] Added value. Value_out: [out] is used for the output when the value is obtained.

Description:

1. The cache_set_and_retain function is used to put the key-value pair into the cache and specify the cost value. When a key is added to the cache, the memory of the key is managed by calling key_retain_cb in the cache_Attributes_t structure. If this function is set to NULL, we are responsible for the lifetime management of the key. Since the cache object is internally stored and retrieved through hash tables, the key-value pair needs to be added to the cache with the property functions key_hash_cb, key_is_equal_cb for key-hash calculation and comparison. For values, the reference count is set to 1 when the value is added to the cache. If we want to handle the memory storage of the value in the cache, we need to specify value_reTAIN_cb in the cache attribute to do this. Values added to the cache can be NULL. The final cost parameter is used to specify the cost value of the key-value pair, and the smaller the value, the less time it will remain in the cache, and vice versa.

2. The cache_get_and_retain function is used to retrieve a value by key. Value_out returns NULL if the corresponding key-value pair is not stored in the cache, is discarded, or the memory allocated for the value is cleared, and the special value ENOENT is returned. The cache object increments its reference count each time a value is fetched. Therefore, when we no longer need to access the returned value, we need to call the manual cache_release_value function to reduce the reference count of the value in the cache object. When the reference count of a value goes to 0, the memory allocated for the value is purgeable or destroyed.

3. The cache_remove function is used to remove key-value pairs from the cache. When deleting key-value pairs from the cache, the cache object calls the key_RELEase_cb function in the property structure for memory destruction of the key and value_RELEase_cb function for memory destruction of the value if the reference count of the value becomes zero.

Sample code:

#include <cache.h>
#include <cache_callbacks.h>

void main() { cache_attributes_t attr; attr.key_hash_cb = cache_key_hash_cb_cstring; attr.key_is_equal_cb = cache_key_is_equal_cb_cstring; attr.key_retain_cb = NULL; attr.key_release_cb = cache_release_cb_free; attr.version = CACHE_ATTRIBUTES_VERSION_2; attr.user_data = NULL; attr.value_retain_cb = NULL; attr.value_release_cb = cache_release_cb_free; attr.value_make_purgeable_cb = cache_value_make_purgeable_cb; attr.value_make_nonpurgeable_cb = cache_value_make_nonpurgeable_cb; Cache_t *cache = NULL; int ret = cache_create("com.test", &attr, &cache); Char *key = malloc(4); strcpy(key,"key");
    char *val = malloc(4);
    strcpy(val, "val"); ret = cache_set_and_retain(cache, key, val, 0); ret = cache_release_value(cache, val); // Get the key-value pair and release it after use. char *val2 = NULL; ret = cache_get_and_retain(cache, key, (void**)&val2); ret = cache_release_value(cache, val2); Cache_remove (cache, key); // Destroy the cache. cache_destroy(cache); }Copy the code

3. Key/value pair cleaning strategy and value access strategy in cache

Depending on current memory usage and other scenarios, the cache will discard key/value pairs stored in it. A cost value is also specified when you call cache_set_and_retain to add the key-value pair to the cache; larger values are less likely to be discarded. As explained in the introduction above, caches manage reference counts for values in key-value pairs. The value reference count is set to 1 when cache_set_and_retain is called, and the value is increased if the key-value pair is in the cache when cache_get_and_retain is called to retrieve the value. Instead of accessing and manipulating values, we need to call cache_release_value to decrease the reference count by one. The following happens immediately or later when the reference count of a value goes to zero:

1. If we set value_make_purGEABLE_cb in the property structure of the cache, this function is called to indicate that the value can be cleaned. To be cleared means that the physical memory allocated for a value can be reclaimed at any time. Therefore, when a value is set to cleanable, it cannot continue to access the memory allocated by the value directly.
2. If the key-value pair has been removed from the cache before because of a call to cache_remove, value_release_cb in the property structure is called to perform the destruction of value memory.
3. If a key-value pair in the cache needs to be discarded due to system memory stress, the key-value pair with a value reference count of 0 is discarded! Note: The cache is only discarded if the value reference count is 0.

Each access to a value in the cache needs to be performed using the cache_get_and_retain function. When cache_get_and_retain is called, the following happens:

1. Determines whether the current key-value pair is in the cache, and returns NULL if it is not.
2. If the key-value pair is in the cache. If value_make_nonPURGEABLE_cb exists in the structure property of the cache, value_make_nonPURGEable_cb is called to make the memory of the value uncleanable. If the value is set to uncleanable and returns false, the memory for the value has been cleaned, the key-value pair is discarded from the cache, and the cache_get_and_retain function returns NULL. Of course this does not happen if value_make_nonPURGEABLE_cb is empty.
3. Add value to reference count and return value.

---

Welcome to ouyang Big Brother 2013Making the addressandJane’s address book