- 博客(115)
- 资源 (3)
- 收藏
- 关注
RSS订阅原创 链接 加载
实验程序：$ cat SimpleSection.cint printf(const char* format,...);int globa_init_var = 84;int global_uninit_val;void func1(int i){ printf("%d\n",i);}int main(){ static int static_va
2016-10-17 20:33:56
1462
1
原创 求职记-迷茫&思考
开始找工作了，可以说有足够的自信，也有足够的压力，甚至是迷茫。我想每个过来人都有过同样的经历吧。只要把眼光放长远一两个月，现在的迷茫自然烟消云散。我倒是更珍惜当前的压力，压力迫使自己进行更深入的思考，这种思考比以往都要深刻，暴漏的问题也更隐蔽，这也是提高自己的绝佳机会。想对自己说的是不要忘记自己当初为什么努力，付出多少就能得到多少！ 等找完工作之后，再来详细记录这段时间的迷茫和思考。。。。。。——
2016-09-14 14:21:09
732
原创 CopyOnWriteArrayList与java内存模型
关于CopyOnWriteArrayList的介绍可以参考之前文章中的CopyOnWriteArrayList、CopyOnWriteArraySet（其中分析了它的特点以及适合的使用场景，建议看一下）。本文原本是打算分析CopyOnWriteArrayList的源码的，结果看了一下其源码实现比较简单，只是有一个地方很难理解。本文就只探讨这个点。相关代码如下： /** The array,
2016-08-21 16:34:57
836
1
原创 一个全新的视角来看KMP算法（简单！形象！）
前面《字符串匹配》中我们介绍了KMP算法，《KMP算法Java实现》中给出了KMP算法的实现。KMP算法很多人都说难，我第一次从《算法导论》中看到的时候也觉得难，后来重看算导时自己推导了一遍，觉得不难了，但是还是感觉印象不深，推导过后一段时间又会很模糊，下次遇到又得重新推。KMP算法原理上并不难，但是之所以给人难的感觉是因为它不够直观。今天突发奇想想到了一种将KMP算法图形化的方法，我
2016-07-23 09:53:18
1493
原创 数据结构：数组+链表（巧妙！）
数组+链表这种数据结构在《HashMap源码分析》一文中以及在之前分析Linux内核源码的过程中多次碰到，本篇文章专门探讨这种数据结构。数组与链表各自的优缺点大家肯定都很熟悉了，而数组+链表这种数据结构其实是综合了二者之间的优点，这类似于A*算法综合了广度优先搜索算法与贪心算法的优点一样，这种思想应用比较广，一定要掌握。再举个例子，比如我们知道遗传算法收敛速度比较慢，但是爬山法的收敛速
2016-07-18 19:12:37
19830
原创 LinkedHashMap源码分析
26 package java.util; 27 import java.io.*;147 public class LinkedHashMap148 extends HashMap149 implements Map150 {151 152 private static final long serialVersionUID = 380
2016-07-18 10:48:03
721
原创 拓扑排序实例
在前面的文章《深度优先搜索》中介绍了拓扑排序，这里看两道相关题目1.Course ScheduleThere are a total of n courses you have to take, labeled from 0 ton - 1.Some courses may have prerequisites, for example to take course 0 y
2016-03-09 10:31:47
2727
原创 LUP分解求解线性方程组及求逆矩阵 java
具体的分析参考算法导论public class LU{ /**矩阵相乘*/ public static float[][] multiply(float[][]A,float[][]B){ int n = A[0].length,i = 0,j = 0,k = 0; float[][] C = new float[n][n]; for(i = 0;i < n;i++)
2015-11-22 19:07:50
3874
1
原创 寻找最近点对
本文是关于在n>=2个点的集合Q中寻找最近点对的问题。容易想到的暴力手段，需要遍历theta(n^2)个点对，效率不高。本文中给出一种时间复杂度为O(nlgn)的算法，算法采用分治策略。下面具体描述：输入为P、X和Y，其中P是Q的子集，数组X包含P的所有点，并按照x坐标单调递增，同样Y中的点按照y坐标排序。为了维持O(nlgn)的时间界，不能在每次递归调用中都排序，否则运行时间递归式就
2015-11-16 15:26:11
446
原创 KMP算法Java实现
之前的文章《字符串匹配》中介绍了KMP算法，下面给出其Java实现。public class KMP{ static final int MAX = 100; static int[] pi = new int[MAX]; //第一种方法 /** 思路：遍历T中的每一个字符，如果与P中的匹配，则二者游标递增，增到P的长度说明已经匹配，返回true * 如果不匹配，分两种情况
2015-10-25 18:45:41
390
原创 判定两条线段是否相交
首先介绍一下非常重要的关于叉积的概念，它是线段方法的核心。可以把叉积解释成由点(0,0)，p1，p2和p1+p2=(x1+x2,y1+y2)所构成的平行四边形的有向面积，也可以看做是矩阵行列式：根据P_{1}与P_{2}的叉积，我们就能判断p_{2}是在P_{1}的顺时针方向还是逆时针方向。下面给出的是判断两条是否相交的代码主要注意这里判定的是线段，而不是直线。1.在直
2015-10-24 21:11:12
774
原创 寻找凸包-graham扫描法
Graham扫描法通过维持一个关于候选点的栈S来解决凸包问题。输入集合Q中的每个点都被压栈一次，非CH(Q)中的点最终被弹出栈。当算法终止时，栈S仅包含CH(Q)中的顶点，以逆时针的顺序出现在边界上。该算法最核心的一点就是，逆时针方向遍历凸包时，应该在每个顶点处左转。import java.util.*;public class Graham{ static int MAX = 10
2015-10-24 19:22:05
1290
原创 深度优先实现拓扑排序--java
import java.util.*;public class Topology{ static final int MAX = 20; //最大点数 static int[][] g; //图 static LinkedList queue; //保存排序结果 static int[] ingoing; //记录节点入度 static int[] outgoing;//记录节点出
2015-10-23 09:38:31
2798
原创 Ford-Fulkerson算法 java实现
/*for each edge(u,v) 属于 G,E(u,v).f = 0;while there exists a path p from s to t in the residual network Gfcf(p) = min{cf(u,v):(u,v) is in p};for each edge(u,v) in pif(u,v)属于E(u,v).f += cf
2015-10-22 18:48:08
1699
原创 linux0.99网络模块-数据链路层(发送)
在前面的文章中，分析了网络层数据报的传输过程，其中调用了下面的代码net/tcp/ip.c855 dev->queue_xmit(skb, dev, sk->priority);现在我们就来看一下该设备（wd8003）注册的发送函数，在网络设备初始化一篇中我们分析了wd8003的初始化过程，发送函数正是在那里面注册的，如下：net/tcp/Space.c6
2015-10-22 16:05:59
806
原创 linux0.99网络模块-网络层(发送)
在TCP的write系统调用中调用了下面的函数用于数据报的发送net/tep/tcp.c852 prot->queue_xmit (sk, dev, skb,0);来看一下TCP注册的queue_xmit：net/tcp/tcp.c3185 struct proto tcp_prot =3201 ip_queue_xmit,
2015-10-21 21:03:20
684
原创 linux0.99网络模块-应用层 or 传输层读写
应用层的操作大都会以系统调用的形式调用相应的内核函数，本文就分析一下相关的系统调用以及其他一些辅助函数。本文重点分析UDP与TCP的read/write函数，以达到承前启后的目的（其他函数读者可以大致浏览一下）。create 884 static int 885 ip_proto_create (struct socket *sock, int prot
2015-10-21 20:29:36
980
3
原创 linux0.99网络模块-传输层（TCP接收）
上一篇文章《linux0.99网络模块-网络层(接收)》中我们提到过，注册到IP层的协议有ICMP，TCP，UDP。本文就来分析TCP处理数据报的过程。我们记得上一篇中网络层通过调用下面的函数来把数据报传递给TCP。775 ipprot->handler (skb2, dev, &opt, iph->daddr,776 net16(iph-
2015-10-21 09:24:45
1508
原创 linux0.99网络模块-传输层（UDP接收）
上一篇文章《linux0.99网络模块-网络层(接收)》中我们提到过，注册到IP层的协议有ICMP，TCP，UDP。本文就来分析UDP处理数据报的过程。我们记得上一篇中网络层通过调用下面的函数来把数据报传递给UDP。775 ipprot->handler (skb2, dev, &opt, iph->daddr,776 net16(i
2015-10-20 20:00:58
564
原创 linux0.99网络模块-网络层(接收)
上一篇文章中我们说道了ip层的处理函数为ip_rcv，现在我们就来看一下网络层收到数据报后是如何处理的。第一部分不过在此之前我们先来看一下会用到的一些结构或函数。1.net/tcp/ip.h: 84 struct ip_header 85 { 86 unsigned char ihl:4, version:4; 87 unsigned
2015-10-20 09:25:55
817
原创 linux0.99网络模块-数据链路层(接收)
在《linux0.99网络模块-中断处理》中我们知道网卡设备接收到数据报后就会触发中断，在中断处理函数中会把接收到的封装为sk_buff结构的数据添加到链路层的backlog中，并设置了下半部激活标志。现在我们就来看一下链路层是如何把数据交给上层的。我们从中断下半部的处理开始：net/tcp/dev.c294 void295 inet_bh(void *tmp)29
2015-10-19 11:27:43
548
原创 linux0.99网络模块-物理层(中断处理)
前面《linux0.99网络模块-网络设备初始化》的分析中wd8003注册了中断处理函数wd8003_sigaction（irqaction (dev->irq, &wd8003_sigaction)）。当网络设备接收到数据报之后就会触发中断，然后就会调用该函数。net/tcp/we.c：639 static struct sigaction wd8003_sigaction =
2015-10-18 11:13:10
682
1
原创 linux0.99网络模块-网络设备初始化
在《llinux0.99网络模块-网络模块初始化》中我们分析了网络模块的初始化过程，其中关于设备初始化我们单独拿到这里来分析。对于linux0.99内核来说，它初始化了两个设备-loopback和wd8003.1.数据结构net/tcp/dev.h 47 #define DEV_NUMBUFFS 3 48 #define MAX_ADDR_L
2015-10-15 16:05:10
690
原创 linux0.99网络模块-网络模块初始化
linux0.11版内核的启动过程我们已经分析过了，对于0.99版稍有不同。我们看一下head.S中的改变。linux0.11内核head.s:135 after_page_tables:136 pushl $0 # These are the parameters to main :-)137 pushl $0138 pu
2015-10-13 20:32:03
857
转载 深入剖析Socket实现
在我们平时的开发中用到的最多的是HTTP协议，而HTTP协议本身是一种应用层协议，属于文本协议；并且这种协议也基本上满足了应用的大部分需求。HTTP协议当初的设计并没有想到它应用的是如此的广泛，所以设计的时候考虑的比较简单实用，也许也就是这种简单实用才这么广泛；但如今，HTTP协议似乎并不能满足所有的需求，特别是当今的web2.0时代，浏览器应用横行的年代，也越来越多需要长连接的应用，所以在HTM
2015-09-07 20:55:18
721
原创 TCP/IP详解 卷I 笔记
第1章 概述知识点比较少，主要一个是不同的网络层：应用层 传输层 网络层 链路层它们分别对应的协议，比如IP协议对应网络层 TCP协议对应传输层 以太网协议对应链路层。另外一个是IP地址分类：A类0开始，网络号占一个字节B类10网络号占两个字节C类110网路号占三个字节D类1110，剩余的是28位多播地址E类11110，剩
2015-07-01 22:12:15
1048
原创 内存管理--page.s memory.c源码分析
page.s 1 /* 2 * linux/mm/page.s 3 * 4 * (C) 1991 Linus Torvalds 5 */ 6 7 /* 8 * page.s contains the low-level page-exception code. 9 * the real work is done in
2015-06-29 10:53:23
1003
原创 文件系统(四)--pipe.c read_write.c stat.c fcntl.c ioctl.c源码分析
pipe.c 1 /* 2 * linux/fs/pipe.c 3 * 4 * (C) 1991 Linus Torvalds 5 */ 6 7 #include 9 #include 10 #include /* for get_free_page */ 11 #include include/l
2015-06-19 22:32:54
1192
原创 文件系统(三) --block_dev.c file_dev.c char_dev.c源码分析
1.blk_dev.c1 /* 2 * linux/fs/block_dev.c 3 * 4 * (C) 1991 Linus Torvalds 5 */ 6 7 #include 9 #include 10 #include 11 #include 12 #include 14 int blo
2015-06-17 14:03:04
1203
原创 文件系统(二)--buffer.c namei.c truncate.c open.c源码分析
buffer.c 1 /* 2 * linux/fs/buffer.c 3 * 4 * (C) 1991 Linus Torvalds 5 */ 6 7 /* 8 * 'buffer.c' implements the buffer-cache functions. Race-conditions have 9 * be
2015-06-14 21:47:19
1107
原创 文件系统(一)--super.c bitmap.c inode.c 源码分析
super.c 1 /* 2 * linux/fs/super.c 3 * 4 * (C) 1991 Linus Torvalds 5 */ 6 7 /* 8 * super.c contains code to handle the super-block tables. 9 */ 10 #include 1
2015-06-14 19:37:07
793
原创 字符设备-seria.c tty_io.c seria.c rs_io.s tty_iocnl.c tty.h termios.h keyboard.s源码分析
1 /* 2 * linux/kernel/serial.c 3 * 4 * (C) 1991 Linus Torvalds 5 */ 6 7 /* 8 * serial.c 9 * 10 * This module implements the rs232 io functions 11 * void rs_wr
2015-06-12 15:50:14
1465
原创 块设备--blk.h/hd.c/ll_rw_blk.c源码分析
1. blk.h1 #ifndef _BLK_H 2 #define _BLK_H 3 4 #define NR_BLK_DEV 7 5 /* 6 * NR_REQUEST is the number of entries in the request-queue. 7 * NOTE that writes may use only th
2015-06-10 10:37:04
2709
原创 sched.c signal.c exit.c sys.c源码分析
1 /* 2 * linux/kernel/sched.c 3 * 4 * (C) 1991 Linus Torvalds 5 */ 6 7 /* 8 * 'sched.c' is the main kernel file. It contains scheduling primitives 9 * (sleep_on, wake
2015-06-08 11:05:31
1123
原创 asm.s /trap.c/system_call.s源码分析
asm.s 1 /* 2 * linux/kernel/asm.s 3 * 4 * (C) 1991 Linus Torvalds 5 */ 6 7 /* 8 * asm.s contains the low-level code for most hardware faults. 9 * page_except
2015-06-05 10:06:20
1301
原创 execve源码分析
C语言的execve经过库函数，最终也会通过int 0x80中断陷入内核，并通过eax寄存器来传递调用号。内核会根据系统初始化时注册的中断处理函数来对其进行处理。它的中断处理函数为system_call。这个函数定义在system_call.s中，它会保存一些寄存器的值（对于系统调用来说，保存的主要是参数），然后根据调用号调用syscall_table中相应的表项。syscall_table定
2015-06-03 21:30:20
2247
原创 fork源码分析
kernel/system_call.s207 .align 2208 _sys_fork:209 call _find_empty_process210 testl %eax,%eax211 js 1f212 push %gs213 pushl %esi214 pushl %edi215 p
2015-06-03 16:30:51
2697
1
原创 init/main.c源码分析
前面我们说到head最终调用了main.c的main方法。现在我们就来看一些这个文件的源码。 1 /* 2 * linux/init/main.c 3 * 4 * (C) 1991 Linus Torvalds 5 */ 我们来看一下main函数104 void main(void) /* This really IS
2015-05-12 16:11:22
2577
原创 head.s源码分析
我们前面分析了setup源码，setup在把模式转为保护模式后立刻调用了一个跳转指令，跳转到内存地址0处开始执行，这个位置对应的就是head.s.head.s经过编译后会与其他程序一起连接成system模块，位于system模块最开始，这也是为什么称它head.s.system放在磁盘上setup之后开始的扇区中，即从磁盘上第6个扇区开始。一般情况下，linux0.11内核的sys
2015-05-11 09:30:25
779
原创 setup.s源码分析
1 ! 2 ! setup.s (C) 1991 Linus Torvalds 3 ! 4 ! setup.s is responsible for getting the system data from the BIOS, 5 ! and putting them into the appropriate places in system memory.
2015-05-07 12:59:57
776
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人