list_sort算法实现不应使用快速排序, 考虑采用归并排序

sorry 我理解错了

重复的代码很多，建议在适当的时候进行重构，削减重复代码，减少代码数量。

include <cstl/calgorithm.h>

int main(int argc, char* argv[])
{
list_t* plist = create_list(int);
iterator_t it;

list_init(plist);
it = algo_remove_if(list_begin(plist), list_end(plist), NULL);    // assertion failure.
list_destroy(plist);

}

deque_equal函数头注释有一句"If the two deques are not same type, then return false"。但是实际上当两个deque中数据类型不同的时候函数的行为是未定义的，debug版本会触发断言。

环境是：IBM AIX
编译器是:alc

建议：判断是此类系统就去掉此编译选项

1 #include <cstl/cdeque.h>
2
3 int main(int argc, char* argv[]) {
4 deque_t* pdeq_first = create_deque(int);
5 deque_t* pdeq_second = create_deque(int);
6 deque_t* pdeq_third = create_deque(int);
7 deque_t* pdeq_fourth = create_deque(int);
8 int i = 0;
9
10 deque_init(pdeq_first);
11 for(i = 0; i < 1000; ++i) {
12 deque_push_back(pdeq_first, 9);
13 deque_pop_front(pdeq_first);
14 }
15 deque_destroy(pdeq_first);
16
17 deque_init(pdeq_second);
18 for(i = 0; i < 1000; ++i) {
19 deque_push_front(pdeq_second, 9);
20 deque_pop_back(pdeq_second);
21 }
22 deque_destroy(pdeq_second);
23
24 deque_init(pdeq_third);
25 for(i = 0; i < 100; ++i) {
26 deque_push_back(pdeq_third, 9);
27 }
28 for(i = 0; i < 50; ++i) {
29 deque_pop_front(pdeq_third);
30 }
31 deque_insert_n(pdeq_third, deque_end(pdeq_third), 1000, 9);
32 deque_destroy(pdeq_third);
33
34 deque_init(pdeq_fourth);
35 for(i = 0; i < 100; ++i) {
36 deque_push_front(pdeq_fourth, 9);
37 }
38 for(i = 0; i < 50; ++i) {
39 deque_pop_back(pdeq_fourth);
40 }
41 deque_insert_n(pdeq_fourth, deque_begin(pdeq_fourth), 1000, 9);
42 deque_destroy(pdeq_fourth);
43
44 return 0;
45 }
46

这段代码展示了这个bug，当循环达到一定次数之后，12行，19行在debug版本中会崩溃，31行，41行在debug版本会崩溃。

感谢 无聊才聊[email protected] 发现这个问题。

缺乏类型检查，什么都可以往里塞。
编译不报错，连warning也不报。

运行时报错

 vector_t *pvec_strptr = create_vector(string_t);
 vector_init(pvec_strptr);
 string_t *pstr1 = create_string();
 string_init(pstr1);
 string_assign_cstr(pstr1, "abc");
 vector_push_back(pvec_strptr, pstr1);
 vector_push_back(pvec_strptr, "123");
 vector_push_back(pvec_strptr, 123);
 vector_push_back(pvec_strptr, NULL);
 string_t *pstr2 = (string_t *)vector_at(pvec_strptr, 0);
 printf("%s ", string_c_str(pstr2));
 vector_destroy(pvec_strptr);

第六章，第一节，3算发的种类
_copy后缀中的algo_reverse_if()应该是algo_reverse_copy()。

我找原来的版本找到了，不知道和现在是不是相同的

https://github.com/activesys/libcstl/blob/aba1becc02/doc/user/libcstl_user_guide.pdf

将libcstl内建类型重定义之后，在创建保存重定义类型的容器的时候失败：
第一种情况：
typedef vector_t intvec_t;
这样是不行的，编译都不能够通过。

第二种情况：

define INTVEC_T vector_t

让后在创建的时候使用
vector_t* pvec = create_vector(INTVEC_T);
这样返回的结果是pvec == NULL，因为create_vector将认为用户使用的是INTVEC_T类型而不是宏替换后的vector_t类型，但是INTVEC_T类型没有注册，所以创建失败。

第三种情况：
typedef vector_t myvec_t
然后在创建的时候：
type_duplicate(vector_t, myvec_t);
pvec = create_vector(myvec_t);
但是这样也会创建失败。

[wb@ActiveSys libcstl]$ cat test_cpp_stl.cpp

void test_cpp_stl(void)
{
    std::vector<int> v1, v2;

    v1.assign(300, -39);
    v2 = v1;
}

int main(int argc, char* argv[])
{
    for (int i = 0; i < 100000; ++i) {
        test_cpp_stl();
    }
    return 0;
}

[wb@ActiveSys libcstl]$ cat test_cstl.c

void test_cstl(void)
{
    vector_t* pvec1 = NULL;
    vector_t* pvec2 = NULL;

    if ((pvec1 = create_vector(int)) == NULL) {
         return;
    }
    if ((pvec2 = create_vector(int)) == NULL) {
        vector_destroy(pvec1);
        return;
    }

    vector_init_elem(pvec1, 300, -39);
    vector_init(pvec2);
    vector_assign(pvec2, pvec1);

    vector_destroy(pvec1);
    vector_destroy(pvec2);
}

int main(int argc, char* argv[])
{
    int i = 0;
    for (i = 0; i < 100000; ++i) {
        test_cstl();
    }
    return 0;
}

[wb@ActiveSys libcstl]$ time ./test_cpp_stl

real 0m0.342s
user 0m0.303s
sys 0m0.021s
[wb@ActiveSys libcstl]$ time ./test_cstl

real 0m44.984s
user 0m42.134s
sys 0m0.039s

cstl_types.c文件中，_type_get_varg_value函数 637行
void* pv_elem = va_arg(val_elemlist, void*);
改为
void* pv_elem = val_elemlist;
不然自己写的copy函数拿不到结构体首地址

I've searching from the Internet for hours only to find that MinGW need a special treatment when compiling a dll file. That is, ld need a special parameter when creating dll file, if without it, we'll get this message instead of a dll file when linking:

libtool: link: warning: undefined symbols not allowed in i686-pc-mingw32 shared libraries

To solve this problem, we need to pass the -no-defined argument to ld, this can be done via modifying the Makefile.am in src folder, or someone suggest to use the following command instead of a simple make:
make LDFLAGS=-no-undefined

如何构建二维vector，为什么create_vector( vector_t )以及create_vector( vector_t * )都会返回NULL？

是需要先type_register一下吗？

第二章 libcstl库的基本概念

第二节 容器

1. 序列容器

1. p15
   “这样就可以使用下标来随即的访问”
   是否应为
   这样就可以使用下标来随机的访问

make check-TESTS
make[3]: Entering directory '/home/jackiez/eclipse-workspace/libcstl/test/ut'
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< test cstl_deque.c >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
-------------------------------- test deque_init --------------------------------
test_deque_init__null_deque_container: Starting test
Segmentation fault
Segmentation fault
test_deque_init__null_deque_container: Test failed.
test_deque_init__non_created_deque_container: Starting test
/bin/bash: line 5: 19807 Segmentation fault (core dumped) ${dir}$tst
FAIL: libcstl_ut
=======================================
1 of 1 test failed
Please report to [email protected]
=======================================
Makefile:3602: recipe for target 'check-TESTS' failed
make[3]: *** [check-TESTS] Error 1
make[3]: Leaving directory '/home/jackiez/eclipse-workspace/libcstl/test/ut'
Makefile:3724: recipe for target 'check-am' failed
make[2]: *** [check-am] Error 2
make[2]: Leaving directory '/home/jackiez/eclipse-workspace/libcstl/test/ut'
Makefile:249: recipe for target 'check-recursive' failed
make[1]: *** [check-recursive] Error 1
make[1]: Leaving directory '/home/jackiez/eclipse-workspace/libcstl/test'
Makefile:291: recipe for target 'check-recursive' failed
make: *** [check-recursive] Error 1

map<char*,void*>类型在查找的时候，使用pair_second时返回void**，需要使用*(void**)强转一下才能工作，新手可能完全没有头绪,建议返回值改为void*

容器的insert_range函数的行为，以deque_insert_range为例：

#include <stdio.h>
#include <cstl/cdeque.h>

int main(int argc, char* argv[])
{
    deque_t* pdeq = create_deque(int);
    iterator_t it;
    int i = 0;

    if (pdeq == NULL) {
        return -1;
    }

    deque_init(pdeq);

    deque_push_front(pdeq, 5);
    deque_push_front(pdeq, 4);
    deque_push_front(pdeq, 3);
    deque_push_front(pdeq, 2);
    deque_push_front(pdeq, 1);
    deque_push_front(pdeq, 0);
    deque_push_back(pdeq, 6);
    deque_push_back(pdeq, 7);
    deque_push_back(pdeq, 8);
    deque_push_back(pdeq, 9);
    for (it = deque_begin(pdeq);
         !iterator_equal(it, deque_end(pdeq));
         it = iterator_next(it)) {
        printf("%d ", *(int*)iterator_get_pointer(it));
    }
    printf("\n");

    deque_insert_range(pdeq, iterator_next_n(deque_begin(pdeq), 4),
        deque_begin(pdeq), iterator_next_n(deque_begin(pdeq), 2));
    for (it = deque_begin(pdeq);
         !iterator_equal(it, deque_end(pdeq));
         it = iterator_next(it)) {
        printf("%d ", *(int*)iterator_get_pointer(it));
    }
    printf("\n");

    return 0;
}

它的输出结果是：

0 1 2 3 4 5 6 7 8 9 
0 1 2 3 2 3 4 5 6 7 8 9

而不是想象中的：

0 1 2 3 4 5 6 7 8 9 
0 1 2 3 0 1 4 5 6 7 8 9

其实STL响应的代码也是这样的结果：

#include <iostream>
#include <deque>

int main(int argc, char* argv[])
{
    std::deque<int> deq;

    deq.push_front(5);
    deq.push_front(4);
    deq.push_front(3);
    deq.push_front(2);
    deq.push_front(1);
    deq.push_front(0);
    deq.push_back(6);
    deq.push_back(7);
    deq.push_back(8);
    deq.push_back(9);

    for (std::deque<int>::iterator it = deq.begin();
         it != deq.end();
         ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    deq.insert(deq.begin() + 4, deq.begin(), deq.begin() + 2);
    for (std::deque<int>::iterator it = deq.begin();
         it != deq.end();
         ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出结果：

0 1 2 3 4 5 6 7 8 9 
0 1 2 3 2 3 4 5 6 7 8 9

像这样的行为需要记录到教程或者参考手册中。

list_t* plist = create_list(basic_string_t);
创建失败,plist == NULL，原因是类型系统中不支持basic_string_t作为容器元素类型，参考doc/libcstl.bnf

In macos system, the file in system's default path also define stack_t structure.

In file included from ../cstl/cstack.h:35:
../cstl/cstl_stack_private.h:45:2: error: typedef redefinition with different types ('struct _tagstack'
vs 'struct __darwin_sigaltstack')
}stack_t;
^
/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.10.sdk/usr/include/sys/_types/_sigaltstack.h:42:29: note:
previous definition is here
typedef _STRUCT_SIGALTSTACK stack_t;

What steps will reproduce the problem?

1. define a struct A.
2. then define vector_t* v = create_vector(A_) but without register A_.
3. compile is fine, but will meet runtime error.

What is the expected output? What do you see instead?
All pointer can be treat as one type. If container can support a generic type pointer will be a good enhancement.

What version of the product are you using? On what operating system?
All, windows, linux, others. Only depend standard C lib.

Please provide any additional information below.

vector_push_back null crash in vector_destroy

    vector_t *pvec_charptr = create_vector(char *);
    vector_init(pvec_charptr);
    char *p;
    char *q = NULL;
    vector_push_back(pvec_charptr, p);
    vector_push_back(pvec_charptr, q);
    vector_destroy(pvec_charptr);

当用户使用了嵌套自定义类型的时候，即如下的形式：
typedef struct {
vector_t* pvec; /* pvec = create_vector(abc_t); */
} abc_t;
这个类型注册的时候没有问题，但是当外层容器初始化的时候会导致无限递归调用，直至调用栈满，然后进程崩溃。
例子代码：

  1 #include <stdio.h>
  2 #include <cstl/chash_map.h>
  3 #include <cstl/chash_set.h>
  4 
  5 typedef struct {
  6     hash_set_t* vars;
  7     hash_map_t* field_map;
  8     int status;
  9 } Alias;
 10 
 11 static void _alias_init(const void* cpv_input, void* pv_output)
 12 {
 13     Alias* p = (Alias*)cpv_input;
 14 
 15     p->vars = create_hash_set(char*);
 16     hash_set_init(p->vars);
 17     p->field_map = create_hash_map(char*, Alias); /* You must not be invoke init function */
 18     hash_map_init(p->field_map);
 19     p->status = 0;
 20 
 21     *(bool_t*)pv_output = true;
 22 }
 23 static void _alias_destroy(const void* cpv_input, void* pv_output)
 24 {
 25     Alias* p = (Alias*)cpv_input;
 26 
 27     hash_set_destroy(p->vars);
 28     hash_map_destroy(p->field_map);
 29 
 30     *(bool_t*)pv_output = true;
 31 }
 32 static void _alias_less(const void* cpv_first, const void* cpv_second, void* pv_output)
 33 {
 34     Alias* p1 = (Alias*)cpv_first;
 35     Alias* p2 = (Alias*)cpv_second;
 36 
 37     if (hash_set_less(p1->vars, p2->vars)) {
 38         *(bool_t*)pv_output = true;
 39         return;
 40     }
 41 
 42     if (hash_map_less(p1->field_map, p2->field_map)) {
 43         *(bool_t*)pv_output = true;
 44         return;
 45     }
 46 
 47     if (p1->status < p2->status) {
 48         *(bool_t*)pv_output = true;
 49         return;
 50     }
 51 
 52     *(bool_t*)pv_output = false;
 53 }
 54 static void _alias_copy(const void* cpv_first, const void* cpv_second, void* pv_output)
 55 {
 56     Alias* p1 = (Alias*)cpv_first;
 57     Alias* p2 = (Alias*)cpv_second;
 58 
 59     hash_set_assign(p1->vars, p2->vars);
 60     hash_map_assign(p1->field_map, p2->field_map);
 61     p1->status = p2->status;
 62 
 63     *(bool_t*)pv_output = true;
 64 }
 65 
 66 int main(int argc, char* argv[])
 67 {
 68     vector_t* pvec = NULL;
 69 
 70     type_register(Alias, _alias_init, _alias_copy, _alias_less, _alias_destroy);
 71     pvec = create_vector(Alias);
 72     if (pvec == NULL) {
 73         return -1;
 74     }
 75     vector_init_n(pvec, 10);
 76     printf("%d\n", vector_size(pvec));
 77 
 78     vector_destroy(pvec);
 79     return 0;
 80 }
 81                                                                

最近版本。
./configure
ok
make
failed!!
libcstl_la-cstl_algo_nonmutating.Tpo <==这种Tpo文件的操作上出错！，就没有这文件，倒是Plo文件在src/.deps里有

将libcstl组件化，按照不同的需求，在编译的时候按需选取不同的数据结构极其算法来编译和安装。

类似于deque_insert_range这样的range函数不允许range属于目标容器。还有例如deque_assign_range等等。

stl中当容器保存的类型不同的时候，有编译错误：
[wangbo@centos stl]$ cat test_compare_not_same_type.cc

#include <iostream>
#include <vector>

int main(int argc, char* argv[])
{
    std::vector<int> v1;
    std::vector<void*> v2;
    std::vector<void*> v3;

    std::cout << bool(v2 == v3) << std::endl;
    std::cout << bool(v1 == v2) << std::endl;

    return 0;
}

[wangbo@centos stl]$ g++ -g test_compare_not_same_type.cc
test_compare_not_same_type.cc: In function ‘int main(int, char**)’:
test_compare_not_same_type.cc:12: error: no match for ‘operator==’ in ‘v1 == v2

但是libcstl认为两个包含不同类型的容器不等：
[wangbo@centos stl]$ cat test_compare_not_same_type.c

#include <stdio.h>
#include <cstl/cvector.h>

int main(int argc, char* argv[])
{
    vector_t* pvec1 = create_vector(int);
    vector_t* pvec2 = create_vector(double);
    vector_t* pvec3 = create_vector(double);

    vector_init(pvec1);
    vector_init(pvec2);
    vector_init(pvec3);
    printf("%d, %d\n", vector_equal(pvec1, pvec2), vector_equal(pvec2, pvec3));

    return 0;
}

[wangbo@centos stl]$ gcc -lcstl test_compare_not_same_type.c
[wangbo@centos stl]$ ./a.out
0, 1

typedef uint64_t vp_uint64_t;

create_multimap(vp_uint64_t, int); 总是返回NULL；请问下对于typedef的类型需要使用type_register来注册吗？如何使用呢？

另外，我发现uint64_t在mac上运行没问题，在linux虚拟机上却读取出错。

priority_queue_init(ppque1);
priority_queue_init_ex(ppque2, fun_greater_int);

priority_queue_assign(ppque1, ppque2);
函数执行成功并且将ppque2的优先级规则赋值给ppque1，正确情况下，这样的赋值行为是为定义的。

http://libcstl.org/docs/tutorial.html

顺便提下：
参考手册没有完善是因为没时间吗？
为什么不用doxygen生成描述文档，可以生成HTML哦！

In ms vc inline should be replace as __inline.
Error Place:
cstl_types.c static inline bool_t _type_cstl_builtin_special(...)

环境
Linux ubuntu 3.0.0-15-generic-pae #26-Ubuntu SMP Fri Jan 20 17:07:31 UTC 2012 i686 i686 i386 GNU/Linux
库
libcstl, libev
编译
clang

stack_t 重定义
In file included from src/inc/cstl/cstack.h:35:
src/inc/cstl/cstl_stack_private.h:45:2: error: typedef redefinition with different types ('struct _tagstack' vs 'struct sigaltstack')
}stack_t;
^

In file included from src/inc/ev.h:146:
In file included from /usr/include/signal.h:356:
/usr/include/i386-linux-gnu/bits/sigstack.h:55:5: note: previous definition is here
} stack_t;
^

iterator_next(string_end(pstr));
这段代码实际上应该崩溃，但是实际没有崩溃。
同样下列代码也不会崩溃。
iterator_get_value(string_end(pstr), &c);
iterator_set_value(string_end(pstr), &c);
iterator_get_pointer(string_end(pstr));

第三章

第一节 小内存管理机制

1. 8, 16, 24, 32, 40, 48, 56, 84, ....
   是否应为
   8, 16, 24, 32, 40, 48, 56, 64
2. 也就是实际回分配 32 个字节
   是否应为
   也就是实际会分配 32 个字节
3. 这样我们可以使用一个数组表示这 16 中内存块
   是否应为
   这样我们可以使用一个数组表示这 16 种内存块

What steps will reproduce the problem?
如下代码会触发debug下的断言:
string_t *strTest = create_string();
string_init_cstr(strTest, "test");
size_t pos = string_find_cstr(strTest, "a", 0);

What is the expected output? What do you see instead?
应返回NPOS, 但程序触发basic_string_find_subcstr中1047行assert(false);

What version of the product are you using? On what operating system?
win32下测试libcstl 2.0.2.

Please provide any additional information below.
根据我的观察似乎那句assert(false);是多余的，直接去掉就能正常运行。。。
Delete comment Comment 1 by project member activesys.wb, Oct 12, 2011
bug已经修复，请使用issue27.patch补丁。

看了下你的源代码，写的很好，但是没有体现面向对象的**，C为什么要面向对象？Linux内核就是最好的例子，Linux内核尽管是C和汇编写的，但是里面却大量使用了面向对象的**，要不然它的代码怎么会写的如此精妙，同一份源代码能够支持几十种架构

另外你的API应该和C++ STL要类似，这样可以减少开发者的学习成本和更方便的使用，比如说C++的list里有哪些方法，你的libcstl应该提供对应的方法

之前我自己也封装过，但是对于自定义的类型处理不好，所以弃坑了......

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// list简单封装...

typedef void* Type;

typedef struct Node{
int data;
struct Node *next;
struct Node *prev;
}Node;

// 把所有的方法都封装在list里面，类似于class
typedef struct list{
void (*add) (Node *head,int data);
void (*insert) (Node *head,int data,int pos);
bool (*empty) (Node *head);
// ...
}list;

void list_add(Node *head,int data){
printf("data = %d\n",data);
}

bool list_empty(Node *head){
printf("list is empty...\n");
return false;
}

// 这个方法返回的是一个list结构体
list create_list(Type T){
list m_list = {
.add = list_add,
.empty = list_empty
};
// 进行链表的一些初始化，构造头节点...
// ...
return m_list;
}

// 这个方法返回的是一个list结构体指针，类似于C++的new
list* new_list(Type T){
list p_list = (list)malloc(sizeof(list));
p_list->add = list_add;
p_list->empty = list_empty;
// 进行链表的一些初始化，构造头节点...
// ...
return p_list;
}

/* main function */
int main(int argc,char **argv){
// 构造list对象，通过对象调用方法，这样就可以达到类似面向对象的效果
list mlist = create_list(NULL);
mlist.add(NULL,666);

list *plist = new_list(NULL);
plist->empty(NULL);

return 0;

}

http://libcstl.org/

貌似红黑树和哈希表是支持按键删除的啊？

string_append_subcstr 当遇到 '\0' 字符时，整个 '\0' 之后的字符串会被截断，即使字符串长度参数设为很大也不起作用。

建议 string 中可容纳 '\0' 字符，以保持和 c++ 中的 stl 一致，对于 c++ 程序，我经常通过类似于如下的代码来存放数据：
string buffer("hello\0, world.", 14);

之所以选择 string，是因为它很适合存储网络或串口数据，并提供了一些相关的算法方便解析数据，因此建议对于该功能，有必要考虑一下是否增加。

同样，对于获取数据时也可根据需要不截断 '\0' 数据。

Program terminated with signal 11, Segmentation fault.
#0 0x00000000004403a3 in pair_init (ppair_pair=0xf018a7c) at cstl_pair.c:51

51 if ((ppair_pair->_pv_first = malloc(_GET_PAIR_FIRST_TYPE_SIZE(ppair_pair))) == NULL) {

其中stack_t在Mac的gcc下已有定义。
见 _signaltstack.h 中的typedef _STRUCT_SIGALTSTACK stack_t;

libcstl版本：2.3.0
gcc版本：
Apple LLVM version 7.0.2 (clang-700.1.81)
Target: x86_64-apple-darwin15.2.0
Thread model: posix

Mac OS X 10.11

include <stdio.h>

include <cstl/cvector.h>

int main(int argc, char* argv[])
{
vector_t* pvec = create_vector(long);
long l = 0;

if (pvec == NULL) {
    return -1;
}

vector_init(pvec);
vector_push_back(pvec, -3333);
l = -3333;
vector_push_back(pvec, l);
printf("%ld, %ld\n", *(long*)vector_at(pvec, 0), *(long*)vector_at(pvec, 1));
vector_destroy(pvec);

return 0;

}

结果是：
4294963963, -3333