终于见到OSD-Lyrics了

2009年9月17日 18:21

真是惭愧，直到今天才终于用上OSD-Lyrics

效果真是非常地赞，嘻嘻

自己只是写了个简单的搜狗歌词下载，连另一个歌词下载引擎：千千，都是tigersoldier给写的，艾...

.........................

要怎么办呢...

Tags:
Posted in Unix-C Programming | 2 Comments

unix编程学习路线图（转）

2009年6月11日 04:14

建议学习路径：

　　首先先学学编辑器，vim, emacs什么的都行。
然后学make file文件，只要知道一点就行，这样就可以准备编程序了。

　　然后看看《C程序设计语言》K&R，这样呢，基本上就可以进行一般的编程了，顺便找本数据结构的书来看。

　　如果想学习UNIX/LINUX的编程，《APUE》绝对经典的教材，加深一下功底，学习《UNP》的第二卷。这样基本上系统方面的就可以掌握了。

　　然后再看Douglus E. Comer的《用TCP/IP进行网际互连》第一卷，学习一下网络的知识，再看《UNP》的第一卷，不仅学习网络编程，而且对系统编程的一些常用的技巧就很熟悉了，如果继续网络编程，建议看《TCP/IP进行网际互连》的第三卷，里面有很多关于应用协议telnet、ftp等协议的编程。
如果想写设备驱动程序，首先您的系统编程的接口比如文件、IPC等必须要熟知了，再学习《LDD》2。

　　对于几本经典教材的评价：

　　《The C Programing Language》K&R 经典的C语言程序设计教材，作者是C语言的发明者，教材内容深入浅出。虽然有点老，但是必备的一本手册，现在有时候我还常翻翻。篇幅比较小，但是每看一遍，就有一遍的收获。另外也可用谭浩强的《C语言程序设计》代替。

　　《Advanced Programing in Unix Envirement》 W.Richard Stevens：也是非常经典的书（废话，Stevens的书哪有不经典的！），虽然初学者就可以看，但是事实上它是《Unix Network Programing》的一本辅助资料。国内的翻译的《UNIX环境高级编程》的水平不怎么样，现在有影印版，直接读英文比读中文来得容易。

　　《Unix Network Programing》W.Richard Stevens：第一卷讲BSD Socket网络编程接口和另外一种网络编程接口的，不过现在一般都用BSD Socket，所以这本书只要看大约一半多就可以了。第二卷没有设计到网络的东西，主要讲进程间通讯和Posix线程。所以看了《APUE》以后，就可以看它了，基本上系统的东西就由《APUE》和《UNP》vol2概括了。看过《UNP》以后，您就会知道系统编程的绝大部分编程技巧，即使卷一是讲网络编程的。国内是清华翻译得《Unix网络编程》，翻译者得功底也比较高，翻译地比较好。所以建议还是看中文版。

　　《TCP/IP祥解》一共三卷，卷一讲协议，卷二讲实现，卷三讲编程应用。我没有怎么看过。，但是据说也很经典的，因为我没有时间看卷二，所以不便评价。

　　《用TCP/IP进行网际互连》Douglus.E.Comer 一共三卷，卷一讲原理，卷二讲实现，卷三讲高级协议。感觉上这一套要比Stevens的那一套要好，就连Stevens也不得不承认它的第一卷非常经典。事实上，第一卷即使你没有一点网络的知识，看完以后也会对网络的来龙去脉了如指掌。第一卷中还有很多习题也设计得经典和实用，因为作者本身就是一位教师，并且卷一是国外研究生的教材。习题并没有答案，留给读者思考，因为问题得答案可以让你成为一个中级的Hacker，这些问题的答案可以象Douglus索取，不过只有他只给教师卷二我没有怎么看，卷三可以作为参考手册，其中地例子也很经典。如果您看过Qterm的源代码，就会知道Qterm的telnet 实现部分大多数就是从这本书的源代码过来的。对于网络原理的书，我推荐它，而不是Stevens的《TCP/IP祥解》。

　　《Operating System - Design and Implement》这个是讲操作系统的书，用Minix做的例子。作者母语不是英文，所以英文看起来比较晦涩。国内翻译的是《操作系统设计与实现》，我没看过中文版，因为翻译者是尤晋元，他翻译的《APUE》已经让我失望头顶了。读了这本书，对操作系统的底层怎么工作的就会
有一个清晰的认识。

　　《Linux Device Driver》2e ，为数不多的关于Linux设备驱动程序的好书。不过内容有些杂乱，如果您没有一些写驱动的经验，初次看会有些摸不着南北。国内翻译的是《Linux设备驱动程序》第二版，第一版，第二版的译者我都有很深的接触，不过总体上来说，虽然第二版翻译的有些不尽人意，但是相比第一版来说已经超出了一大截。要读这一本书，至少应该先找一些《计算机原理》《计算机体系结构》的书来马马虎虎读读，至少应该对硬件和计算机的工作过程有一些了解。

Tags:
Posted in Unix-C Programming | 0 Comments

GNU Profiler(GProf): 度量程序性能

2009年6月08日 23:38

<<程序设计实践>>：

“使用轮廓程序。除了可靠的计时方法外，在性能分析中最重要的工具就是一种能产生轮廓文件的系统。轮廓文件是对程序在哪些地方消耗了时间的一种度量。在有些轮廓文件中列出了执行中调用的各个函数、各函数被调用的次数以及它们消耗的时间在整个执行中的百分比。另一些轮廓文件计算每个语句执行的次数。执行非常频繁的语句通常对总运行时间的贡献比较大，根本没执行的语句所指明的可能是些无用代码，或者是没有合理测试到的代码。轮廓文件是一种发现程序中执行热点的有效手段，所谓热点就是那些消耗了大部分计算时间的函数或者代码段。当然，对轮廓文件的解释也应该慎重。由于编译程序本身的复杂性、缓冲存储器和主存的复杂影响，还有做程序的轮廓文件对其本身执行所造成的影响等，轮廓文件的统计信息只能看作是近似的.轮廓文件常常可以通过编译系统的一个标志或选择项打开，然后运行程序，最后用一个分析工具显示结果。在U n i x上，这个标志一般是- p，对应的工具是p r o f“

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

来源:

blog.csdn.net/lengxingfei/archive/2006/01/20/584889.aspx

在优化程序的时候，要记住：在值得优化的地方优化！没有必要花上几个小时来优化一段实际上只运行0.04秒的程序。

GProf 使用了一种异常简单但是非常有效的方法来优化C/C++ 程序，而且能很容易的识别出值得优化的代码。一个简单的案例分析将会显示，GProf如何通过识别并优化两个关键的数据结构，将实际应用中的程序从3分钟的运行时优化到5秒的。

这个程序最早可以追溯到1982年关于编译器构建的特别讨论大会（the SIGPLAN Symposium on Compiler Construction）。现在这个程序成了各种UNIX 平台上的一个标准工具。

_________________ _________________ _________________

Profiling in a nutshell

程序概要分析的概念非常简单：通过记录各个函数的调用和结束时间，我们可以计算出程序的最大运行时的程序段。这种方法听起来似乎要花费很多气力——幸运的是，我们其实离真理并不远！我们只需要在用 gcc 编译时加上一个额外的参数('-pg')，运行这个（编译好的）程序（来搜集程序概要分析的有关数据），然后运行'gprof'以更方便的分析这些结果。

案例分析: Pathalizer

我使用了一个现实中使用的程序来作为例子，是pathalizer的一部分: 即 event2dot，一个将路径“事件”描述文件转化为图形化“dot”文件的工具（executable which translates a pathalizer 'events' file to a graphviz 'dot' file）。

简单的说，它从一个文件里面读取各种事件，然后将它们分别保存为图像(以页为节点，且将页与页之间的转变作为边），然后将这些图像整合为一张大的图形，并保存为图形化的'dot'格式文件。

给程序计时

先让我们给我们未经优化的程序计一下时，看看它们的运行要多少时间。在我的计算机上使用event2dot并用源码里的例子作为输入（大概55000的数据），大致要三分多钟:

real    3m36.316s
user    0m55.590s
sys     0m1.070s

程序分析

要使用gprof 作概要分析，在编译的时候要加上'-pg' 选项，我们就是如下重新编译源码如下：

g++ -pg dotgen.cpp readfile.cpp main.cpp graph.cpp config.cpp -o event2dot

现在我们可以再次运行event2dot，并使用我们前面使用的测试数据。这次我们运行的时候，event2dot运行的分析数据会被搜集并保存在'gmon.out'文件中，我们可以通过运行'gprof event2dot | less'来查看结果。

gprof 会显示出如下的函数比较重要：

 % cumulative  self              self     total
 time seconds  seconds  calls s/call s/call name
43.32   46.03  46.03 339952989  0.00  0.00 CompareNodes(Node *,Node *)
25.06   72.66  26.63    55000   0.00  0.00 getNode(char *,NodeListNode *&)
16.80   90.51  17.85 339433374  0.00  0.00 CompareEdges(Edge *,AnnotatedEdge *)
12.70  104.01  13.50    51987   0.00  0.00 addAnnotatedEdge(AnnotatedGraph *,Edge *)
 1.98  106.11   2.10    51987   0.00  0.00 addEdge(Graph *,Node *,Node *)
 0.07  106.18   0.07        1   0.07  0.07 FindTreshold(AnnotatedEdge *,int)
 0.06  106.24   0.06        1   0.06 28.79 getGraphFromFile(char *,NodeListNode *&,Config *)
 0.02  106.26   0.02        1   0.02 77.40 summarize(GraphListNode *,Config *)
 0.00  106.26   0.00    55000   0.00  0.00 FixName(char *)

可以看出，第一个函数比较重要: 程序里面绝大部分的运行时都被它给占据了。

优化

上面结果可以看出，这个程序大部分的时间都花在了CompareNodes函数上，用 grep 查看一下则发现CompareNodes 只是被 CompareEdges调用了一次而已, 而CompareEdges则只被 addAnnotatedEdge调用——它们都出现在了上面的清单中。这儿就是我们应该做点优化的地方了吧！

我们注意到addAnnotatedEdge遍历了一个链表。虽然链表是易于实现，但是却实在不是最好的数据类型。我们决定将链表 g->edges 用二叉树来代替: 这将会使得查找更快。

结果

现在我们看一下优化后的运行结果:

real    2m19.314s
user    0m36.370s
sys     0m0.940s

第二遍

再次运行 gprof 来分析:

%   cumulative self           self    total
 time   seconds seconds calls  s/call  s/call name
87.01     25.25  25.25  55000    0.00    0.00 getNode(char *,NodeListNode *&)
10.65     28.34   3.09  51987    0.00    0.00 addEdge(Graph *,Node *,Node *)

看起来以前占用大量运行时的函数现在已经不再是占用运行时的大头了！我们试一下再优化一下呢：用节点哈希表来取代节点树。

这次简直是个巨大的进步:

real    0m3.269s
user    0m0.830s
sys     0m0.090s

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

另外，还可以参考：

使用 GNU profiler 来提高代码运行速度

寻找应用程序中占用时间最长的部分

www.ibm.com/developerworks/cn/linux/l-gnuprof.html

Tags: gprof
Posted in Unix-C Programming | 0 Comments

APUE 线程私有数据与errno的实现

2009年5月19日 23:54

线程私有数据

每个线程可以独立地访问数据副本，而不需要担心与其他线程的同步访问问题。

它提供了让基于进程的接口适应多线程环境的机制，一个很明显的实例就是errno。为了让线程也能够使用那些原本基于进程的系统调用和库例程，errno被重新定义为线程私有数据。这样，一个线程设置errno的操作并不会影响进程中其他线程的errno值。

#include<pthread.h>

int pthread_key_create(pthread_key_t *keyp, void (*destructor)(void *));

“键”可以被进程中的所有线程使用，而每个线程把这个键与不同的线程私有数据地址进行关联，这就是其基本原理。

errno的定义

在<errno.h>头文件中：

/* Declare the `errno' variable, unless it's defined as a macro by
bits/errno.h. This is the case in GNU, where it is a per-thread
variable. This redeclaration using the macro still works, but it
will be a function declaration without a prototype and may trigger
a -Wstrict-prototypes warning. */
#ifndef errno
extern int errno;
#endif

在<bits/errno.h>头文件中：

# ifndef __ASSEMBLER__
/* Function to get address of global `errno' variable. */
extern int *__errno_location (void) __THROW __attribute__ ((__const__));

# if !defined _LIBC || defined _LIBC_REENTRANT
/* When using threads, errno is a per-thread value. */
# define errno (*__errno_location ())
# endif
# endif /* !__ASSEMBLER__ */

errno实际上，并不是我们通常认为的是个整型数值，而是通过整型指针来获取值的。这个整型就是线程安全的。

另外，宏之所以这样实现，是因为标准库规定了必须能够通过&errno方式取得保存错误代码的变量的地址，因此__errno_location()函数的返回值是指针，并把宏定义为解引用函数返回的地址*__errno_location()。如果__errno_location直接返回int类型，此时就无法取得保存错误代码的变量的地址。

errno的可能实现

#include<stdlib.h>
#include<pthread.h>

static pthread_key_t key;
static pthread_once_t init_done = PTHREAD_ONCE_INIT;

static void
thread_init(void)
{
pthread_key_create(&key, free);
}

int *
__errno_location_simply_fake(void)
{
int *errp;

/* 保证多线程环境里 key 只被创建一次 */
pthread_once(&init_done, thread_init);

errp = (int *)pthread_getspecific(key);
if(errp == NULL) {
errp = malloc(sizeof(int));
if(errp != NULL)
pthread_setspecific(key, errp);
}

return errp;
}

参考:

1. 《APUE》第12.6节线程私有数据

2. blog.csdn.net/romandion/archive/2008/01/11/2036975.aspx

3. bbs.chinaunix.net/viewthread.php

Tags: APUE errno 线程私有数据
Posted in Unix-C Programming | 1 Comments

linux errno code

2009年5月16日 01:07

来源: blog.csdn.net/wei801004/archive/2007/03/05/1521100.aspx

   124 EMEDIUMTYPE   Wrong medium type
   123 ENOMEDIUM     No medium found
   122 EDQUOT        Disk quota exceeded
   121 EREMOTEIO     Remote I/O error
   120 EISNAM        Is a named type file
   119 ENAVAIL       No XENIX semaphores available
   118 ENOTNAM       Not a XENIX named type file
   117 EUCLEAN       Structure needs cleaning
   116 ESTALE        Stale NFS file handle
   115 EINPROGRESS +Operation now in progress
   114 EALREADY      Operation already in progress
   113 EHOSTUNREACH No route to host
   112 EHOSTDOWN     Host is down
   111 ECONNREFUSED Connection refused
   110 ETIMEDOUT    +Connection timed out
   109 ETOOMANYREFS Too many references: cannot splice
   108 ESHUTDOWN     Cannot send after transport endpoint shutdown
   107 ENOTCONN      Transport endpoint is not connected
   106 EISCONN       Transport endpoint is already connected
   105 ENOBUFS       No buffer space available
   104 ECONNRESET    Connection reset by peer
   103 ECONNABORTED Software caused connection abort
   102 ENETRESET     Network dropped connection on reset
   101 ENETUNREACH   Network is unreachable
   100 ENETDOWN      Network is down
    99 EADDRNOTAVAIL Cannot assign requested address
    98 EADDRINUSE    Address already in use
    97 EAFNOSUPPORT Address family not supported by protocol
    96 EPFNOSUPPORT Protocol family not supported
    95 EOPNOTSUPP    Operation not supported
    94 ESOCKTNOSUPPORT Socket type not supported
    93 EPROTONOSUPPORT Protocol not supported
    92 ENOPROTOOPT   Protocol not available
    91 EPROTOTYPE    Protocol wrong type for socket
    90 EMSGSIZE     +Message too long
    89 EDESTADDRREQ Destination address required
    88 ENOTSOCK      Socket operation on non-socket
    87 EUSERS        Too many users
    86 ESTRPIPE      Streams pipe error
    85 ERESTART      Interrupted system call should be restarted
    84 EILSEQ        Invalid or incomplete multibyte or wide character
    83 ELIBEXEC      Cannot exec a shared library directly
    82 ELIBMAX       Attempting to link in too many shared libraries
    81 ELIBSCN       .lib section in a.out corrupted
    80 ELIBBAD       Accessing a corrupted shared library
    79 ELIBACC       Can not access a needed shared library
    78 EREMCHG       Remote address changed
    77 EBADFD        File descriptor in bad state
    76 ENOTUNIQ      Name not unique on network
    75 EOVERFLOW     Value too large for defined data type
    74 EBADMSG      +Bad message
    73 EDOTDOT       RFS specific error
    72 EMULTIHOP     Multihop attempted
    71 EPROTO        Protocol error
    70 ECOMM         Communication error on send
    69 ESRMNT        Srmount error
    68 EADV          Advertise error
    67 ENOLINK       Link has been severed
    66 EREMOTE       Object is remote
    65 ENOPKG        Package not installed
    64 ENONET        Machine is not on the network
    63 ENOSR         Out of streams resources
    62 ETIME         Timer expired
    61 ENODATA       No data available
    60 ENOSTR        Device not a stream
    59 EBFONT        Bad font file format
    57 EBADSLT       Invalid slot
    56 EBADRQC       Invalid request code
    55 ENOANO        No anode
    54 EXFULL        Exchange full
    53 EBADR         Invalid request descriptor
    52 EBADE         Invalid exchange
    51 EL2HLT        Level 2 halted
    50 ENOCSI        No CSI structure available
    49 EUNATCH       Protocol driver not attached
    48 ELNRNG        Link number out of range
    47 EL3RST        Level 3 reset
    46 EL3HLT        Level 3 halted
    45 EL2NSYNC      Level 2 not synchronized
    44 ECHRNG        Channel number out of range
    43 EIDRM         Identifier removed
    42 ENOMSG        No message of desired type
    40 ELOOP         Too many levels of symbolic links
    39 ENOTEMPTY    +Directory not empty
    38 ENOSYS       +Function not implemented
    37 ENOLCK       +No locks available
    36 ENAMETOOLONG +File name too long
    35 EDEADLK      +Resource deadlock avoided
    34 ERANGE       +Numerical result out of range
    33 EDOM         +Numerical argument out of domain
    32 EPIPE        +Broken pipe
    31 EMLINK       +Too many links
    30 EROFS        +Read-only file system
    29 ESPIPE       +Illegal seek
    28 ENOSPC       +No space left on device
    27 EFBIG        +File too large
    26 ETXTBSY       Text file busy
    25 ENOTTY       +Inappropriate ioctl for device
    24 EMFILE       +Too many open files
    23 ENFILE       +Too many open files in system
    22 EINVAL       +Invalid argument
    21 EISDIR       +Is a directory
    20 ENOTDIR      +Not a directory
    19 ENODEV       +No such device
    18 EXDEV        +Invalid cross-device link
    17 EEXIST       +File exists
    16 EBUSY        +Device or resource busy
    15 ENOTBLK       Block device required
    14 EFAULT       +Bad address
    13 EACCES       +Permission denied
    12 ENOMEM       +Cannot allocate memory
    11 EAGAIN       +Resource temporarily unavailable
    10 ECHILD       +No child processes
     9 EBADF        +Bad file descriptor
     8 ENOEXEC      +Exec format error
     7 E2BIG        +Argument list too long
     6 ENXIO        +No such device or address
     5 EIO          +Input/output error
     4 EINTR        +Interrupted system call
     3 ESRCH        +No such process
     2 ENOENT       +No such file or directory
     1 EPERM        +Operation not permitted
#    0 --            Success

Tags: errno
Posted in Unix-C Programming | 1 Comments

僵死进程

2009年5月11日 02:56

APUE 第8章:

如果子进程在父进程之前终止，那么父进程又如何能在做相应检查时得到子进程的终止状态呢？

对此问题的回答是：内核为每个终止子进程保存了一定量的信息，所以当父进程调用wait或者waitpid时，可以得到这些信息，这些信息至少包括进程ID，终止状态，以及该进程使用的CPU时间总量。内核可以释放终止进程所使用的所有存储区，关闭其所有打开的流等。

一个已经终止，但是其父进程尚未对其进行善后处理（获取终止子进程的有关信息等）的进程被称为僵死进程(zombie)

想到的一个问题就是：终止子进程处于僵死进程直到什么时候为止？

于是google之：

来源: blogs.sun.com/haifeng/entry/unix_%E5%83%B5%E6%AD%BB_zombie_%E8%BF%9B%E7%A8%8B1

进程在它的生命周期有几种状态：睡眠，可运行，停止，正在运行和僵死状态。所谓僵死进程，指的是一个进程已经退出，它的内存和相关的资源已经被内核释放掉，但是在进程表中这个进程项（entry）还保留着，以便它的父进程得到它的退出状态。一个进程退出时，它的父进程会收到一个SIGCHLD信号。一般情况下，这个信号的句柄通常执行wait系统调用，这样处于僵死状态的进程会被删除。如果父进程没有这么做，结果是什么呢？毫无疑问，进程会处于僵死状态。实际上，僵死进程不会对系统有太大的伤害，最多就是它的进程号(PID)和进程表中的进程项系统不能使用。(感觉这里说的更加清楚，难道是中文版翻译的不行呵呵）

去掉僵尸进程

在Solaris中，可以用ptree命令列出所有进程，查找进程名称为“defunct”的进程。如果发现了，那么系统存在僵死进程。注意用kill命令不能杀死这种进程。原因是它已经退出了，什么也没有了，自然无法收到任何信号。

删除僵尸进程的根本方法是让它的父进程调用wait来处理SIGCHLD信号。有两种方式可以做到这一点。一种方法是改变它的父进程。可以用kill命令杀死它的父进程，这样init变成它的新的父进程，而init会定时地执行wait系统调用。另一种方式是使用调试器，在父进程中执行wait系统调用。如果知道了父进程的程序名称和它的进程号，运行下面命令：

   %gdb `parent application name` `parent pid`
   (gdb) set unwindonsignal on
   (gdb) call wait(pid of zombie process)

gdb会在父进程中调用wait，从而达到我们的目的。注意，unwindonsignal要被set为on, 它告诉gdb把堆栈恢复到调用wait之前的状态。要不然父进程会crash。在程序中避免僵死进程除了显式调用wait或waitpid外，也可以使用下面的代码来避免僵死进程（这儿假设父进程对子进程的状态不感兴趣），它遵循POSIX，是可移植的。

   struct sigaction sa;
   sa.sa_handler = SIG_IGN;
   sa.sa_flags = SA_NOCLDWAIT;
   sigemptyset (&sa.sa_mask);
   sigaction (SIGCHLD, &sa, NULL);

参考exit(2)手册页。

来源: www.chinaunix.net/jh/4/665906.html

一、僵屍進程的産生

当子进程比父进程先运行结束，而父进程没有回收子进程的时候，子进程将成为一个僵尸进程。如果父进程先退出，子进程被init接管，子进程退出后init会回收，就没事了。

二、僵屍進程的危害

僵尸进程是一个运行完毕的进程，所有资源都已经释放了，除了它的进程表项。因此，导致的影响如下：如果操作系统最多能管理1000个进程，那么僵尸进程的存在，将会使得操作系统管理正常进程减少。

三、如何避免僵屍進程的産生

1、父进程通过wait和waitpid等函数等待子进程结束，这会导致父进程挂起

2. 如果父进程很忙，那么可以用signal函数为SIGCHLD安装handler，因为子进程结束后，父进程会收到该信号，可以在handler中调用wait回收

3. 如果父进程不关心子进程什么时候结束，那么可以用signal（SIGCHLD, SIG_IGN）通知内核，自己对子进程的结束不感兴趣，那么子进程结束后，内核会回收，并不再给父进程发送信号

4. 还有一些技巧，就是fork两次(APUE有介绍)，父进程fork一个子进程，然后继续工作，子进程fork一个孙进程后退出，那么孙进程被init接管，孙进程结束后，init会回收。不过子进程的回收估计还要自己做。

Tags: APUE zombie
Posted in Unix-C Programming | 1 Comments

数组的不对称边界

2009年5月06日 02:53

/**
* @file bsearch.c
* @brief binary search,
* C Traps and Pitfalls, P132
* 主题: 数组的不对称边界
* lower与higher是不对称边界的两头，即lower<=k<higher
* 可以表示为[lower, higher)
* 这样表示的效果:
* 1. 取值范围的元素个数就是上界与下界之差
* 2. 如果上界等于下界，那么取值范围为空
* 3. 即使取值范围为空，上界也永远不可能小于下界
*
* 设mid = (lower+higher)/2
* 若target小于下标为mid的元素，取higher=mid，表示mid是位于可能范围以外的最小下标
* 若target大于下标为mid的元素，取lower=mid+1，表示mid+1是位于可能范围内的最小下标
* lower==higer的时候，表示可能范围为空，可判定target不存在
*
* @author simplyzhao
* @version 0.0
* @date 2009-05-05
*/

#include<stdio.h>
#include<stdlib.h>
/**
* @brief 数组版本
*
* @param arr[]
* @param length
* @param target
*
* @return 返回指向目标元素的指针，不存在则返回NULL
*/
int *bsearch_arr(int arr[], int length, int target)
{
int lower = 0;
int higher = length; /* 这里higher取的是length，而不是length-1 */
int mid;

while(lower < higher) {
mid = (lower+higher)/2; /* 这里的除法运算可以替代为: (lower+higher)>>1, 当然前提是lower+higher非负 */
if(arr[mid] > target)
higher = mid;
else if(arr[mid] < target)
lower = mid+1;
else
return arr+mid;
}

return NULL;
}

/**
* @brief 指针版本
*
* @param arr
* @param length
* @param target
*
* @return
*/
int *bsearch_ptr(int *arr, int length, int target)
{
int *lower = arr;
/* 可以使用数组“溢界”元素的地址，这个地址可以用于赋值和比较，当然解引用肯定是非法的 */
int *higher = arr+length;
int *mid;

while(lower < higher) {
mid = lower + ((higher-lower) >> 1); /* 注意：这里指针不能进行相加运算 */
if(*mid > target)
higher = mid;
else if(*mid < target)
lower = mid+1;
else
return mid;
}

return NULL;
}

Tags:
Posted in Unix-C Programming | 0 Comments

可变参数的实现原理

2009年5月04日 05:32

/**
* @brief 理解varargs.h的实现，虽然该头文件
* 在GUN C库中已经被stdarg.h取代，但对于理解可变参数的实现
* 以及参数传递机制还是非常有学习价值
*
* 参考《C陷阱与缺陷》，附录
* @date 2009-05-03
*/

#include<stdio.h>

typedef char *v_list;
#define v_dcl int v_alist;
#define v_start(list) list=(char *)&v_alist
#define v_end(list)
#define v_arg(list,mode) \
((mode *)(list+=sizeof(mode)))[-1]

/*
* 假定:
* 底层的C语言实现要求函数参数在内存中连续存储
* 这样，但我们知道当前参数的地址，就能依次访问参数列表中的其他参
*/

void
test_arg(v_alist) v_dcl
{
v_list ap;
v_start(ap);

char ch;
printf("ap: %p\n", ap);
/*
   * 陷阱
   * v_arg宏的第二个参数不能被指定为char, short, float
   * 因为char 和 short 参数将被转换为 int 类型, 而float 参数会被转换为 double
   */
ch = v_arg(ap, int);
printf("%c\n", ch);

int i;
printf("ap: %p\n", ap);
i = v_arg(ap, int);
printf("%d\n", i);

double d;
printf("ap: %p\n", ap);
d = v_arg(ap, double);
printf("%f\n", d);

char *p;
printf("ap: %p\n", ap);
p = v_arg(ap, char *);
printf("%s\n", p);

v_end(ap);
}

int
main(int argc, char *argv[])
{
char ch;
int i;
double d;
char *p;
ch = 'z';
i = 1;
d = 3.5;
p = "simplyzhao";
test_arg(ch, i, d, p);
return 0;
}

输出:

simplyzhao@Full-House:~$ gcc test.c
simplyzhao@Full-House:~$ ./a.out
ap: 0xbf8f8530
z
ap: 0xbf8f8534
1
ap: 0xbf8f8538
3.500000
ap: 0xbf8f8540
simplyzhao

ps.

发现stdarg.h头文件并不在/usr/include目录下，不知何解?

simplyzhao@Full-House:~$ locate stdarg.h
/usr/include/c++/4.3/tr1/stdarg.h
/usr/lib/gcc/i486-linux-gnu/4.3/include/stdarg.h

Tags: varargs.h 可变参数
Posted in Unix-C Programming | 1 Comments

终于把APUE看完一遍

2009年5月02日 22:54

还是挺有成就感的，虽然只是把这本经典书看了一遍，书中的例子基本敲了一遍。

翻看之前的blog记录，在2月28日有一篇：学习计划Unix-C，其中写着想看的几本关于Unix下C编程的书，原本打算是今年暑假看完的，没想到现在已经看的差不多了，还剩一本《C陷阱与缺陷》，目前正在看，很薄的一本书，都不敢看得太快，否则没几天又看完了嘻嘻。

当然，还仅限于把书看完的程度而已，与掌握相比还有相当大的距离。可以说，看完第一遍，只是对于一些基本的系统调用与函数有了感性的认识，真正想要掌握和灵活地运用，关键还是在于多实践，光看书却不实践，是没法真正提高水平的。

接下来，准备把APUE再仔细地翻看一遍，第一遍看的时候有很多地方有疑惑，对于某些章节特别是信号以及线程的内容还不能理解透彻，第二遍打算看得仔细点，速度放慢点，另外把每一章的课后习题也好好钻研钻研。

总之，继续努力吧，Fighting...

另外，要说大四有什么好的话，对于我来说，那就是有充足的时间来学习自己感兴趣的东西

我的大四，过得很充实...

ps.

前几天在写下载歌词的小程序时，突然发觉自己挺喜欢编程的呵呵。

想当初，从历史系转过来的时候，只是想着计算机系至少是个理科，并没有想到究竟自己喜不喜欢这个专业，现在看来，挺适合我的。

Tags: APUE
Posted in Unix-C Programming | 7 Comments

doxygen+VIM文档实用指南for C/C-liked Programmers

2009年5月02日 08:56

好文啊，忍不住就又拷贝过来了呵呵

来源: blog.csdn.net/clarkZHUO/archive/2006/12/31/1471573.aspx

再次感谢原文作者，

摘要：

文档撰写是一项十分繁琐而且费力的工作，相信已经有很多人对此深感头痛。文档生成工具的出现最大限度地帮助程序员解决了这个问题，这些工具通常可以从程序源代码自动生成文档，大大方便了文档工作。这篇小东西主要介绍了如何用VIM和doxygen来快速生成注释，并用最少的额外劳动来完成专业水准的程序文档的过程。仅供参考，如有雷同，纯属巧合。

关键字：

doxygen vim doxygentoolkit chm dot lex CLanuageScanner

Tags: doxygen vim doxygentoolkit
Posted in Unix-C Programming | 1 Comments

终于见到OSD-Lyrics了

unix编程学习路线图（转）

GNU Profiler(GProf): 度量程序性能

Profiling in a nutshell

案例分析: Pathalizer

给程序计时

程序分析

优化

结果

第二遍

使用 GNU profiler 来提高代码运行速度

APUE 线程私有数据与errno的实现

linux errno code

僵死进程

数组的不对称边界

可变参数的实现原理

终于把APUE看完一遍

doxygen+VIM文档实用指南for C/C-liked Programmers

分类

链接

功能

Profiling in a nutshell

案例分析: Pathalizer

给程序计时

程序分析

优化

结果

第二遍

使用 GNU profiler 来提高代码运行速度

分类

标签云

链接

功能