??xml version="1.0" encoding="utf-8" standalone="yes"?>սƵ2019:C++博客-sin的博?/title><link>//www.pppqb.icu/sixinquan/</link><description>旉悄悄地流q,今天你做了什?/description><language>zh - սƵ2019|սع//www.pppqb.icu/sixinquan/archive/2019/02/22/216254.htmlsinsinFri, 22 Feb 2019 04:51:00 GMT//www.pppqb.icu/sixinquan/archive/2019/02/22/216254.html//www.pppqb.icu/sixinquan/comments/216254.html//www.pppqb.icu/sixinquan/archive/2019/02/22/216254.html#Feedback0//www.pppqb.icu/sixinquan/comments/commentRss/216254.html//www.pppqb.icu/sixinquan/services/trackbacks/216254.html博客搬至CSDN

sin 2019-02-22 12:51 发表评论
]]>
Linux自旋锁和互斥锁的实现 - սƵ2019|սع//www.pppqb.icu/sixinquan/archive/2013/10/29/203981.htmlsinsinTue, 29 Oct 2013 14:40:00 GMT//www.pppqb.icu/sixinquan/archive/2013/10/29/203981.html//www.pppqb.icu/sixinquan/comments/203981.html//www.pppqb.icu/sixinquan/archive/2013/10/29/203981.html#Feedback0//www.pppqb.icu/sixinquan/comments/commentRss/203981.html//www.pppqb.icu/sixinquan/services/trackbacks/203981.html

自旋锁(spin lockQ应用在多处理器环境中。如果内核控制\径发现自旋锁“开着”Q就获取锁ƈl箋自己的执行。相反,如果内核控制路径发现锁由q行在另一个CPU上的内核控制路径“?着”Q就在周?#8220;旋{”Q反复执行一条紧凑的循环指oQ直到锁被释放。自旋锁的@环指令表C?#8220;忙等”。即使等待的内核控制路径无事可做Q除了浪Ҏ_Q它也在CPU上保持运行。不q,自旋锁通常非常方便Q因为很多内核资源只?毫秒的时间片D;所以说Q等待自旋锁的释放不会消耗太多CPU的时间?br />

一般来_p旋锁所保护的每个界区都是止内核抢占的。在单处理器pȝ上,q种锁本wƈ不v锁的作用Q自旋锁技术仅仅是用来止或启用内核抢 占。请注意Q在自旋锁忙{期_因ؓq没有进入界区Q所以内核抢占还是有效的Q因此,{待自旋锁释攄q程有可能被更高优先U的所取代。这U设计是合理 的,因ؓ不能因ؓ占用CPU太久而ɾpȝ死锁?/p>
互斥锁(mutex lockQ的实现Q实际上是一把锁l护了一个等待队列和一个引用计数器Q当获取锁之前,先对引用计数器减1操作Q如果ؓ非负Q则可以获取锁进入界区。否则将该Q务设Z可中断状态(uninterruptibleQ,挂在该等待对列上。获取锁的Q务从临界区退出后Q计数器?操作Q唤醒(wake upQ等待队列上的被挂vq程?img src ="//www.pppqb.icu/sixinquan/aggbug/203981.html" width = "1" height = "1" />

sin 2013-10-29 22:40 发表评论
]]>
C++对象模型 - սƵ2019|սع//www.pppqb.icu/sixinquan/archive/2013/10/26/203929.htmlsinsinSat, 26 Oct 2013 15:39:00 GMT//www.pppqb.icu/sixinquan/archive/2013/10/26/203929.html//www.pppqb.icu/sixinquan/comments/203929.html//www.pppqb.icu/sixinquan/archive/2013/10/26/203929.html#Feedback0//www.pppqb.icu/sixinquan/comments/commentRss/203929.html//www.pppqb.icu/sixinquan/services/trackbacks/203929.html阅读全文

sin 2013-10-26 23:39 发表评论
]]>
虚析构函数问题:Z么要基cȝ的析构函数设成虚的? - սƵ2019|սع//www.pppqb.icu/sixinquan/archive/2013/10/19/203817.htmlsinsinSat, 19 Oct 2013 13:36:00 GMT//www.pppqb.icu/sixinquan/archive/2013/10/19/203817.html//www.pppqb.icu/sixinquan/comments/203817.html//www.pppqb.icu/sixinquan/archive/2013/10/19/203817.html#Feedback0//www.pppqb.icu/sixinquan/comments/commentRss/203817.html//www.pppqb.icu/sixinquan/services/trackbacks/203817.html
转自Q?/span>//blog.csdn.net/pathuang68/article/details/4156308

?/span>
CSDN|友问:
class A
{
public:
   
~A() 
   { 
      cout 
< <"A::~A" < <endl; 
   }
};


class B:public A
{
public
   
virtual ~B() 
   { 
      cout 
< <"B::~B" < <endl; 
   }
};


class C:public B
{
public
   
~C() 
   { 
      cout 
< <"C::~C" < <endl; 
   }
};

 
int main()

   A 
*a=new A(); 
   B 
*b=new B(); 
   C 
*c=new C(); 
   A 
*d=new B(); 
   A 
*e=new C(); 
   B 
*f=new C(); 

   delete a; 
   cout 
< <endl; 
   delete b; 
   cout 
< <endl; 
   delete c; 
   cout 
< <endl; 
   delete d; 
   cout 
< <endl; 
   delete e; 
   cout 
< <endl; 
   delete f; 
   cout 
< <endl; 

   system(
"Pause");
}

q段E序q行时有错,当时考的时候题目直接说写出q行l果Q我q里糊涂得写下来,回来~下发现有错Q请教下错在哪,最好告诉我Z么?

  

玄机逸士回答Q?/span>

1. 一般来_如果一个类要被另外一个类l承Q而且用其指针指向其子cd象时Q如题目中的A* d = new B();(假定A是基c,B是从Al承而来的派生类)Q那么其(Ac?/span>)析构函数必须是虚的,否则?/span>delete dӞBcȝ析构函数不会被调用Q因而会产生内存泄漏和异常;

2. 在构造一个类的对象时Q先构造其基类子对象,卌用其基类的构造函敎ͼ然后调用本类的构造函敎ͼ销毁对象时Q先调用本类的析构函敎ͼ然后再调用其基类的构造函敎ͼ

3. 题目l出的代码是可以~译的,但会出现q行旉误。错误出现在delete d;q一句。ؓ讨论方便Q我们不妨将AcdBcL写如下:


class A
{
public:
    
int a;
    
~A()
    {
        cout 
<< "A::~A" << endl;
    }
};

class B : public A
{
public:
    
int b;
    
virtual ~B()
    {
        cout 
<< "B::~B" << endl;
    }
};


那么A* d = new B();q一句的左边所产生B的对象的内存l构如下Q?/span>



?/span>A对象的内存结构如下:


可见d只能扑ֈa?/span>Acȝ析构函数Q而无法找?/span>B对象的析构函敎ͼ所以当delete d;的时候,B对象所占用的内存就此被泄漏掉了Q也从而生了异常?/span>

如果?/span>Acȝ析构函数设ؓ虚的Q那?/span>Acd象的内存l构ؓQ?br />

Bcd象的内存l构为:


此时通过A* d = new B();Q?/span>A对象的内存结构中?/span>vfptrQ即虚函数表指针Q就?/span>B对象?/span>vfptr(B对象?/span>vfptr?/span>bitwise copyQ即拷贝到A对象?/span>vfptr。如B是从A虚承而来的,则需要加一?/span>offsetQ情况要更复杂,?a >//blog.csdn.net/pathuang68/archive/2009/04/24/4105902.aspx)Q因此,A对象?/span>vfptr所指向的是B对象的虚函数表,?/span>B的析构函C于书函数?/span>0的位|,因此Q这样就可以通过Acd象的指针dQ找?/span>Bcd象的析构函数Q从而在delete d;Ӟ可以销?/span>B对象Q而不会生内存泄漏和异常?/span>


事实上,该题目只要将A中的析构函数设成虚的Q?/span>BcM的析构函数前面的virtual关键字不是否存在,其析构函C一定是虚的Q?/span>Ccd此道理。因此,得到l论是Q只要能够保证承关pM最高的基类的析构函数是虚的Q那么就不会产生前面所谈及的问题。这是Z么在想用多态特性的时候,需要将基类的析构函数设成虚的真正原因?/span>

 



sin 2013-10-19 21:36 发表评论
]]>
TCPH口滑动机制 - սƵ2019|սع//www.pppqb.icu/sixinquan/archive/2013/10/18/203808.htmlsinsinFri, 18 Oct 2013 13:54:00 GMT//www.pppqb.icu/sixinquan/archive/2013/10/18/203808.html//www.pppqb.icu/sixinquan/comments/203808.html//www.pppqb.icu/sixinquan/archive/2013/10/18/203808.html#Feedback0//www.pppqb.icu/sixinquan/comments/commentRss/203808.html//www.pppqb.icu/sixinquan/services/trackbacks/203808.html滑动H口协议的基本原理就是在L时刻Q发送方都维持了一个连l的允许发送的帧的序号Q称为发送窗口;同时Q接收方也维持了一个连l的允许接收的的序PUCؓ接收H口。发送窗口和接收H口的序L上下界不一定要一P甚至大小也可以不同。不同的滑动H口协议H口大小一般不同。发送方H口内的序列号代表了那些已经被发送,但是q没有被认的Q或者是那些可以被发送的帧。下面D一个例子(假设发送窗口尺ؓ2Q接收窗口尺ؓ1Q:


①初始态,发送方没有帧发出,发送窗口前后沿盔R合。接收方0L口打开Q等待接?号Q?
②发送方打开0L口,表示已发?帧但确认返回信息。此时接收窗口状态不变;
③发送方打开0?L口,表示0?号均在{待认之列。至此,发送方打开的窗口数已达规定限度Q在未收到新的确认返回之前Q发送方暂停发送新的数据。接收窗口此时状态仍未变Q?
④接收方已收到0号Q?L口关闭,1L口打开Q表C准备接?号。此时发送窗口状态不变;
⑤发送方收到接收方发来的0号Ἃ认q回信息Q关?L口,表示从重发表中删?号。此时接收窗口状态仍不变Q?
⑥发送方l箋发?号Q?L口打开Q表C?号也纳入待认之列。至此,发送方打开的窗口又已达规定限度Q在未收到新的确认返回之前Q发送方暂停发送新的数据Q此时接收窗口状态仍不变Q?
⑦接收方已收到1号Q?L口关闭,2L口打开Q表C准备接?号。此时发送窗口状态不变;
⑧发送方收到接收方发来的1号收毕的确认信息,关闭1L口,表示从重发表中删?号。此时接收窗口状态仍不变?/div>

sin 2013-10-18 21:54 发表评论
]]>Linux内存理之三 늚分配和释?/title><link>//www.pppqb.icu/sixinquan/archive/2012/07/29/185545.html</link><dc:creator>sin</dc:creator><author>sin</author><pubDate>Sun, 29 Jul 2012 06:44:00 GMT</pubDate><guid>//www.pppqb.icu/sixinquan/archive/2012/07/29/185545.html</guid><wfw:comment>//www.pppqb.icu/sixinquan/comments/185545.html</wfw:comment><comments>//www.pppqb.icu/sixinquan/archive/2012/07/29/185545.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>//www.pppqb.icu/sixinquan/comments/commentRss/185545.html</wfw:commentRss><trackback:ping>//www.pppqb.icu/sixinquan/services/trackbacks/185545.html</trackback:ping><description><![CDATA[Linux对内存区内的|的分配和释放Q采用的法是伙伴系l?br /><img alt="" src="//www.pppqb.icu/images/cppblog_com/sixinquan/伙伴pȝ.png" height="233" width="562" /><br /><br />如上图,Linux分配|Q只能分?^n个页。内核维护MAX_ORDER个链表,每个链表记录着q箋的空闲页。第一个链表中的每一ؓ1个空闲页Q第二个链表中的每一ؓ2个空闲页Q第三个链表中的每一ؓ4个空闲页。。。,依次cL。分配页Ӟ从对应的链表上摘除空闲页Q释NӞ对应的归q到对应的链表。分配释N的过E中Q可能伴随着内存늚拆分和合q。比如要分配16个空闲页Q但是对应的链表为空Q这时如?2个空闲页对应的链表如果不为空Q则从链表中摘除32个空闲页Qƈ其一分ؓ二,其中16个页用于内存分配Q剩?6个页则插入到16个页对应的链表中?br /><br />管늚分配法是简单的Q但是实际过E却非常复杂。这是因为分配页式必考虑一下几点:<br />1 备用内存区。当从一个内存区无法得到内存Ӟpȝ会从同一内存节点的其它内存区或者从另一个内存节点中的内存区中获取内存?br />2 늚换入和换出,在没有够多的空闲页Ӟ可能需要将|Z获取I闲内存?br />3 늚回收Q对一些缓冲区的不再用的进行回Ӟ以获取空闲页?br />4 pȝ中必M持一?#8220;水位”的空闲页Q以应付对内存的紧急分配。如果系l将分配完Q在急需内存Ӟ再进行页的回收或换出Q无疑是非常p糕的设计。系l中必须保持一定量的内存页?br />5 不同的分配策略。不同的分配{略可能采用的方法有区别?br />MQ页的分配和释放需要考虑许多因素Q尽量满_存分配的同时Q要保证pȝ的稳定性和健壮性?img src ="//www.pppqb.icu/sixinquan/aggbug/185545.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="//www.pppqb.icu/sixinquan/" target="_blank">sin</a> 2012-07-29 14:44 <a href="//www.pppqb.icu/sixinquan/archive/2012/07/29/185545.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>Linux内存理之二 内存节点和内存分?/title><link>//www.pppqb.icu/sixinquan/archive/2012/07/29/185090.html</link><dc:creator>sin</dc:creator><author>sin</author><pubDate>Sun, 29 Jul 2012 01:38:00 GMT</pubDate><guid>//www.pppqb.icu/sixinquan/archive/2012/07/29/185090.html</guid><wfw:comment>//www.pppqb.icu/sixinquan/comments/185090.html</wfw:comment><comments>//www.pppqb.icu/sixinquan/archive/2012/07/29/185090.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>//www.pppqb.icu/sixinquan/comments/commentRss/185090.html</wfw:commentRss><trackback:ping>//www.pppqb.icu/sixinquan/services/trackbacks/185090.html</trackback:ping><description><![CDATA[UMA和NUMAQ?br />UMA(Uniform Memory Access)Q即一致性内存访问。这U情况下QCPU讉K内存的Q何位|,代h都是一L?br />NUMA)(Non Uniform Memory Access)Q即非一致性内存访问。这U情况下QCPU讉K不同位置的内存,代h是不一L。在多CPU情况下,Ҏ个CPU来说有本地内存和q端内存Q访问本地内存的代h比访问远端内存的代h。确保CPU讉K内存代h最,是非帔R要的一炏V?br /><br />Linux支持多种g体系l构Q因此Linux必须采用通用的方法来描述内存Q以方便对内存进行管理。ؓ此,Linux有了内存节点、内存区、页框的概念Q这些概念也是一目了然的?br />内存节点Q主要依据CPU讉K代h的不同而划分。多CPU下环境下Q本地内存和q端内存是不同的节炏V即使在单CPU环境下,讉K所有内存的代h都是一LQLinux内核依然存在内存节点的概念,只不q只有一个内存节点而已。内总struct  pg_data_t来描q内存分区?br />内存分区QLinux对内存节点再q行划分Q分Z同的分区。内总struct zone来描q内存分区。通常一个节点分为DMA、Normal和High Memory内存区,具体下面再介l?br />|QLinux采用式内存理Q页是物理内存管理的基本单位Q每个内存分区又由大量的|l成。内总struct page来描q页框。页框有很多属性,q些属性描qCq个|的状态、用途等Q例如是否被分配?br /><img alt="" src="//www.pppqb.icu/images/cppblog_com/sixinquan/node.JPG" height="502" width="857" /><br /><br />上图中的zone_mem_map是一个页框的数组Q它记录了一个内存分区的所有页框的使用情况?br /><div class="dpun"><br />DMA内存区:即直接内存访问分区,通常为物理内存的起始16M。主要是供一些外设用,外设和内存直接访问数据访问,而无需pȝCPU的参与?br />Normal内存区:?6M?96M内存区?br />HighMemory内存区:896M以后的内存区?br /><br />Z么高端内存的边界?96MQ这是因为,32位Linux虚拟内存I间?-4GQ其?-3G用于用户态,3G-4G用于内核态。这意味着内核只有1G的虚拟地址I间Q如果物理内存超q?GQ内核就无法映射了。Linux采取的策略是Q内核地址I间的前896M采用固定映射Q映方法是Q虚拟地址-3G = 物理地址Q只能映到物理地址的前896M。也是说内核虚拟地址I间?G?G+896Mq部分,表的映是固定的,pȝ初始化时徏立v来。而虚拟地址I间的最?28MQ也是3G+896M?G部分采用动态映,也就是说表映射的物理地址可变的。在pȝq行q程中,通过更新表Q就可以映射C同的物理地址Q当然也包括高端物理内存?br /><br />q主要解决了两个问题Q第一Q这可以使内核地址I间映射到高端物理内存;W二Q虚拟地址I间?G+896M?G部分Q连l的虚拟地址I间可以映射到非q箋的物理内存,只要通过更新表可以做刎ͼq和用户态的虚拟内存映射采用了同栯U方法。这在没有大D连l的I闲物理地址Ӟ是非帔R要的?br /><br />备用内存区:<br />在一个内存区分配|Q如果这个内存区没有满条g的内存页Q则需要从其它内存区或从其它内存节点分配。Linux为每个内存区都徏立了备用内存区列表,当前内存区没有满x件的内存Ӟ׃备用内存区分配。比如,pȝ中有4个内存节点A,B,C,DQ每个内存节点又分ؓDMA、Normal、HighMemory内存区。对节点B来说Q内存区分配列表可能是B(HighMemory)、B(Normal)、B(DMA)?div>A(HighMemory)、A(Normal)、A(DMA)?/div><div class="dpun">C(HighMemory)、C(Normal)、C(DMA)?/div><div class="dpun">D(HighMemory)、D(Normal)、D(DMA)?br />分配内存Ӟ优先从本地内存节点分配,再从其它内存节点分配。对一个内存节点,优先从HighMemory分配Q再从Normal或DMA分配?/div></div><img src ="//www.pppqb.icu/sixinquan/aggbug/185090.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="//www.pppqb.icu/sixinquan/" target="_blank">sin</a> 2012-07-29 09:38 <a href="//www.pppqb.icu/sixinquan/archive/2012/07/29/185090.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>Linux内存理之一 分段与分?/title><link>//www.pppqb.icu/sixinquan/archive/2012/07/19/184234.html</link><dc:creator>sin</dc:creator><author>sin</author><pubDate>Thu, 19 Jul 2012 13:22:00 GMT</pubDate><guid>//www.pppqb.icu/sixinquan/archive/2012/07/19/184234.html</guid><wfw:comment>//www.pppqb.icu/sixinquan/comments/184234.html</wfw:comment><comments>//www.pppqb.icu/sixinquan/archive/2012/07/19/184234.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>//www.pppqb.icu/sixinquan/comments/commentRss/184234.html</wfw:commentRss><trackback:ping>//www.pppqb.icu/sixinquan/services/trackbacks/184234.html</trackback:ping><description><![CDATA[C操作pȝ的内存管理机制有两种Q段式管理和式理?br /><br />D式内存理Q就是将内存分成D,每个D늚起始地址是D基地址。地址映射的时候,由逻辑地址加上D基地址而得到物理地址。纯_的D式内存理的缺点很明显Q就是灵zL和效率比较差。首先是D늚长度是可变的Q这l内存的换入换出带来诸多不便Q如何选择一个段的长度是一个棘手的问题Q其ơ进E在q行q程中,可能会扩充地址I间Q这p增加D,从而造成q程的地址I间由很多小D|成,在进E运行过E中Q访问不同的D|Q就需要频J切换段基地址Q再一点,D式内存理如果有太多的段Q在释放D늚时候,会造成外部片?br /><br />式内存理Q内存分成固定长度的一个个늉。地址映射的时候,需要先建立表Q页表中的每一w记录了这个页的基地址。通过表Q由逻辑地址的高位部分先扑ֈ逻辑地址对应的页基地址Q再由页基地址偏移一定长度就得到最后的物理地址Q偏Uȝ长度由逻辑地址的低位部分决定。一般情况下Q这个过E都可以q件完成,所以效率还是比较高的。页式内存管理的优点是比较灉|Q内存管理以较小的页为单位,方便内存换入换出和扩充地址I间?br /><br />严格说Linux采用D页式内存管理,也就是既分段Q又分页。地址映射的时候,先确定对应的D,定D基地址Q段内分,再找到对应的表,定基地址Q再由逻辑地址低位定的页偏移量,p扑ֈ最l的物理地址。但是,实际上Linux采用的是式内存理。原因是Linux中的D基地址都是0Q相当于所有的D都是相同的。这样做的原因是某些体系l构的硬仉Ӟ比如Intel的i386。作Y件的操作pȝQ必要W合g体系。虽然所有段基地址都是0Q但是段的概念在Linux内核中是实存在的。比如常见的内核代码Dc内核数据段、用h代码段、用h数据段{。除了符合硬件要求外Q段也是有实际意义的?br /><br />x86g分段单元Q?br /><img alt="" src="//www.pppqb.icu/images/cppblog_com/sixinquan/分段单元.jpg" height="140" width="311" /><br /><div class="dpun">逻辑地址分ؓ两部分组成:D|识符和指定段内相对地址的偏U量?br /><div class="dpun">D|q符Q用来存放段起始地址Q段大小Q存储权限等?br />D|q符表:存放D|q的表项?br />D寄存器Q存放段标识W?个段寄存器称为cs(代码D寄存器)Qss(栈段寄存?Qds(数据D寄存器)QesQfs 和gs?br />D基地址寄存器:指向D|q符表地址?/div></div><br />Linux分段机制Q?br />Linux对分D用非常有限。作Z个跨g体系的操作系l,要支持多U硬件体p,而一些硬件体pȝ构式不支持分D늚QLinux把所有段起始地址都设??br />Linux采用4个段q行dQ用h代码段Q用h数据段Q内核态代码段Q内核态数据段?br /><br /><br />x86分页单元Q?br /><img alt="" src="//www.pppqb.icu/images/cppblog_com/sixinquan/分页单元.jpg" height="128" width="377" /><br />x86采用两表?br />W一Uؓ늛录表Q存储在一?K字节的页中,每个表项包含了一个页表的物理地址。线性地址最高的10?22-31)用来产生W一U表索引Q由该烦引得到的表项中的内容定位了二U表中的一个表的地址Q即下表所在的内存块号?br />W二Uؓ表Q存储在一?K字节中Q每个表包含了一个页的物理地址。线性地址的中?0?12-21)位进行烦引,定位表表项Q获得页的物理地址。页物理地址的高20位与U性地址的低12位Ş成最后的物理地址?br /><div class="dpun">分页机制由CR0寄存器中的PG位启用。如PG=1Q启用分|Ӟ把线性地址转换为物理地址。如PG=0Q禁用分|Ӟ直接D|制生的U性地址当作物理地址使用?br />늛录表的物理地址存放在CR3寄存器。每个进E有它自q全局目录和自q表集。当发生q程切换ӞLinux把CR3控制寄存器的内容保存在前一个执行进E的描述W中Q然后把下一个要执行q程的描q符的D入CR3寄存器中。这保了当新进E重新开始在CPU上执行时Q分单元指向一l正的表?/div><br />Linux分页机制Q?br />作ؓ一个通用的操作系l,Linux需要兼容各U硬件体p,包括不同位数的CPU。对64位的CPU来说Q两U页表仍然太,一个页表会太大Q这会占用太多宝늚物理内存。Linux采用了通用的四U页表。实际采用几U页表则具体受硬件的限制?br /><img alt="" src="//www.pppqb.icu/images/cppblog_com/sixinquan/linux4U页?gif" height="332" width="581" /><br />四种表分别UCؓQ?全局目录、页上目录、页中间目录、页表。对?2位x86pȝQ两U页表已l够了。Linux通过?#8220;上U目?#8221;位和“中间目?#8221;位全?Q彻底取消了上U目 录和中间目录字Dc不q,上U目录和中间目录在指针序列中的位置被保留,以便同样的代码在32位系l和64位系l下都能使用?img src ="//www.pppqb.icu/sixinquan/aggbug/184234.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="//www.pppqb.icu/sixinquan/" target="_blank">sin</a> 2012-07-19 21:22 <a href="//www.pppqb.icu/sixinquan/archive/2012/07/19/184234.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>二叉树的非递归遍历 - սƵ2019|սع//www.pppqb.icu/sixinquan/archive/2010/03/16/109802.htmlsinsinTue, 16 Mar 2010 01:57:00 GMT//www.pppqb.icu/sixinquan/archive/2010/03/16/109802.html//www.pppqb.icu/sixinquan/comments/109802.html//www.pppqb.icu/sixinquan/archive/2010/03/16/109802.html#Feedback0//www.pppqb.icu/sixinquan/comments/commentRss/109802.html//www.pppqb.icu/sixinquan/services/trackbacks/109802.html
#include <stdio.h>
#include 
<stdlib.h>

#define MAX_SIZE 128

struct node 
{
    
int        data;
    
struct node*    lchild;
    
struct node*    rchild;
};

struct bin_search_tree 
{
    
struct node*    root;
};


void    init_search_tree(struct bin_search_tree *tree);
void    clear_search_tree(struct bin_search_tree *tree);
void    insert_node(struct bin_search_tree *tree, int element);

void    pre_order(struct node *p);
void    in_order(struct node *p);
void    post_order(struct node *p);

void    visit(struct node *p);


int main()
{
    
struct bin_search_tree tree;
    
int i,arr[] = {4030501127987479915037};
    
    init_search_tree(
&tree);
    
for (i=0; i<sizeof(arr)/sizeof(int); i++)
    {
        insert_node(
&tree, arr[i]);
    }

    
//前序遍历
    pre_order(tree.root);
    printf(
"\n");

    
//中序遍历
    in_order(tree.root);
    printf(
"\n");

    
//后箋遍历
    post_order(tree.root);
    printf(
"\n");

    clear_search_tree(
&tree);
    getchar();
    
return 0;
}



/*
* 二叉树的初始?br>
*/
void init_search_tree(struct bin_search_tree *tree)
{
    tree
->root = NULL;
}

/*
* 清除二叉树,用二叉树层次遍历
*/
void clear_search_tree(struct bin_search_tree *tree)
{
    
int i,j;
    
struct node *p,*queue[MAX_SIZE];

    i 
= j = 0;
    queue[
0= tree->root;

    
while (i<=j)
    {
        
for ( ; i<=j; i++ )
        {
            p 
= queue[i];

            
if (p->lchild)
                queue[
++j] = p->lchild;
            
if (p->rchild)
                queue[
++j] = p->rchild;
        }
    }

    
for (i=0; i<=j; i++)
    {
        free(queue[i]);
    }

    tree
->root = NULL;
}

/*
* 二叉树中插入节点element
*/
void insert_node(struct bin_search_tree *tree, int element)
{
    
struct node    *= tree->root;
    
struct node *child, *newnode;

    newnode 
= (struct node*)malloc(sizeof(struct node));
    newnode
->data = element;
    newnode
->lchild = NULL;
    newnode
->rchild = NULL;

    
if (tree->root == NULL)
    {
        tree
->root = newnode;
        
return;
    }

    
while (p)
    {
        
if ( element < p->data )
        {
            child 
= p->lchild;
            
if (NULL == child)
            {
                p
->lchild = newnode;
                
return;
            }
        }
        
else
        {
            child 
= p->rchild;
            
if (NULL == child)
            {
                p
->rchild = newnode;
                
return;
            }
        }

        p 
= child;
    }
}

/*
* 前序遍历Q非递归
*/
void pre_order(struct node *p)
{
    
int top = -1;
    
struct node *stack[MAX_SIZE];

    
if (p == NULL)
        
return;

    stack[
++top] = p;
    
while (top>-1
    {
        visit(p
=stack[top--]);

        
if (p->rchild)
            stack[
++top] = p->rchild;
        
if (p->lchild)
            stack[
++top] = p->lchild;
    } 
}

/*
* 中序遍历Q非递归
*/
void in_order(struct node *p)
{
    
int top = -1;
    
struct node *stack[MAX_SIZE];

    
while (top>-1 || p!=NULL)
    {
        
while (p)
        {
            stack[
++top] = p;
            p 
= p->lchild;
        }
        visit(p
=stack[top--]);
        p 
= p->rchild;
    }
}

/*
* 后序遍历Q非递归
*/
void post_order(struct node *p)
{
    
int top = -1;
    
int flag[MAX_SIZE];
    
struct node *stack[MAX_SIZE];

    
while (top>-1 || p!= NULL)
    {
        
while (p)        //p的所有左节点压入?/span>
        {
            stack[
++top] = p;
            flag[top] 
= 0;
            p 
= p->lchild;
        }

        p 
= stack[top];    //弹出栈顶
        if (flag[top--]==0 && p->rchild)
        {
            stack[
++top] = p;
            flag[top] 
= 1;
            p 
= p->rchild;
        } 
        
else
        {
            visit(p);
            p 
= NULL;    //p|ؓNULLQ防止进入while(p)循环
        }
    }
}

/*
* 讉K一个节?br>
*/
void visit(struct node *p)
{
    printf(
"%d  ", p->data);
}




sin 2010-03-16 09:57 发表评论
]]>
WIN32多线E五 U程同步机制Semaphore - սƵ2019|սع//www.pppqb.icu/sixinquan/archive/2010/03/15/109713.htmlsinsinSun, 14 Mar 2010 17:22:00 GMT//www.pppqb.icu/sixinquan/archive/2010/03/15/109713.html//www.pppqb.icu/sixinquan/comments/109713.html//www.pppqb.icu/sixinquan/archive/2010/03/15/109713.html#Feedback0//www.pppqb.icu/sixinquan/comments/commentRss/109713.html//www.pppqb.icu/sixinquan/services/trackbacks/109713.html实际上,如果创徏一个信号量Qƈ且它的最大计数是1Q那么它׃Mutex{h?br>
下面是个生?消费者问题的Win32E序Q运行时的截囑֦?


代码如下:
/* 生?消费者问题是一个经典的q程同步问题Q该问题最早由Dijkstra提出Q很多计机问题都可以抽象ؓ生?消费者问题?br> * ?个生产者生产商品放到环形buffer中供5个消费者消费;生者每ơ最多生?个商品,消费者每ơ消?个?br> * 要解册个问题,我们必须保:(1)q且当缓冲区中没有商品时Q消费者不能消费,~冲区满Ӟ生者也不能生商品 (2)不同消费?nbsp; * 不能同时消费同一个商品;
 *
 * 解决(1)我们用一个生产者信号量表示生者者资源,即空闲buffer数量Q用一个消费者信号量表示消费者资源,即非I闲buffer数量?br> * 解决(2)我们用一个互斥量MutexQ得到这个Mutex的消费者才能消贏V?br>
*/

#include 
<time.h>
#include 
<stdlib.h>
#include 
<Windows.h>


#define ASSERT(a) if (!(a)) \
    exit(EXIT_FAILURE)

#define MAX_PRODUCE_COUNT    5      //生者每ơ最多生产数?/span>
#define CONSUMER_COUNT        5     //消费者数?/span>
#define BUFFER_SIZE        20       //~冲区大?/span>
#define SLEEP_TIME        600
#define WM_FORCE_PAINT        (WM_APP+10)

void    ProduceAndConsume();
void    EndProduceConsume();

LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM) ;  
//Win32H口回调函数

DWORD    WINAPI    ProducerThread(LPVOID pVoid);   
//生者线E函?/span>
DWORD    WINAPI    ConsumerThread(LPVOID pVoid);   //消费者线E函?/span>

int        iProducerPointer;         //生者指针,指向可以攑֕品的的位|?/span>
int        iConsumerPointer;         //消费者指针,指向可以消费商品的位|?/span>
HANDLE        hProducerSemaphore;    //生者信号量Q初始有20个资?/span>
HANDLE        hConsumerSemaphore;    //消费者信号量Q初始有0个资?/span>
HANDLE        hConsumerMutex;        //生者Mutex

HANDLE        hProducerThread;                    
//生者线E,不断生商品
HANDLE        hConsumersThread[CONSUMER_COUNT];    //消费者线E,不断消费商品
HWND        hWnd;

int WINAPI WinMain (HINSTANCE hInstance, HINSTANCE hPrevInstance,
                    PSTR szCmdLine, 
int iCmdShow)
{
    
static TCHAR szAppName[] = TEXT("生长者消费?/span>") ;
    MSG        msg ;
    WNDCLASS    wndclass ;


    wndclass.style        
= CS_HREDRAW | CS_VREDRAW ;
    wndclass.lpfnWndProc  
= WndProc ;
    wndclass.cbClsExtra   
= 0 ;
    wndclass.cbWndExtra   
= 0 ;
    wndclass.hInstance    
= hInstance ;
    wndclass.hIcon        
= LoadIcon (NULL, IDI_APPLICATION) ;
    wndclass.hCursor      
= LoadCursor (NULL, IDC_ARROW) ;
    wndclass.hbrBackground
= (HBRUSH) GetStockObject (WHITE_BRUSH) ;
    wndclass.lpszMenuName 
= NULL ;
    wndclass.lpszClassName
= szAppName ;

    
if (!RegisterClass (&wndclass))
    {
        MessageBox (  NULL, TEXT (
"This program requires Windows NT!"),
            szAppName, MB_ICONERROR) ;
        
return 0 ;
    }

    hWnd 
= CreateWindow( szAppName,      
        TEXT (
"生长者消费?/span>"),   
        WS_OVERLAPPEDWINDOW,  
        CW_USEDEFAULT,
        CW_USEDEFAULT,
        CW_USEDEFAULT,
        CW_USEDEFAULT,
        NULL,                 
        NULL,            
        hInstance,   
        NULL) ;     

    ShowWindow (hWnd, iCmdShow) ;
    UpdateWindow (hWnd) ;

    ProduceAndConsume();      
//创徏生者消费者线E、信号量、MutexQƈq行

    
while (GetMessage (&msg, NULL, 00))
    {
        TranslateMessage (
&msg) ;
        DispatchMessage (
&msg) ;
    }
    
    EndProduceConsume();

    
return (int)msg.wParam ;
}


LRESULT CALLBACK WndProc (HWND hwnd, UINT message, WPARAM wParam, LPARAM lParam)
{
    
int        iTemp;
    
int        iXStart,iYStart;
    HDC             hdc ;
    HBRUSH        hBrush;
    PAINTSTRUCT    ps ;
    RECT        rect;
    MSG        msg;

    
switch (message)
    {
    
case WM_CREATE:
        
return 0 ;

    
case WM_FORCE_PAINT:
        InvalidateRect(hWnd, NULL, TRUE);
        
while (PeekMessage(&msg, hWnd, WM_FORCE_PAINT, WM_FORCE_PAINT, PM_REMOVE))
            ;
        
return 0;

    
case  WM_PAINT:    
        hdc 
= BeginPaint (hwnd, &ps) ;

        GetClientRect(hWnd,
&rect);
        iXStart 
= (rect.right-rect.left)/2-200;
        iYStart 
= (rect.bottom-rect.top)/2-10;
        hBrush 
= SelectObject(hdc, (HBRUSH)GetStockObject(GRAY_BRUSH));
        iTemp 
= iConsumerPointer;

        
while (TRUE)
        {
            Rectangle(hdc, iXStart
+iTemp*20, iYStart, iXStart+(iTemp+1)*20, iYStart+20);
            
if (++iTemp >= BUFFER_SIZE)
                iTemp 
= 0;
            
if (iTemp == iProducerPointer)
                
break;
        }

        SelectObject(hdc, hBrush);

        
while (TRUE)
        {
            Rectangle(hdc, iXStart
+iTemp*20, iYStart, iXStart+(iTemp+1)*20, iYStart+20);
            
if (++iTemp >= BUFFER_SIZE)
                iTemp 
= 0;
            
if (iTemp == iConsumerPointer)
                
break;
        }

        EndPaint (hwnd, 
&ps) ;
        
return 0 ;

    
case   WM_DESTROY:
        PostQuitMessage (
0) ;
        
return 0 ;
    }

    
return DefWindowProc (hwnd, message, wParam, lParam) ;
}

DWORD WINAPI ProducerThread(LPVOID pVoid)
{
    
int        i;
    
int        iRandom;

    
while (TRUE)
    {
        srand((unsigned)time(NULL));
        iRandom 
= rand()%MAX_PRODUCE_COUNT;
        
if (iRandom == 0)
            iRandom
++;

        
//生者申请iRandom个资?/span>
        for (i=0; i<iRandom; i++)
            ASSERT( WAIT_OBJECT_0 
== WaitForSingleObject(hProducerSemaphore, INFINITE) );

        
//生者生产iRandom个商?/span>
        iProducerPointer = iProducerPointer+iRandom;
        
if (iProducerPointer>=BUFFER_SIZE)
            iProducerPointer 
= iProducerPointer-BUFFER_SIZE;

        SendMessage(hWnd, WM_FORCE_PAINT, 
00);
        Sleep(SLEEP_TIME);

        
//生者生产了iRandom个商品,消费者有更多的商品消费了Q所以ؓ消费者释放iRandom个资?/span>
        ASSERT(ReleaseSemaphore(hConsumerSemaphore, (long)iRandom, NULL));
    }

    
return 0;
}

DWORD WINAPI ConsumerThread(LPVOID pVoid)
{
    
while (TRUE)
    {
        
//消费者申请到Semaphore和Mutex后,才能消费
        ASSERT( WAIT_OBJECT_0 == WaitForSingleObject(hConsumerSemaphore, INFINITE) );
        ASSERT( WAIT_OBJECT_0 
== WaitForSingleObject(hConsumerMutex, INFINITE) );

        
//消费者消费一个商?/span>
        iConsumerPointer++;
        
if (iConsumerPointer>=BUFFER_SIZE)
            iConsumerPointer 
= 0;

        SendMessage(hWnd, WM_FORCE_PAINT, 
00);
        Sleep(SLEEP_TIME
/2);
        
        
//消费者释放Mutex
        ASSERT(ReleaseMutex(hConsumerMutex));

        
//消费者消费了一个商品,buffer中多了一个空闲位|,为生产者释放一个资?/span>
        ASSERT(ReleaseSemaphore(hProducerSemaphore, (long)1, NULL));
    }

    
return 0;
}

void ProduceAndConsume()
{
    
int        i;
    DWORD    dwThreadID;

    iProducerPointer 
= 0;
    iConsumerPointer 
= 0;

    hProducerSemaphore 
= CreateSemaphore(NULL, BUFFER_SIZE, BUFFER_SIZE, NULL);      //创徏生者信号量Q初始有20个资?/span>
    hConsumerSemaphore = CreateSemaphore(NULL, 0, BUFFER_SIZE, NULL);                //创徏消费者信号量Q初始有0个资?/span>
    hConsumerMutex       = CreateMutex(NULL, FALSE, NULL);                           //创徏消费者Mutex

    hProducerThread       
= CreateThread(NULL, 0, ProducerThread, NULL, 0&dwThreadID);
    
for (i=0; i<CONSUMER_COUNT; i++)
    {
        hConsumersThread[i] 
= CreateThread(NULL, 0, ConsumerThread, NULL, 0&dwThreadID);
    }
}

void EndProduceConsume()
{
    
int i;

    ASSERT(CloseHandle(hProducerSemaphore));
    ASSERT(CloseHandle(hConsumerSemaphore));
    ASSERT(CloseHandle(hConsumerMutex));
    ASSERT(CloseHandle(hProducerThread));
    
for (i=0; i<CONSUMER_COUNT; i++)
    {
        ASSERT(CloseHandle(hConsumersThread[i]));
    }
}



սƵ2019 2010-03-15 01:22 发表评论
]]>