简单堆排序

#include <stdio.h>
#include <string.h>

void heaplify(int *arr, int len, int pos)
{
    int left = pos * 2 + 1;
    int right = pos * 2 + 2;
    int max = 0;
    int temp = 0;

    if( left < len  && arr[left] > arr[pos])
    {
        max = left;
    }
    else
    {
        max = pos;    
    }
    if( right < len && arr[right] > arr[max])
    {
        max = right;
    }

    if( max != pos)
    {
        temp = arr[max];
        arr[max]= arr[pos];
        arr[pos] = temp;

        heaplify(arr, len, max);
    }

}

void buildHeap(int *arr, int len)
{
    for(int i = len / 2 - 1; i>=0 ; i--)
    {
        heaplify(arr, len, i);
    }
}

int * heapSort(int *arr, int len)
{

    buildHeap(arr, len);

    for( int i = len - 1; i > 0 ; i--)
    {
        int tmp = arr[i];
        arr[i] = arr[0];
        arr[0] = tmp;

        heaplify(arr, i , 0);
    }

    return arr;
}

void printArray(int *arr, int len)
{
    for(int i = 0; i < len; i++)
    {
        printf("%-2d",arr[i]);
    }
    printf("/n");
}

void Test_1()
{
    struct T
    {
        int st[10] ;
        int end[10];
    } test[] =
    {
        {7,4,1,3,8,5,6,2,0,9,
        0,1,2,3,4,5,6,7,8,9},
    };
    if(0 == memcmp(test[0].end,heapSort(test[0].st, 10),sizeof(int) * 10))
    {
        printf("PASS! /n");
        printArray(test[0].st,10);
    }
    else
    {
        printf("FAILED! /n");
        printArray(test[0].st,10);
    }

}

int main()
{

    Test_1();

    return 0;
}

 

gdbserver 移植与多线程调试

  在嵌入式linux平台使用gdb调试进行远程调试需要安装gdbserver,gdbserver工作在目标板上,通过串口或者网线与主机上的gdb互联实现远程调试。

  Gdbserver需要根据不同的嵌入式平台来编译生成,首先到http://ftp.gnu.org/gnu/gdb/下载合适的版本。然后在本地进行编译。在Unbuntu下编译gdb需要安装ncurses 库,在redhat上通过yum install “Development tools” 安装依赖就可以了。

  首先编译主机端gdb,编译过程如下:

  解压源码包:

  $> tar xzvf gdb 7.3.1.tar.gz

  进入目录:

  $>cd gdb-7.3.1

  生成makefile文件:

  $>./configure –target=arm-linux –prefix=/mygdb7.3.1

或者,如果是mips平台

  $>./configure –target=mips-linux –prefix=/mygdb7.3.1

  $> make

  $> make install

  执行结束之后你就会在mygdb7.3.1文件夹下bin目录找到arm-linux-gdb 或者 mips-linux-gdb 可执行文件。

  注意:执行 configure 步骤的时候目录一定要选对,否则编译会失败,各种找到不到依赖!

  此外,由于这是生成在Linux主机上调试的可执行文件,因此不必使用交叉编译环境,换句话说在编译生成gdbserver的时候需要使用交叉编译器。

  接下来编译运行在目标板上的gdbserver。

  首先进入gdbserver目录(在gdb7.3.1目录中):

  $>cd gdb gdbserver

  生成makefile文件,这一步需要指定交叉编译器的位置,假设你交叉编译的位置在xx/yy目录下:

  $>CC=xx/yy/arm-linux-gcc ./configure  –target=arm-linux  –host=arm-linux 

  生成gdbserver

  $> make

  这里没有指定—prefix参数,因此生成的gdbserver就位于 gdb7.3.1/gdb/gdbserver目录下。

  现在可以将gdbserver移植到目标板中了,方法有很多,就看你的环境了,可以使用nfs,可以使用tftp等工具。

 

  进行调试:

  假设我们使用交叉编译器产生了一个helloworld可执行程序,在目标板上运行:

  $> gdbserver 192.168.1.100:2345 helloworld

  其中 192.168.1.100 是调试主机的地址,2345是调试端口,helloword是需要调试的可执行程序。

  随后在主机上运行:

  $> gdb helloworld

  $> target remote 192.168.1.10:2345

  其中 192.168.1.10 是目标板的地址,2345是gdbserver打开的用于创建调试连接的端口。

 

可能遇到的问题:

  1. 在调试实际模块的时候,设置了断点一运行就表现出各种找不到动态连接库(.so)

    可以这样设置:set solib-search-path PATH

         通过上面设置告诉gdb所以来的动态库在那里,其中PATH是被调试可执行程序所需的动态库的位置,多个不同路径可以使用“:”来隔开,这些路径一般都是你价差编译工具链的位置。

 

  2. 在调试多线程程序的时候目标板出现“gdb: error initializing thread_db library”“Child terminated with signal 5

    出现这个问题的原因有很多,有可能是你目标板上没有thread_db 库,但是也有可能是你使用的gdb版本过低不支持多线程调试(注意gdb7.0以下就不支持! 我当时一味的追求生成的文件小就使用gdb6.3 这个问题一直没有找到原因,折腾了一阵,最好也不要使用strip裁剪生成的可执行文件)。

 

  3. 编译gdb失败:提示在linux-low.c中“siginfo isn’t known

    进入到linux-low.c 中,找到相应函数(大概有两个函数),将 struct siginfo 全部换成为 siginfo_t。

 

  4. 多线程调试可以设置 set follow-fork-mode child/parent

    表示在多线程中产生新线程的时候gdb进入到子线程还是父线程。

 

Gdb多线程调试常用命令:

http://coolshell.cn/articles/3643.html

多线程调试可能是问得最多的。其实,重要就是下面几个命令:

  • info thread 查看当前进程的线程。
  • thread <ID> 切换调试的线程为指定ID的线程。
  • break file.c:100 thread all  在file.c文件第100行处为所有经过这里的线程设置断点。
  • set scheduler-locking off|on|step,这个是问得最多的。在使用step或者continue命令调试当前被调试线程的时候,其他线程也是同时执行的,怎么只让被调试程序执行呢?通过这个命令就可以实现这个需求。
    • off 不锁定任何线程,也就是所有线程都执行,这是默认值。
    • on 只有当前被调试程序会执行。
    • step 在单步的时候,除了next过一个函数的情况(熟悉情况的人可能知道,这其实是一个设置断点然后continue的行为)以外,只有当前线程会执行。

多线程死锁调试小技巧

  据说再高的高手在写多线程程序的时候都难确保不会产生死锁,死锁的调试也就成为一个比较常见的问题,假设有下面这样一个问题:

  一个正在生产环境下运行的进程死锁了,或者你只是在跑一个程序,并没有在调试器里面打开它,然后发现没有响应,日志输出也停止了。由于你是一个有经验的程序员,会想到“我刚刚加上了新的锁策略,不一定稳定,这可能是死锁了“。但是你不想就这么杀掉进程,因为多线程的 bug 不容易重现,遇上一次死锁可能要凭运气,错过了这次,它下次死锁可能会出现在你演示给老板看的时候……怎么办?

  对于这样的问题可以借助Core Dump来调试。

  什么是Core Dump?

  Core的意思是内存, Dump的意思是扔出来, 堆出来.开发和使用Unix程序时, 有时程序莫名其妙的down了, 却没有任何的提示(有时候会提示core dumped). 这时候可以查看一下有没有形如core.进程号的文件生成运行过程中发生异常, 程序异常退出时, 由操作系统把程序当前的内存状况存储在一个core文件中, 叫core dump.这个文件便是操作系统把程序down掉时的内存内容扔出来生成的, 它可以做为调试程序的参考.

  Core Dump又叫核心转储, 当程序没有core文件生成怎么办呢?

  有时候程序down了, 但是core文件却没有生成,core文件的生成跟你当前系统的环境设置有关系, 可以用下面的语句设置一下, 然后再运行程序便会生成core文件.

  ulimit -c unlimited

  core文件生成的位置一般于运行程序的路径相同, 文件名一般为core.进程号,在我的ubuntu12.04lts下生产的文件名为core。

  介绍了core dump之后,来看看如何在多线程调试中使用core dump。

  使用 kill 命令产生 core dump文件:

  kill -11 pid

  这不还是杀掉进程嘛?没错,但是你用信号11杀掉它,会让进程产生一个 Segmentation Fault,从而(如果你没禁用 core dump 的话),导致一个 core dump。随后你得到一个 core 文件,里面包含了死锁的时候,进程的内存镜像,也就包括了正在纠结缠绵,生离死别从而产生死锁的那两个,没准是几个,线程们的,栈。

  现在知道该怎么办了吧?用 gdb 打开这个 core 文件,然后

  thread apply all bt

  gdb 会打出所有线程的栈,如果你发现有那么几个栈停在 pthread_wait 或者类似调用上,大致就可以得出结论:就是它们几个儿女情长,耽误了整个进程。

  下面我来举一个简单的例子(为了代码尽量简单,使用了C++11的thread library)

#include <iostream>
#include <thread>
#include <mutex>
#include <chrono>
using namespace std;

mutex m1,m2;


void func_2()
{
    m2.lock();
    cout<< "about to dead_lock"<<endl;
    m1.lock();
    
}

void func_1()
{
    m1.lock();
    
    chrono::milliseconds dura( 1000 );// delay to trigger dead_lock
    this_thread::sleep_for( dura );
        
    m2.lock();
    
}


int main()
{

    thread t1(func_1);

    thread t2(func_2);
    
    t1.join();
    t2.join();
    return 0;

}

 

  编译代码

  $> g++ -Wall -std=c++11 dead_lock_demo.cpp -o dead_lock_demo -g -pthread

  运行程序,发现程序打印出“about to dead_lock” 就不动了,现在我们使用gdb来调试。注意gdb的版本要高于7.0,之前使用过gdb6.3调试多线程是不行的。

  在这之前需要先产生core dump文件:

  $> ps -aux | grep dead_lock_demo

  找出 dead_lock_demo 线程号,然后:

  $> kill -11 pid

  此时会生成core dump 文件,在我的系统上名字就是 core

  然后调试:

  $> gdb dead_lock_demo core

  $> thread apply all bt

  下面来看一下实际的过程:

多线程死锁调试小技巧

  

  从上图可以看出两个线程都阻塞在wait上,而且还给出了在哪一行代码中,很容易就定位到产生死锁的位置。

 

MySQL 存储过程/游标/事务

将会用到的几个表
mysql> DESC products;
+————+————–+——+—–+———+—————-+
| Field      | Type         | Null | Key | Default | Extra          |
+————+————–+——+—–+———+—————-+
| prod_id    | int(11)      | NO   | PRI | NULL    | auto_increment |
| vend_id    | int(11)      | YES  |     | NULL    |                |
| prod_name  | varchar(100) | YES  |     | NULL    |                |
| prod_price | int(11)      | YES  |     | NULL    |                |
| prod_desc  | varchar(300) | YES  |     | NULL    |                |
+————+————–+——+—–+———+—————-+
 
mysql> DESC orders;
+————+————-+——+—–+———+—————-+
| Field      | Type        | Null | Key | Default | Extra          |
+————+————-+——+—–+———+—————-+
| order_num  | int(11)     | NO   | PRI | NULL    | auto_increment |
| order_date | date        | YES  |     | NULL    |                |
| cust_id    | varchar(20) | YES  |     | NULL    |                |
+————+————-+——+—–+———+—————-+
 
mysql> DESC orderitems;
+————+————-+——+—–+———+—————-+
| Field      | Type        | Null | Key | Default | Extra          |
+————+————-+——+—–+———+—————-+
| order_num  | int(11)     | NO   | PRI | NULL    | auto_increment |
| order_item | varchar(20) | YES  |     | NULL    |                |
| prod_id    | varchar(20) | YES  |     | NULL    |                |
| quantity   | int(11)     | YES  |     | NULL    |                |
| item_price | int(11)     | YES  |     | NULL    |                |
+————+————-+——+—–+———+—————-+
 
创建存储过程:参数需要指定 OUT / IN / INOUT
 
CREATE PROCEDURE productpricing(
     OUT pl DECIMAL(8,2),
     OUT ph DECIMAL(8,2),
     OUT pa DECIMAL(8,2)
)
BEGIN
     SELECT Min( prod_price)
     INTO pl
     FROM products;
     SELECT Max( prod_price)
     INTO ph
     FROM products;
     SELECT Avg( prod_price)
     INTO pa
     FROM products;
END;
 
调用存储过程:
CALL productpricing( @pricelow, @pricehigh, @priceaverage);
 
选择返回的值:
SELECT @pricelow;
SELECT @pricelow,@pricehigh,@priceaverage  –选择多个
 
删除存储过程:
DROP PROCEDURE productpricing;
 
————————————————-
 
CREATE PROCEDURE ordertotal(
     INT onumber INT,
     OUT ototal DECIMAL(8,2)
)
BEGIN
     SELECT sum(item_price * quantity)
     FROM orderitems
     WHERE order_num = onumber
     INTO ototal;
END;
 
调用:
CALL ordertotal(20005, @total);
 
SELECT @total;
 
存储过程实际场景:需要获得以前一样的订单合计,但需要对合计增加营业税,不过只针对某些顾客,那么需要做:
1. 获得合计
2. 把营业税有田间的添加到合计
3. 返回合计(带或不带税)
 
CREATE PROCEDURE ordertotal(
IN onumber INT,
IN taxable BOOLEAN,
OUT octoal DECIMAL(8,2)
)
BEGIN
     — 注释 Declare variable for total
     DECLARE total DECIMAL(8,2);
     DECLARE taxrate INT DEFAULT 6;
 
     — Get the order total
     SELECT Sum( item_price * quantity)
     FROM orderitems
     WHERE order_num = onumber
     INTO total;
 
     — Is this taxable ?
     IF taxable THEN
          SELECT total + (tatal / 100 *taxrate) INTO total;
     END IF;
     
     SELECT total INTO ototal;
END;
     
CALL ordertotal(2005, 0, @total);
SELECT @total;
 
检查存储过程:
SHOW CREATE PROCEDURE ordertoal;
 
————————————————–
————————————————–
 
     SELECT 返回的是一个结果集,可能含有多行数据,有时候需要在检索出来的行中前进或后退一行或多行。这就是使用游标的原因。游标(CURSOR) 是一个存储在MySQL服务器上的数据库查询,它不是一条SELECT语句,而是被语句检索出来的结果集。在存储了游标之后应用程序可以根据需要滚动或浏览其中的数据。
     游标主要用于交互式应用,其中用户需要滚动屏幕上的数据,并对数据进行浏览或作出更改。
 
     MySQL游标只能用于存储过程。
使用游标的步骤:
1. 定义游标(针对某个SELECT语句)
2. 打开游标
3. 对填有数据的游标,根据需要取出各行
4. 关闭游标
 
简单示例:
CREATE PROCEDURE processorders()
BEGIN
     DECLARE ordernumbers CURSOR
     FOR
     SELECT order_num FROM orders;
 
     OPEN ordernumbers;
 
     CLOSE ordernumbers;
END;
—————- 使用游标数据
 
CREATE PROCEDURE processorders()
BEGIN
 
     DECLARE o INT;
     DECLARE ordernumbers CURSOR
     FOR
     SELECT order_num FROM orders;
 
     OPEN ordernumbers;
 
     FETCH ordernumbers INTO o;
 
     CLOSE ordernumbers;
END;
—————-循环检索数据
 
CREATE PROCEDURE processorders()
BEGIN
 
     DECLARE o INT;
     DECLARE done BOOLEAN DEFAULT 0;
 
     DECLARE ordernumbers CURSOR
     FOR
     SELECT order_num FROM orders;
 
     — Declare continue handler
     DECLARE CONTINUE HANDLER FOR SQLSTATE ‘02000’ SET done = 1;
     — SQLSTATE ‘02000’ 是一个未找到条件,当没有更多行可读的时候设置 done = 1 然后退出
 
     OPEN ordernumbers;
     REPEAT
 
          FETCH ordernumbers INTO o;
 
     UNTIL done END REPEAT;
 
     CLOSE ordernumbers;
END;
—————————————————–
—————————————————–
——使用table 记录CURSOR FETCH 出来的值
CREATE PROCEDURE processorders()
BEGIN
 
     DECLARE o INT;
     DECLARE done BOOLEAN DEFAULT 0;
     DECLARE t DECIMAL(8,2);
 
     DECLARE ordernumbers CURSOR
     FOR
     SELECT order_num FROM orders;
 
     — Declare continue handler
     DECLARE CONTINUE HANDLER FOR SQLSTATE ‘02000’ SET done = 1;
     — SQLSTATE ‘02000’ 是一个未找到条件,当没有更多行可读的时候设置 done = 1 然后退出
 
     — 创建table
     CREATE TABLE IF NOT EXISTS ordertotals(
          order_num INT, total DECIAML(8,2)
     );
 
     OPEN ordernumbers;
     REPEAT
 
          FETCH ordernumbers INTO o;
          CALL ordertotal(o,1,t); — 调用过程
 
          — 插入table
          INSERT INTO ordertotals(order_num, total)
          VALUES(o,t);
 
     UNTIL done END REPEAT;
 
     CLOSE ordernumbers;
END;
—————————————————–
—————————————————–
触发器:在事件发生的时候自动执行
创建触发器时,需要给出4条信息:
1.唯一的触发器名
2.触发器关联的表
3.触发器应该响应的活动(DELETE/ INSERT / UPDATE)
4.触发器何时执行
——————–
CREATE TRIGGER newproduct AFTER INSERT ON products FOR EACH ROW SELECT ‘Product added’;
 
–该例子触发器在每次插入之后显示 Product added 消息
 
—删除触发器
 
DROP TRIGGER newproduct;
 
————————————————–
————————————————–
事务处理( transaction processing) 可以用来维护数据库的完整性,它保证成批的MySQL操作要么完全执行,要么不执行。
几个术语:
事务:transaction 指一组SQL语句
回退:rollback 指撤销指定SQL语句过程
提交:commit 指将为存储的SQL语句结果写入数据库表
保留点:savepoint 指事务处理中设置的临时占位符,你可以对它发布退回
————-
SELECT * FROM ordertotals;
START TRANSACTION;
DELETE FROM ordertotals; –删除表
SELECT * FROM ordertotals; — 确认删除
ROLLBACK; — 回滚
SELECT * FROM ordertotal; — 再次显示
 
————–commit
一般的MySQL语句都是直接针对数据库表进行操作,进行隐含的提交,即提交操作是自动执行的。
在 事务处理中,提交不会隐含执行,需要使用COMMIT语句。
START TRANSACTION;
DELETE FROM orderitems WHERE order_num = 20010;
DELETE FROM orders WHERE order_num = 20010;
COMMIT;