The hash table of common data structures and algorithms in the iOS standard Library

💾 KV database

For the storage of structured data, we usually use a relational database, but for the storage of key-value type data, it is not suitable to use a relational database. Therefore, iOS system also has a set of file database based on key-value storage: NDBM.

Function: a set of database based on key-value form storage.

Header file: #include

Platform: BSD Unix

Create, Open, close

Function: database file creation, open, close.

Function signature:

Dbm_open (const char *file, int open_FLAGS, mode_t file_mode); Dbm_close (DBM *db);Copy the code

Parameters:

File :[in] Specifies the file name of the database. The system automatically adds the suffix name of the.db internally when opening and creating the database, so we do not need to specify the suffix extension part.

Open_flags: [in] the file open the properties, general transfer O_RDWR | O_CREAT show that reading and writing, and there is no creation.

File_mode :[in] File access mode. The value is 0660.

Db :[in] The handle used to perform the database shutdown, which is returned by the database file opening.

Return :[out] Database handle pointer is a DBM type of data. This type is transparent to us and does not need to be addressed.

Second, add

Function: Add a key-value pair to a database. The system does not limit the contents of a key-value, but the key-value must be converted to a structure defined as follows:

typedef struct { void *dptr; // The address of the memory data size_t dsize; // The size of memory data. } datum;Copy the code

Function signature:

int dbm_store(DBM *db, datum key, datum content, int store_mode);
Copy the code

Parameters:

Db: [in] Handle to the database.

Key :[in] The content of the key part to be inserted.

Content :[in] Specifies the content of the value part to be inserted.

Store_mode :[in] Insert mode. The value can be DBM_INSERT or DBM_REPLACE. If DBM_INSERT is set to insert, the operation fails if the corresponding key exists in the database. When DBM_REPLACE is specified, add is performed if the key does not exist, and replace is performed if the corresponding key exists.

Return :[out] Returns 0 on success, 1 on insertion of an existing key, and -1 on insertion failure.

Three, delete,

Run the following command to delete a key-value pair from a database:

Function signature:

 int dbm_delete(DBM *db, datum key);

Copy the code

Parameters:

Db: [in] Handle to the database.

Key :[in] Key to delete.

Return :[out] If 0 is returned, the deletion succeeds. If 1 is returned, the specified key does not exist. If -1 is returned, other errors occur.

Fourth, the query

Run the following command to search for a value in the database based on the specified key:

Function signature:

 datum dbm_fetch(DBM *db, datum key);

Copy the code

parameter

Db :[in] Handle to the database.

Key :[in] Searches for the specified key

Return :[out] The system returns a structure datum that stores the returned value. If there is no corresponding value for the key, the DPTR value in the datum returned will be NULL. We do not need to free the returned value, nor can we modify the contents of the returned value.

5. Disk synchronization

Run the following command to synchronize the key-value saved in the memory to the disk

Header file: #include

Platform: BSD Unix

Description:

For the NDBM database, the system does not directly provide an API for synchronizing in-memory data to disk. In addition to providing NDBM, the system provides a more general file database interface, which is defined in db.h files. We can see the type of db provided by the system and the detailed definition of the database handle from the declaration of the initial file:

// Three database types :B tree, HASH table, record typedef enum {DB_BTREE, DB_HASH, DB_RECNO} DBTYPE; // Generic database handle definition. typedef struct __db { DBTYPEtype; /* int (*close)(struct __db *); Int (*del)(const struct __db *, const DBT *, unsigned int); Int (*get)(const struct __db *, const DBT *, DBT *, unsigned int); Int (*put)(const struct __db *, DBT *, const DBT *, unsigned int); Int (*seq)(const struct __db *, DBT *, DBT *, unsigned int); Int (*sync)(const struct __db *, unsigned int); Void *internal; Int (*fd)(const struct __db *); // get the file descriptor function} DB;Copy the code

The key-value library we used is actually a DB_HASH database file inside. The DBM type is also a DB type. Therefore, when we need to carry out disk synchronization, we only need to convert DBM type handle to DB type handle, and then call sync function to realize disk file synchronization. This way we can call the synchronization function directly when we need to save the memory data to disk without closing the file to achieve disk storage.

Sample code:

DBM *dbm = XXX; // Assume that DBM is a database file handle opened elsewhere. DB *db = (DB*)dbm; // Convert to DB type pointer. db->sync(db, 0); // Call this function here to implement memory data to disk synchronization processing.Copy the code

Six, traverse

Function: the system provides two traversal functions, respectively is to get the first key value in the entire database, and to get the next valid key value function.

Function signature:

// Get the first stored key. datum dbm_firstkey(DBM *db); // Get the next stored key. datum dbm_nextkey(DBM *db);Copy the code

Parameters:

Db :[in] Handle to the database

Return :[out] returns the corresponding key. If there is no key, the DPTR in the returned structure will be NULL.

Description:

You can use these two functions to iterate over the key values in the database, and then use dbM_FETCH to fetch the corresponding values. It is important to note that if an insert or delete operation is performed during a traversal, the traversal should be repeated, otherwise the result is unknown.

Sample code:

Void traversendbm(DBM * DBM) {printf("start:-------------\n");

    datum key = dbm_firstkey(dbm);
    while(key.dptr ! = NULL) { datum val = dbm_fetch(dbm, key);if(val.dptr ! = NULL) {printf("key=%s, val=%s\n",key.dptr, val.dptr);
        }
        
        key = dbm_nextkey(dbm);
    }
    
    printf("end:-------------\n");
}

void main()
{
    DBM *dbm = dbm_open("/Users/apple/testdb", O_RDWR | O_CREAT, 0660);
    
    datum key1,val1,key2,val2;
    key1.dptr = "aa";
    key1.dsize = 3;
    key2.dptr = "bb";
    key2.dsize = 3;
    val1.dptr = "vvv1";
    val1.dsize = 5;
    val2.dptr = "vvv2"; val2.dsize = 5; / / addif (dbm_store(dbm, key1, val1, DBM_INSERT) < 0)
    {
        printf ("insert error:%d\n", dbm_error(dbm));
    }
    
    if (dbm_store(dbm, key2, val2, DBM_INSERT) < 0)
    {
        printf ("insert error:%d\n", dbm_error(dbm)); } traversendbm(dbm); // replace val1.dptr ="vvv3";
    val1.dsize = 5;
    if (dbm_store(dbm, key1, val1, DBM_REPLACE) < 0)
    {
        printf ("insert error:%d\n", dbm_error(dbm)); } traversendbm(dbm); Int ret1 = dbm_delete(DBM, key1); trandbm(dbm); / / close dbm_close (DBM); }Copy the code

All additions or deletions in iOS internal implementations are not actually saved to disk files unless dbm_close is executed. So if you use the API in iOS, remember to perform database shutdown when appropriate. Of course, you can also use the disk synchronization method provided above to achieve memory to disk save processing.

Some Unix systems have a key-value length limit of 1024 while others do not.