内核的likely()/unlikely和glib的G_LIKELY/G_UNLIKELY zz

glib data structure.

os posted @ 2013年8月10日 17:16 in Glib , 1987 阅读

1. Glib Array (可变长的数组）

可以存放任意类型的元素，并且大小随着元素的增加可以自动增长。

glib库中的数组GArray类型很像C++标准容器库中的vector容器。要使用glib库中的数组中需要声明一个指向GArray类型的指针。

struct _GArray
{
  gchar *data;
  guint len;
};

struct _GByteArray
{
  guint8 *data;
  guint	  len;
};

struct _GPtrArray
{
  gpointer *pdata;
  guint	    len;
};

struct _GArray
{
  gchar *data;
  guint len;
};

struct _GByteArray
{
  guint8 *data;
  guint	  len;
};

struct _GPtrArray
{
  gpointer *pdata;
  guint	    len;
};

2. Glib SList/SList (单项列表/双向列表）

glib库单向链表GSList介绍

typedef struct _GSList GSList;

struct _GSList
{
  gpointer data;
  GSList *next;
};

struct _GSList
{
  gpointer data;
  GSList *next;
};

glib库双向链表GList介绍

双向链表与单向链表的区别是，从一个节点，不仅能访问到它的下一个节点，还能访问到它的上一个节点，其定义如下：

typedef struct _GList GList;

struct _GList
{
  gpointer data;
  GList *next;
  GList *prev;
};

typedef struct _GList GList;

struct _GList
{
  gpointer data;
  GList *next;
  GList *prev;
};

glib库队列GQueue介绍

struct _GQueue
{
  GList *head;
  GList *tail;
  guint  length;
};

typedef struct _GQueue		GQueue;

struct _GQueue
{
  GList *head;
  GList *tail;
  guint  length;
};

队列是一种向最后添加条目，从最前删除条目的数据结构，这种数据结构在处理按顺序到达的数据是很有用。glib库提供的队列GQueue是一个双端队列，它的实现基础是双向链表，所以它支持在队列的两端进行添加和删除，也支持很多其它的操作，比如在队列中进行插入和删除，但是我不推荐使用这样的功能，因为当你经常需要在队列中进行插入和删除的时候，链表或许是个更好的选择。

4. Glib Hash Table

glib库hash表GHashTable介绍

typedef struct _GHashNode      GHashNode;

struct _GHashNode
{
  gpointer   key;
  gpointer   value;

  /* If key_hash == 0, node is not in use
   * If key_hash == 1, node is a tombstone
   * If key_hash >= 2, node contains data */
  guint      key_hash;
};

struct _GHashTable
{
  gint             size;
  gint             mod;
  guint            mask;
  gint             nnodes;
  gint             noccupied;  /* nnodes + tombstones */
  GHashNode       *nodes;
  GHashFunc        hash_func;
  GEqualFunc       key_equal_func;
  volatile gint    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 _GHashNode      GHashNode;

struct _GHashNode
{
  gpointer   key;
  gpointer   value;

  /* If key_hash == 0, node is not in use
   * If key_hash == 1, node is a tombstone
   * If key_hash >= 2, node contains data */
  guint      key_hash;
};

struct _GHashTable
{
  gint             size;
  gint             mod;
  guint            mask;
  gint             nnodes;
  gint             noccupied;  /* nnodes + tombstones */
  GHashNode       *nodes;
  GHashFunc        hash_func;
  GEqualFunc       key_equal_func;
  volatile gint    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;
};

glib中hash table

http://blog.chinaunix.net/uid-24774106-id-3605760.html

从头到尾彻底解析Hash 表算法

http://cache.baiducontent.com/c?m=9d78d513d9d706ef06e2ce384b54c0676a499d267992c71508d4c20ece735b36163bbca67e760d04d1c67f6507b24359edf0316537747af1c496&p=8357c54ad5c243ef0be29664580ca5&newp=817ac64ad49118f708e2977f0f5cc6231610db2151d2d6132d8dcb&user=baidu

5. Glib Tree

平衡二叉树：对有序序列的一种优化，可以用来高效的查找和遍历等的一种树形结构。

typedef struct _GTreeNode  GTreeNode;

/**
 * GTree:
 *
 * The <structname>GTree</structname> struct is an opaque data
 * structure representing a <link
 * linkend="glib-Balanced-Binary-Trees">Balanced Binary Tree</link>. It
 * should be accessed only by using the following functions.
 **/
struct _GTree
{
  GTreeNode        *root;
  GCompareDataFunc  key_compare;
  GDestroyNotify    key_destroy_func;
  GDestroyNotify    value_destroy_func;
  gpointer          key_compare_data;
  guint             nnodes;
  gint              ref_count;
};

struct _GTreeNode
{
  gpointer   key;         /* key for this node */
  gpointer   value;       /* value stored at this node */
  GTreeNode *left;        /* left subtree */
  GTreeNode *right;       /* right subtree */
  gint8      balance;     /* height (left) - height (right) */
  guint8     left_child;  
  guint8     right_child;
};

struct _GTree
{
  GTreeNode        *root;
  GCompareDataFunc  key_compare;
  GDestroyNotify    key_destroy_func;
  GDestroyNotify    value_destroy_func;
  gpointer          key_compare_data;
  guint             nnodes;
  gint              ref_count;
};

struct _GTreeNode
{
  gpointer   key;         /* key for this node */
  gpointer   value;       /* value stored at this node */
  GTreeNode *left;        /* left subtree */
  GTreeNode *right;       /* right subtree */
  gint8      balance;     /* height (left) - height (right) */
  guint8     left_child;  
  guint8     right_child;
};

N树：

/* N-way tree implementation
 */
struct _GNode
{
  gpointer data;
  GNode	  *next;
  GNode	  *prev;
  GNode	  *parent;
  GNode	  *children;
};

/* N-way tree implementation
 */
struct _GNode
{
  gpointer data;
  GNode	  *next;
  GNode	  *prev;
  GNode	  *parent;
  GNode	  *children;
};

6. Glib String

7. Glib Quark

8. Glib Slice

/* --- structures --- */
typedef struct _ChunkLink      ChunkLink;
typedef struct _SlabInfo       SlabInfo;
typedef struct _CachedMagazine CachedMagazine;
struct _ChunkLink {
  ChunkLink *next;
  ChunkLink *data;
};
struct _SlabInfo {
  ChunkLink *chunks;
  guint n_allocated;
  SlabInfo *next, *prev;
};
typedef struct {
  ChunkLink *chunks;
  gsize      count;                     /* approximative chunks list length */
} Magazine;
typedef struct {
  Magazine   *magazine1;                /* array of MAX_SLAB_INDEX (allocator) */
  Magazine   *magazine2;                /* array of MAX_SLAB_INDEX (allocator) */
} ThreadMemory;
typedef struct {
  gboolean always_malloc;
  gboolean bypass_magazines;
  gboolean debug_blocks;
  gsize    working_set_msecs;
  guint    color_increment;
} SliceConfig;
typedef struct {
  /* const after initialization */
  gsize         min_page_size, max_page_size;
  SliceConfig   config;
  gsize         max_slab_chunk_size_for_magazine_cache;
  /* magazine cache */
  GMutex       *magazine_mutex;
  ChunkLink   **magazines;                /* array of MAX_SLAB_INDEX (allocator) */
  guint        *contention_counters;      /* array of MAX_SLAB_INDEX (allocator) */
  gint          mutex_counter;
  guint         stamp_counter;
  guint         last_stamp;
  /* slab allocator */
  GMutex       *slab_mutex;
  SlabInfo    **slab_stack;                /* array of MAX_SLAB_INDEX (allocator) */
  guint        color_accu;
} Allocator;

/* --- structures --- */
typedef struct _ChunkLink      ChunkLink;
typedef struct _SlabInfo       SlabInfo;
typedef struct _CachedMagazine CachedMagazine;
struct _ChunkLink {
  ChunkLink *next;
  ChunkLink *data;
};
struct _SlabInfo {
  ChunkLink *chunks;
  guint n_allocated;
  SlabInfo *next, *prev;
};
typedef struct {
  ChunkLink *chunks;
  gsize      count;                     /* approximative chunks list length */
} Magazine;
typedef struct {
  Magazine   *magazine1;                /* array of MAX_SLAB_INDEX (allocator) */
  Magazine   *magazine2;                /* array of MAX_SLAB_INDEX (allocator) */
} ThreadMemory;
typedef struct {
  gboolean always_malloc;
  gboolean bypass_magazines;
  gboolean debug_blocks;
  gsize    working_set_msecs;
  guint    color_increment;
} SliceConfig;
typedef struct {
  /* const after initialization */
  gsize         min_page_size, max_page_size;
  SliceConfig   config;
  gsize         max_slab_chunk_size_for_magazine_cache;
  /* magazine cache */
  GMutex       *magazine_mutex;
  ChunkLink   **magazines;                /* array of MAX_SLAB_INDEX (allocator) */
  guint        *contention_counters;      /* array of MAX_SLAB_INDEX (allocator) */
  gint          mutex_counter;
  guint         stamp_counter;
  guint         last_stamp;
  /* slab allocator */
  GMutex       *slab_mutex;
  SlabInfo    **slab_stack;                /* array of MAX_SLAB_INDEX (allocator) */
  guint        color_accu;
} Allocator;

Glib中slab内存管理算法实现（1/2/3）