Chinaunix首页 | 论坛 | 博客

Tommyhung

首页　| 　博文目录　| 　关于我

hongjiujing

  • 博客访问： 425810
  • 博文数量： 115
  • 博客积分： 10
  • 博客等级： 民兵
  • 技术积分： 393
  • 用 户 组： 普通用户
  • 注册时间： 2011-02-26 12:10
个人简介

踏实做事，认真做人

文章分类

全部博文（115）

文章存档

2017年（1）

2016年（2）

2015年（14）

2014年（63）

2013年（35）

我的朋友
最近访客
推荐博文
相关博文
STL源码剖析—list（3）

分类： C/C++

2014-07-15 11:27:10

原文地址：STL源码剖析—list（3） 作者：andyhzw

操作系统：ubuntu10.04
STL源码版本：2.91


前言：
    通过前面的两个章节，大概对stl的架构有个基础的了解，那么接下来应该怎么做呢：
    应该从应用的角度，也就是最上层的应用，来看 list是如何被使用，在一步步深入。

1，list的接口：
    1.1）list的各个接口的使用用例，请看：
             

c++ stl list使用总结



    1.2）由上面可得，list的类定义为：
        文件list是调用list接口的#include文件。

点击(此处)折叠或打开 《文件list》

  1. #ifndef __SGI_STL_LIST
  2. #define __SGI_STL_LIST

  4. #include <stl_algobase.h>
  5. #include <stl_alloc.h>
  6. #include <stl_construct.h>
  7. #include <stl_uninitialized.h>
  8. #include <stl_list.h>

  10. #endif /* __SGI_STL_LIST */

        1.2.1）list接口真正定义在 文件中
            对于 typedef 在类中的定义有疑问的请看：c++的类中typedef的作用 

点击(此处)折叠或打开

  1. template <class T, class Alloc = alloc>
  2. class list {
  3. protected:
  4.   typedef void* void_pointer;
  5.   typedef __list_node<T> list_node;
  6.   typedef simple_alloc<list_node, Alloc> list_node_allocator;
  7. public:
  8.   typedef T value_type;
  9.   typedef value_type* pointer;
  10.   typedef const value_type* const_pointer;
  11.   typedef value_type& reference;
  12.   typedef const value_type& const_reference;
  13.   typedef list_node* link_type;
  14.   typedef size_t size_type;
  15.   typedef ptrdiff_t difference_type;

  17. public:
  18.   typedef __list_iterator<T, T&, T*> iterator;
  19.   typedef __list_iterator<T, const T&, const T*> const_iterator;

  21.   typedef reverse_iterator<const_iterator> const_reverse_iterator;
  22.   typedef reverse_iterator<iterator> reverse_iterator;

  24. protected:
  25.   link_type get_node() { return list_node_allocator::allocate(); }
  26.   void put_node(link_type p) { list_node_allocator::deallocate(p); }

  28.   link_type create_node(const T& x) {
  29.     link_type p = get_node();
  30.     __STL_TRY {
  31.       construct(&p->data, x);
  32.     }
  33.     __STL_UNWIND(put_node(p));
  34.     return p;
  35.   }
  36.   void destroy_node(link_type p) {
  37.     destroy(&p->data);
  38.     put_node(p);
  39.   }

  41. protected:
  42.   void empty_initialize() {
  43.     node = get_node();
  44.     node->next = node;
  45.     node->prev = node;
  46.   }

  48.   void fill_initialize(size_type n, const T& value) {
  49.     empty_initialize();
  50.     __STL_TRY {
  51.       insert(begin(), n, value);
  52.     }
  53.     __STL_UNWIND(clear(); put_node(node));
  54.   }

  56.   template <class InputIterator>
  57.   void range_initialize(InputIterator first, InputIterator last) {
  58.     empty_initialize();
  59.     __STL_TRY {
  60.       insert(begin(), first, last);
  61.     }
  62.     __STL_UNWIND(clear(); put_node(node));
  63.   }

  65. protected:
  66.   link_type node;

  68. public:
  69.   list() { empty_initialize(); }

  71.   iterator begin() { return (link_type)((*node).next); }
  72.   const_iterator begin() const { return (link_type)((*node).next); }
  73.   iterator end() { return node; }
  74.   const_iterator end() const { return node; }
  75.   reverse_iterator rbegin() { return reverse_iterator(end()); }
  76.   const_reverse_iterator rbegin() const {
  77.     return const_reverse_iterator(end());
  78.   }
  79.   reverse_iterator rend() { return reverse_iterator(begin()); }
  80.   const_reverse_iterator rend() const {
  81.     return const_reverse_iterator(begin());
  82.   }
  83.   bool empty() const { return node->next == node; }
  84.   size_type size() const {
  85.     size_type result = 0;
  86.     distance(begin(), end(), result);
  87.     return result;
  88.   }
  89.   size_type max_size() const { return size_type(-1); }
  90.   reference front() { return *begin(); }
  91.   const_reference front() const { return *begin(); }
  92.   reference back() { return *(--end()); }
  93.   const_reference back() const { return *(--end()); }
  94.   void swap(list<T, Alloc>& x) { __STD::swap(node, x.node); }
  95.   iterator insert(iterator position, const T& x) {
  96.     link_type tmp = create_node(x);
  97.     tmp->next = position.node;
  98.     tmp->prev = position.node->prev;
  99.     (link_type(position.node->prev))->next = tmp;
  100.     position.node->prev = tmp;
  101.     return tmp;
  102.   }
  103.   iterator insert(iterator position) { return insert(position, T()); }

  105.   template <class InputIterator>
  106.   void insert(iterator position, InputIterator first, InputIterator last);

  108.   void insert(iterator pos, size_type n, const T& x);
  109.   void insert(iterator pos, int n, const T& x) {
  110.     insert(pos, (size_type)n, x);
  111.   }
  112.   void insert(iterator pos, long n, const T& x) {
  113.     insert(pos, (size_type)n, x);
  114.   }

  116.   void push_front(const T& x) { insert(begin(), x); }
  117.   void push_back(const T& x) { insert(end(), x); }
  118.   iterator erase(iterator position) {
  119.     link_type next_node = link_type(position.node->next);
  120.     link_type prev_node = link_type(position.node->prev);
  121.     prev_node->next = next_node;
  122.     next_node->prev = prev_node;
  123.     destroy_node(position.node);
  124.     return iterator(next_node);
  125.   }
  126.   iterator erase(iterator first, iterator last);
  127.   void resize(size_type new_size, const T& x);
  128.   void resize(size_type new_size) { resize(new_size, T()); }
  129.   void clear();

  131.   void pop_front() { erase(begin()); }
  132.   void pop_back() {
  133.     iterator tmp = end();
  134.     erase(--tmp);
  135.   }
  136.   list(size_type n, const T& value) { fill_initialize(n, value); }
  137.   list(int n, const T& value) { fill_initialize(n, value); }
  138.   list(long n, const T& value) { fill_initialize(n, value); }
  139.   explicit list(size_type n) { fill_initialize(n, T()); }

  141. #ifdef __STL_MEMBER_TEMPLATES
  142.   template <class InputIterator>
  143.   list(InputIterator first, InputIterator last) {
  144.     range_initialize(first, last);
  145.   }

  147.   list(const list<T, Alloc>& x) {
  148.     range_initialize(x.begin(), x.end());
  149.   }
  150.   ~list() {
  151.     clear();
  152.     put_node(node);
  153.   }
  154.   list<T, Alloc>& operator=(const list<T, Alloc>& x);

  156. protected:
  157.   void transfer(iterator position, iterator first, iterator last) {
  158.     if (position != last) {
  159.       (*(link_type((*last.node).prev))).next = position.node;
  160.       (*(link_type((*first.node).prev))).next = last.node;
  161.       (*(link_type((*position.node).prev))).next = first.node;
  162.       link_type tmp = link_type((*position.node).prev);
  163.       (*position.node).prev = (*last.node).prev;
  164.       (*last.node).prev = (*first.node).prev;
  165.       (*first.node).prev = tmp;
  166.     }
  167.   }

  169. public:
  170.   void splice(iterator position, list& x) {
  171.     if (!x.empty())
  172.       transfer(position, x.begin(), x.end());
  173.   }
  174.   void splice(iterator position, list&, iterator i) {
  175.     iterator j = i;
  176.     ++j;
  177.     if (position == i || position == j) return;
  178.     transfer(position, i, j);
  179.   }
  180.   void splice(iterator position, list&, iterator first, iterator last) {
  181.     if (first != last)
  182.       transfer(position, first, last);
  183.   }
  184.   void remove(const T& value);
  185.   void unique();
  186.   void merge(list& x);
  187.   void reverse();
  188.   void sort();

  190.   template <class Predicate> void remove_if(Predicate);
  191.   template <class BinaryPredicate> void unique(BinaryPredicate);
  192.   template <class StrictWeakOrdering> void merge(list&, StrictWeakOrdering);
  193.   template <class StrictWeakOrdering> void sort(StrictWeakOrdering);

  195.   friend bool operator== __STL_NULL_TMPL_ARGS (const list& x, const list& y);
  196. };

  2，空间配置器 allocate
    在看class list的过程中，需要了解的第一个要点是 空间配置器 allocate，其实现内存的动态分配。

点击(此处)折叠或打开

  1. template<class T, class Alloc>
  2. class simple_alloc {

  4. public:
  5.     static T *allocate(size_t n)
  6.                 { return 0 == n? 0 : (T*) Alloc::allocate(n * sizeof (T)); }
  7.     static T *allocate(void)
  8.                 { return (T*) Alloc::allocate(sizeof (T)); }
  9.     static void deallocate(T *p, size_t n)
  10.                 { if (0 != n) Alloc::deallocate(p, n * sizeof (T)); }
  11.     static void deallocate(T *p)
  12.                 { Alloc::deallocate(p, sizeof (T)); }
  13. };
        内存的真正的动态分配的实现在：

点击(此处)折叠或打开 >

  1. typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
      在ubuntu10.04中的gcc使用的宏定义中可知：

点击(此处)折叠或打开

  1. # ifdef __STL_PTHREADS
  2. # include <pthread.h>
  3. # define __NODE_ALLOCATOR_THREADS true
  4. # endif

点击(此处)折叠或打开

  1. template <bool threads, int inst>  //
  2. class __default_alloc_template {

  4. private:
  5.   static size_t ROUND_UP(size_t bytes) {
  6.         return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
  7.   }
  8. __PRIVATE:
  9.   union obj {
  10.         union obj * free_list_link;
  11.         char client_data[1]; /* The client sees this. */
  12.   };
  13. private:
  14.     static obj * __VOLATILE free_list[__NFREELISTS];

  16.   static size_t FREELIST_INDEX(size_t bytes) {
  17.         return (((bytes) + __ALIGN-1)/__ALIGN - 1);
  18.   }

  20.   // Returns an object of size n, and optionally adds to size n free list.
  21.   static void *refill(size_t n);
  22.   // Allocates a chunk for nobjs of size "size". nobjs may be reduced
  23.   // if it is inconvenient to allocate the requested number.
  24.   static char *chunk_alloc(size_t size, int &nobjs);

  26.   // Chunk allocation state.
  27.   static char *start_free;
  28.   static char *end_free;
  29.   static size_t heap_size;

  31.   static pthread_mutex_t __node_allocator_lock;

  33.     class lock {
  34.         public:
  35.             lock() { __NODE_ALLOCATOR_LOCK; }
  36.             ~lock() { __NODE_ALLOCATOR_UNLOCK; }
  37.     };
  38.     friend class lock;

  40. public:

  42.   /* n must be > 0 */
  43.   static void * allocate(size_t n)
  44.   {
  45.     obj * __VOLATILE * my_free_list;
  46.     obj * __RESTRICT result;

  48.     if (n > (size_t) __MAX_BYTES) {
  49.         return(malloc_alloc::allocate(n));
  50.     }
  51.     my_free_list = free_list + FREELIST_INDEX(n);
  52.     // Acquire the lock here with a constructor call.
  53.     // This ensures that it is released in exit or during stack
  54.     // unwinding.

  56.         lock lock_instance;

  58.     result = *my_free_list;
  59.     if (result == 0) {
  60.         void *r = refill(ROUND_UP(n));
  61.         return r;
  62.     }
  63.     *my_free_list = result -> free_list_link;
  64.     return (result);
  65.   };

  67.   /* p may not be 0 */
  68.   static void deallocate(void *p, size_t n)
  69.   {
  70.     obj *q = (obj *)p;
  71.     obj * __VOLATILE * my_free_list;

  73.     if (n > (size_t) __MAX_BYTES) {
  74.         malloc_alloc::deallocate(p, n);
  75.         return;
  76.     }
  77.     my_free_list = free_list + FREELIST_INDEX(n);
  78.     // acquire lock

  80.         /*REFERENCED*/
  81.         lock lock_instance;

  83.     q -> free_list_link = *my_free_list;
  84.     *my_free_list = q;
  85.     // lock is released here
  86.   }

  88.   static void * reallocate(void *p, size_t old_sz, size_t new_sz);

  90. } ;
    malloc_alloc定义如下：

点击(此处)折叠或打开

  1. typedef __malloc_alloc_template<0> malloc_alloc;

点击(此处)折叠或打开

  1. template <int inst>
  2. class __malloc_alloc_template {

  4. private:

  6. static void *oom_malloc(size_t);

  8. static void *oom_realloc(void *, size_t);

  10. #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
  11.     static void (* __malloc_alloc_oom_handler)();
  12. #endif

  14. public:

  16. static void * allocate(size_t n)
  17. {
  18.     void *result = malloc(n);
  19.     if (0 == result) result = oom_malloc(n);
  20.     return result;
  21. }

  23. static void deallocate(void *p, size_t /* n */)
  24. {
  25.     free(p);
  26. }

  28. static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
  29. {
  30.     void * result = realloc(p, new_sz);
  31.     if (0 == result) result = oom_realloc(p, new_sz);
  32.     return result;
  33. }

  35. static void (* set_malloc_handler(void (*f)()))()
  36. {
  37.     void (* old)() = __malloc_alloc_oom_handler;
  38.     __malloc_alloc_oom_handler = f;
  39.     return(old);
  40. }

  42. };

3，__list_node的定义：

点击(此处)折叠或打开

  1. template <class T>
  2. struct __list_node {
  3.   typedef void* void_pointer;
  4.   void_pointer next;
  5.   void_pointer prev;
  6.   T data;
  7. };

4，__list_iterator的定义：

点击(此处)折叠或打开

  1. template<class T, class Ref, class Ptr>
  2. struct __list_iterator {
  3.   typedef __list_iterator<T, T&, T*> iterator;
  4.   typedef __list_iterator<T, const T&, const T*> const_iterator;
  5.   typedef __list_iterator<T, Ref, Ptr> self;

  7.   typedef bidirectional_iterator_tag iterator_category;
  8.   typedef T value_type;
  9.   typedef Ptr pointer;
  10.   typedef Ref reference;
  11.   typedef __list_node<T>* link_type;
  12.   typedef size_t size_type;
  13.   typedef ptrdiff_t difference_type;

  15.   link_type node;

  17.   __list_iterator(link_type x) : node(x) {}
  18.   __list_iterator() {}
  19.   __list_iterator(const iterator& x) : node(x.node) {}

  21.   bool operator==(const self& x) const { return node == x.node; }
  22.   bool operator!=(const self& x) const { return node != x.node; }
  23.   reference operator*() const { return (*node).data; }

  25.   pointer operator->() const { return &(operator*()); }

  27.   self& operator++() {
  28.     node = (link_type)((*node).next);
  29.     return *this;
  30.   }
  31.   self operator++(int) {
  32.     self tmp = *this;
  33.     ++*this;
  34.     return tmp;
  35.   }
  36.   self& operator--() {
  37.     node = (link_type)((*node).prev);
  38.     return *this;
  39.   }
  40.   self operator--(int) {
  41.     self tmp = *this;
  42.     --*this;
  43.     return tmp;
  44.   }
  45. };


  




阅读(1007) | 评论(0) | 转发(0) |
0

上一篇：Linux内存管理和性能学习笔记（一）：内存测量与堆内存

下一篇：Uncompressing Linux... done, booting the kernel

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6