存档在 ‘STL’ 分类

SGI list内存管理分析

2013年5月1日

list默认使用alloc作为空间配置器,alloc是什么?可以参考前面的文章,其实在这里可能是第一级空间配置器,也可能是第二级空间配置器。

template
class list {};

还是那样为了满足标准,需要对配置器包装,在list中成为list_node_allocator.

  typedef simple_alloc<list_node, Alloc> list_node_allocator;

所以list中就使用list_node_allocator作为配置器。可以如下使用:

list_node_allocator::allocate();
list_node_allocator::deallocate(p)

下面来看看list中节点的构造。
首先看如何配置一个节点空间,并传回地址:

 link_type get_node() { return list_node_allocator::allocate(); }1
再来看如果释放一个节点空间:
1 void put_node(link_type p) { list_node_allocator::deallocate(p); }

那么在list中,如何来构造一个list节点,首先配置空间,然后在返回的空间上构造。
» 阅读更多: SGI list内存管理分析

SGI list代码分析与原理解析[2]

2013年5月1日

SGI list代码分析与原理解析[1]分析了list节点定义,迭代器定义,list类的定义。再来总结一下:
客户需要使用list这个容器,那么就需要通过list配套的迭代器iterator,所以list中有

typedef __list_iterator<T, T&, T*>             iterator;

这个迭代器如何与list关联的呢?比如客户有如下代码

list<int> myList;
myList.begin();

客户想返回头迭代器,而list内部使用的是link_type。看下面的代码就知道了
list类定义中有

iterator begin() { return (link_type)((*node).next); }

__list_iterator类的定义中有

  
link_type node;
__list_iterator(link_type x) : node(x) {}

这样子,客户就可以返回想要的迭代器了。并且能够通过iterator来操作元素了。

list由于使用一个指针就可以来完整访问整个链表,那么list如何设计才能具有如此的性质,初始化的node( link_type node)应该是什么?
其实list设置在尾部有一个空白节点,初始化时让node指向该空白节点,而且符合了stl要求的“前闭后开”特性。

由于node指向尾部空白节点,即为end(),那么begin则为

iterator begin() { return (link_type)((*node).next); }
  const_iterator begin() const { return (link_type)((*node).next); }
  iterator end() { return node; }
  const_iterator end() const { return node; }

可以看出node的下一节点则是头部节点。这样判断list为空也好判断

bool empty() const { return node->next == node; }

因为node的前驱和后继都初始化为它自己。

  void empty_initialize() { 
    node = get_node();
    node->next = node;
    node->prev = node;
  

SGI list代码分析与原理解析[1]

2013年5月1日

list内部采用双向链表实现,而且还是一个环状双向链表,使用一个指针就可以访问整个链表。list的每个节点定义如下。

template <class T>
struct __list_node {
  typedef void* void_pointer;
  void_pointer next;
  void_pointer prev;
  T data;
};

那么list如下定义呢?一下只截取部分代码

template <class T, class Alloc = alloc>
class list {
protected:
  typedef void* void_pointer;
  typedef __list_node<T> list_node;
  typedef simple_alloc<list_node, Alloc> list_node_allocator;
public:      
  typedef T value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef list_node* link_type;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;

public:
  typedef __list_iterator<T, T&, T*>             iterator;
  typedef __list_iterator<T, const T&, const T*> const_iterator;
protected:
  link_type node;
};

在list的定义中,每个节点定义为typedef __list_node list_node;
那么指向每个节点的指针为typedef list_node* link_type;
前面说了,一个list,可以用一个指针访问,那么整个指针为link_type node,整个指针式list类内部使用。然而对于客户要使用list,并且融入stl框架,则需要迭代器。那么list的迭代器如何定义? » 阅读更多: SGI list代码分析与原理解析[1]

如何让自己的迭代器融入标准的STL框架

2013年4月27日

任何迭代器,如果想能与STL完美兼容,也即是能够使用STL的各种算法与各种工具。那么就得遵循它的要求,那就是有5个内嵌类型必须定义,这样就可以让traits萃取。但是在每个迭代器都去自己写这些确实容易遗忘,但是这里有一个较简单的方法来实现。那就是STL提供的iterator这个类,可以让自己定义的新的迭代器继承他。

template <class Category, class T, class Distance = ptrdiff_t,
          class Pointer = T*, class Reference = T&>
struct iterator {
  typedef Category  iterator_category;
  typedef T         value_type;
  typedef Distance  difference_type;
  typedef Pointer   pointer;
  typedef Reference reference;
};

» 阅读更多: 如何让自己的迭代器融入标准的STL框架

STL中的特性萃取机iterator_traits

2013年4月26日

很早以前,第一次看STL源码,第一次接触iterator_traits,我觉得他是一个巧妙的发明。
而现在再来看他,我觉得他变得更加绝妙。

iterator_traits是和迭代器在一起的,是针对迭代器来说的。也就是说通过iterator_traits可以了解到迭代器的信息和迭代器所指向元素的信息。
在编码的时候,往往需要定义一个迭代器指向对象类型的变量或者对象,我们可以利用函数模板推导来获得value_type类型。

template <class I, clss T>
void _func(I iter, T t)
{
	T tmp;
	/*---*/
}

template <class I>
void func(I iter)
{
	_func(iter, *iter);
}

» 阅读更多: STL中的特性萃取机iterator_traits

STL的第二级空间配置器代码分析[2]

2013年4月26日

上面描诉了allocate函数,这个函数是标准配置器的接口函数。在该函数中,首先判断区块大小是否大于128字节,如果大于则调用第一级配置器,小于则检查对应的自由链表,如果对应的自由链表有可用的块则直接使用,否则将区块大小上升到8的倍数,调用refill重新填充空间。再来看看allocate的对立面deallocate,具体的意思看代码里的注释。

   /* p may not be 0 */
  static void deallocate(void *p, size_t n)
  {
    obj *q = (obj *)p;
		//用于指向16个自由链表中最合适哪一个
    obj * __VOLATILE * my_free_list;
		//大于128字节则交给第一级配置器处理
    if (n > (size_t) __MAX_BYTES) {
        malloc_alloc::deallocate(p, n);
        return;
    }
		//确定自由链表
    my_free_list = free_list + FREELIST_INDEX(n);
    // acquire lock
#       ifndef _NOTHREADS
        /*REFERENCED*/
        lock lock_instance;
#       endif /* _NOTHREADS */
	//将p指向的内存块添加到自由链表里
    q -> free_list_link = *my_free_list;
		//修改自由链表的指向
    *my_free_list = q;
    // lock is released here
  }

» 阅读更多: STL的第二级空间配置器代码分析[2]

STL的第二级空间配置器代码分析[1]

2013年4月25日

STL的第二级空间配置器里有很多经典的思想,确实值得细细品味。
为什么使用如下的代码:

  static size_t ROUND_UP(size_t bytes) {
        return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
  }

他的原理可以看这里

» 阅读更多: STL的第二级空间配置器代码分析[1]

STL的第二级空间配置器

2013年4月25日

当申请的内存比较小时,频繁的申请与释放很容易造成碎片,而且还会造成配置的负担。所以当小额分配时,在内存池中进行分配,这样就避免了申请和释放带来的碎片,还避免了频繁申请带来的效率问题。
STL的第二级空间配置器的做法是:如果申请的内存大于128字节,则交给第一级,否则在第二级中用内存池管理。基本原理是,每次配置一大块内存,并用自由链表进行维护,内存的申请直接在自由链表中划拨。释放的内存则由自由链表回收。

对于小额区块内存,都会上升到8的倍数,比如13会上升到16.31会上升到32.
第二级配置器维护16个自由链表,分别管理大小为『8,16,24.。。』的区块。以下3个分别为小额内存的上升边界,小额内存的上限,自由链表的个数。
enum {__ALIGN = 8};
enum {__MAX_BYTES = 128};
enum {__NFREELISTS = __MAX_BYTES/__ALIGN}; » 阅读更多: STL的第二级空间配置器