This is the 7th day of my participation in the August Text Challenge.More challenges in August

Introduce the dictionary implementation in TBOX and GLIB.

Tbox

dictionary

Implementation method:

/// the dictionary item type
typedef struct __tb_oc_dictionary_item_t
{
    /// the key
    tb_char_t const*    key;
​
    /// the value
    tb_object_ref_t     val;
​
}tb_oc_dictionary_item_t;
​
// the dictionary type
typedef struct __tb_oc_dictionary_t
{
    // the object base
    tb_object_t         base;
​
    // the capacity size
    tb_size_t           size;
​
    // the object hash
    tb_hash_map_ref_t   hash;
​
    // increase refn?
    tb_bool_t           incr;
​
}tb_oc_dictionary_t;
​
​
Copy the code

Usage scenarios

  • To create a dictionary, use thetb_oc_dictionary_init().
  • Returns the dictionary size, usingtb_oc_dictionary_size()
  • Set the reference to usetb_oc_dictionary_incr()
  • Create an iterator usingtb_oc_dictionary_itor();
  • Insert keys and values usingtb_oc_dictionary_insert() 。
  • To find the value corresponding to a given key, use thetb_oc_dictionary_value ().
  • To delete keys and values, use thetb_oc_dictionary_remove ().

Glib

Hash Tables

GHashTable provides associations between keys and values optimized to find, insert, or remove associated values in apportionment O (1). All operations through each element take O (n) time (listing all keys/values, table resizing, and so on).

Implementation method:

struct _GHashTable { gsize size; gint mod; guint mask; gint nnodes; gint noccupied; /* nnodes + tombstones */ guint have_big_keys : 1; guint have_big_values : 1; gpointer keys; guint *hashes; gpointer values; GHashFunc hash_func; GEqualFunc key_equal_func; gatomicrefcount ref_count; #ifndef G_DISABLE_ASSERT /* * Tracks the structure of the hash table, not its contents: is only * incremented when a node is added or removed (is not incremented * when the key or data of a node is modified).  */ int version; #endif GDestroyNotify key_destroy_func; GDestroyNotify value_destroy_func; }; typedef struct { GHashTable *hash_table; gpointer dummy1; gpointer dummy2; gint position; gboolean dummy3; gint version; } RealIter; typedef struct _GHashTable GHashTable; typedef gboolean (*GHRFunc) (gpointer key, gpointer value, gpointer user_data); typedef struct _GHashTableIter GHashTableIter; struct _GHashTableIter { /*< private >*/ gpointer dummy1; gpointer dummy2; gpointer dummy3; int dummy4; gboolean dummy5; gpointer dummy6; };Copy the code

Usage scenarios

  • To create aGHashTable, the use ofg_hash_table_new () 。
  • If you want toGHashTableTo insert keys and values, useg_hash_table_insert () 。
  • To find the value corresponding to a given key, use theg_hash_table_lookup ()andg_hash_table_lookup_extended ().
  • You can also useg_ hash_table_lookup_extended ()Simply check to see if there are keys in the hash table.
  • To delete keys and values, use theg_hash_table_remove ().
  • To call a function for each key and value pair, use theg_hash_table_foreach ()Or using iterators to iterate over key/value pairs in a hash table, seeGHashTableIter. The iteration order of hash tables is not defined, and you cannot rely on iterating over them in the same order as the keys/values were inserted.
  • useghash_table_destroy ()To destroy oneGHashTable.
  • A common use case for hash tables is to store information about a set of keys without associating any particular value with each key.GHashTableOptimized one way to do this: if you only storekey == valueKey value pairs of, thenGHashTableNo memory is allocated to store these values, which can save a considerable amount of space if your collection is large. functiong_hash_table_add ()andg_hash_table_contains ()Designed to be used this wayGHashTable.