popular algorithm problems

linkedlist: loop, revert, merge two sorted ones, add two

bst: verify bst(inorder w/o array)

Advertisements

How to use trace of CLISP

//first, let's say we have this lisp file:
;clone a list
(defun clone(lst)
	(if (atom lst) lst
		(cons (clone (car lst))
					(clone (cdr lst))
		)
	)
)

//next, we can launch lisp, and do the following:
Break 4 [13]> (load "clone.lsp")
Break 9 [18]> trace clone
Break 11 [20]> (clone '(a b c))
1. Trace: (CLONE '(A B C))
2. Trace: (CLONE 'A)
2. Trace: CLONE ==> A
2. Trace: (CLONE '(B C))
3. Trace: (CLONE 'B)
3. Trace: CLONE ==> B
3. Trace: (CLONE '(C))
4. Trace: (CLONE 'C)
4. Trace: CLONE ==> C
4. Trace: (CLONE 'NIL)
4. Trace: CLONE ==> NIL
3. Trace: CLONE ==> (C)
2. Trace: CLONE ==> (B C)
1. Trace: CLONE ==> (A B C)
(A B C)
Break 11 [20]>

tips of lisp

say, common lisp.

1) what is exactly cons doing (dot or no dot)?
see
http://en.wikipedia.org/wiki/Cons
which is very clear!

strictly speaking, cons append list
========================================
cons: create a new list whose car is 1st arg, cdr is 2nd arg, no special work is taken for nil ending.
[4]> (cons ‘a ‘b)
(A . B)

[1]> (cons ‘a (cons ‘b nil))
(A B)

[2]> (setq l1 ‘(a b))
(A B)
[3]> (setq l2 ‘(c (d e)))
(C (D E))
[4]> (cons l1 l2)
((A B) C (D E))

list=========================================
list simply put all

how compiled code looks like

Tags

,

//let's define a single hello.cpp file to see how the compiled code looks like
#include <iostream>

using namespace std;

int main()
{
  int i=2;
  int j=3;
  int c = i+j;
}
//compiled file
//g++ -S -o hello.s hello.cpp
	.file	"hello.cpp"
	.local	_ZStL8__ioinit
	.comm	_ZStL8__ioinit,1,1
	.text
	.globl	main
	.type	main, @function
main:
.LFB966:
	.cfi_startproc
	pushl	%ebp
	.cfi_def_cfa_offset 8
	.cfi_offset 5, -8
	movl	%esp, %ebp
	.cfi_def_cfa_register 5
	subl	$16, %esp
	movl	$2, -12(%ebp)
	movl	$3, -8(%ebp)
	movl	-8(%ebp), %eax
	movl	-12(%ebp), %edx
	addl	%edx, %eax
	movl	%eax, -4(%ebp)
	movl	$0, %eax
	leave
	.cfi_restore 5
	.cfi_def_cfa 4, 4
	ret
	.cfi_endproc
.LFE966:
	.size	main, .-main
	.type	_Z41__static_initialization_and_destruction_0ii, @function
_Z41__static_initialization_and_destruction_0ii:
.LFB967:
	.cfi_startproc
	pushl	%ebp
	.cfi_def_cfa_offset 8
	.cfi_offset 5, -8
	movl	%esp, %ebp
	.cfi_def_cfa_register 5
	subl	$24, %esp
	cmpl	$1, 8(%ebp)
	jne	.L2
	cmpl	$65535, 12(%ebp)
	jne	.L2
	movl	$_ZStL8__ioinit, (%esp)
	call	_ZNSt8ios_base4InitC1Ev
	movl	$_ZNSt8ios_base4InitD1Ev, %eax
	movl	$__dso_handle, 8(%esp)
	movl	$_ZStL8__ioinit, 4(%esp)
	movl	%eax, (%esp)
	call	__cxa_atexit
.L2:
	leave
	.cfi_restore 5
	.cfi_def_cfa 4, 4
	ret
	.cfi_endproc
.LFE967:
	.size	_Z41__static_initialization_and_destruction_0ii, .-_Z41__static_initialization_and_destruction_0ii
	.type	_GLOBAL__sub_I_main, @function
_GLOBAL__sub_I_main:
.LFB968:
	.cfi_startproc
	pushl	%ebp
	.cfi_def_cfa_offset 8
	.cfi_offset 5, -8
	movl	%esp, %ebp
	.cfi_def_cfa_register 5
	subl	$24, %esp
	movl	$65535, 4(%esp)
	movl	$1, (%esp)
	call	_Z41__static_initialization_and_destruction_0ii
	leave
	.cfi_restore 5
	.cfi_def_cfa 4, 4
	ret
	.cfi_endproc
.LFE968:
	.size	_GLOBAL__sub_I_main, .-_GLOBAL__sub_I_main
	.section	.ctors,"aw",@progbits
	.align 4
	.long	_GLOBAL__sub_I_main
	.weakref	_ZL20__gthrw_pthread_oncePiPFvvE,pthread_once
	.weakref	_ZL27__gthrw_pthread_getspecificj,pthread_getspecific
	.weakref	_ZL27__gthrw_pthread_setspecificjPKv,pthread_setspecific
	.weakref	_ZL22__gthrw_pthread_createPmPK14pthread_attr_tPFPvS3_ES3_,pthread_create
	.weakref	_ZL20__gthrw_pthread_joinmPPv,pthread_join
	.weakref	_ZL21__gthrw_pthread_equalmm,pthread_equal
	.weakref	_ZL20__gthrw_pthread_selfv,pthread_self
	.weakref	_ZL22__gthrw_pthread_detachm,pthread_detach
	.weakref	_ZL22__gthrw_pthread_cancelm,pthread_cancel
	.weakref	_ZL19__gthrw_sched_yieldv,sched_yield
	.weakref	_ZL26__gthrw_pthread_mutex_lockP15pthread_mutex_t,pthread_mutex_lock
	.weakref	_ZL29__gthrw_pthread_mutex_trylockP15pthread_mutex_t,pthread_mutex_trylock
	.weakref	_ZL31__gthrw_pthread_mutex_timedlockP15pthread_mutex_tPK8timespec,pthread_mutex_timedlock
	.weakref	_ZL28__gthrw_pthread_mutex_unlockP15pthread_mutex_t,pthread_mutex_unlock
	.weakref	_ZL26__gthrw_pthread_mutex_initP15pthread_mutex_tPK19pthread_mutexattr_t,pthread_mutex_init
	.weakref	_ZL29__gthrw_pthread_mutex_destroyP15pthread_mutex_t,pthread_mutex_destroy
	.weakref	_ZL30__gthrw_pthread_cond_broadcastP14pthread_cond_t,pthread_cond_broadcast
	.weakref	_ZL27__gthrw_pthread_cond_signalP14pthread_cond_t,pthread_cond_signal
	.weakref	_ZL25__gthrw_pthread_cond_waitP14pthread_cond_tP15pthread_mutex_t,pthread_cond_wait
	.weakref	_ZL30__gthrw_pthread_cond_timedwaitP14pthread_cond_tP15pthread_mutex_tPK8timespec,pthread_cond_timedwait
	.weakref	_ZL28__gthrw_pthread_cond_destroyP14pthread_cond_t,pthread_cond_destroy
	.weakref	_ZL26__gthrw_pthread_key_createPjPFvPvE,pthread_key_create
	.weakref	_ZL26__gthrw_pthread_key_deletej,pthread_key_delete
	.weakref	_ZL30__gthrw_pthread_mutexattr_initP19pthread_mutexattr_t,pthread_mutexattr_init
	.weakref	_ZL33__gthrw_pthread_mutexattr_settypeP19pthread_mutexattr_ti,pthread_mutexattr_settype
	.weakref	_ZL33__gthrw_pthread_mutexattr_destroyP19pthread_mutexattr_t,pthread_mutexattr_destroy
	.ident	"GCC: (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3"
	.section	.note.GNU-stack,"",@progbits


//let's change it further to test
//mult.h
#include <iostream>

using namespace std;

int multi(int a, int b);

//mult.cpp
#include "mult.h"

int multi(int a, int b)
{
  return a*b;
}
//hello.cpp
#include <iostream>
#include "mult.h"

using namespace std;

int Add(int a, int b)
{
  return a+b;
}

int main()
{
  int i=5;
  int j=6;
  int d = Add(i,j);
  int e = multi(i,j);
  int c = d+e;
  cout << "c is " << c << endl;
}
//g++ -S -o mult.s mult.cpp
	.file	"mult.cpp"
	.local	_ZStL8__ioinit
	.comm	_ZStL8__ioinit,1,1
	.text
	.globl	_Z5multiii
	.type	_Z5multiii, @function
_Z5multiii:
.LFB966:
	.cfi_startproc
	pushl	%ebp
	.cfi_def_cfa_offset 8
	.cfi_offset 5, -8
	movl	%esp, %ebp
	.cfi_def_cfa_register 5
	movl	8(%ebp), %eax
	imull	12(%ebp), %eax
	popl	%ebp
	.cfi_def_cfa 4, 4
	.cfi_restore 5
	ret
	.cfi_endproc
.LFE966:
	.size	_Z5multiii, .-_Z5multiii
	.type	_Z41__static_initialization_and_destruction_0ii, @function
_Z41__static_initialization_and_destruction_0ii:
.LFB967:
	.cfi_startproc
	pushl	%ebp
	.cfi_def_cfa_offset 8
	.cfi_offset 5, -8
	movl	%esp, %ebp
	.cfi_def_cfa_register 5
	subl	$24, %esp
	cmpl	$1, 8(%ebp)
	jne	.L2
	cmpl	$65535, 12(%ebp)
	jne	.L2
	movl	$_ZStL8__ioinit, (%esp)
	call	_ZNSt8ios_base4InitC1Ev
	movl	$_ZNSt8ios_base4InitD1Ev, %eax
	movl	$__dso_handle, 8(%esp)
	movl	$_ZStL8__ioinit, 4(%esp)
	movl	%eax, (%esp)
	call	__cxa_atexit
.L2:
	leave
	.cfi_restore 5
	.cfi_def_cfa 4, 4
	ret
	.cfi_endproc
.LFE967:
	.size	_Z41__static_initialization_and_destruction_0ii, .-_Z41__static_initialization_and_destruction_0ii
	.type	_GLOBAL__sub_I__Z5multiii, @function
_GLOBAL__sub_I__Z5multiii:
.LFB968:
	.cfi_startproc
	pushl	%ebp
	.cfi_def_cfa_offset 8
	.cfi_offset 5, -8
	movl	%esp, %ebp
	.cfi_def_cfa_register 5
	subl	$24, %esp
	movl	$65535, 4(%esp)
	movl	$1, (%esp)
	call	_Z41__static_initialization_and_destruction_0ii
	leave
	.cfi_restore 5
	.cfi_def_cfa 4, 4
	ret
	.cfi_endproc
.LFE968:
	.size	_GLOBAL__sub_I__Z5multiii, .-_GLOBAL__sub_I__Z5multiii
	.section	.ctors,"aw",@progbits
	.align 4
	.long	_GLOBAL__sub_I__Z5multiii
	.weakref	_ZL20__gthrw_pthread_oncePiPFvvE,pthread_once
	.weakref	_ZL27__gthrw_pthread_getspecificj,pthread_getspecific
	.weakref	_ZL27__gthrw_pthread_setspecificjPKv,pthread_setspecific
	.weakref	_ZL22__gthrw_pthread_createPmPK14pthread_attr_tPFPvS3_ES3_,pthread_create
	.weakref	_ZL20__gthrw_pthread_joinmPPv,pthread_join
	.weakref	_ZL21__gthrw_pthread_equalmm,pthread_equal
	.weakref	_ZL20__gthrw_pthread_selfv,pthread_self
	.weakref	_ZL22__gthrw_pthread_detachm,pthread_detach
	.weakref	_ZL22__gthrw_pthread_cancelm,pthread_cancel
	.weakref	_ZL19__gthrw_sched_yieldv,sched_yield
	.weakref	_ZL26__gthrw_pthread_mutex_lockP15pthread_mutex_t,pthread_mutex_lock
	.weakref	_ZL29__gthrw_pthread_mutex_trylockP15pthread_mutex_t,pthread_mutex_trylock
	.weakref	_ZL31__gthrw_pthread_mutex_timedlockP15pthread_mutex_tPK8timespec,pthread_mutex_timedlock
	.weakref	_ZL28__gthrw_pthread_mutex_unlockP15pthread_mutex_t,pthread_mutex_unlock
	.weakref	_ZL26__gthrw_pthread_mutex_initP15pthread_mutex_tPK19pthread_mutexattr_t,pthread_mutex_init
	.weakref	_ZL29__gthrw_pthread_mutex_destroyP15pthread_mutex_t,pthread_mutex_destroy
	.weakref	_ZL30__gthrw_pthread_cond_broadcastP14pthread_cond_t,pthread_cond_broadcast
	.weakref	_ZL27__gthrw_pthread_cond_signalP14pthread_cond_t,pthread_cond_signal
	.weakref	_ZL25__gthrw_pthread_cond_waitP14pthread_cond_tP15pthread_mutex_t,pthread_cond_wait
	.weakref	_ZL30__gthrw_pthread_cond_timedwaitP14pthread_cond_tP15pthread_mutex_tPK8timespec,pthread_cond_timedwait
	.weakref	_ZL28__gthrw_pthread_cond_destroyP14pthread_cond_t,pthread_cond_destroy
	.weakref	_ZL26__gthrw_pthread_key_createPjPFvPvE,pthread_key_create
	.weakref	_ZL26__gthrw_pthread_key_deletej,pthread_key_delete
	.weakref	_ZL30__gthrw_pthread_mutexattr_initP19pthread_mutexattr_t,pthread_mutexattr_init
	.weakref	_ZL33__gthrw_pthread_mutexattr_settypeP19pthread_mutexattr_ti,pthread_mutexattr_settype
	.weakref	_ZL33__gthrw_pthread_mutexattr_destroyP19pthread_mutexattr_t,pthread_mutexattr_destroy
	.ident	"GCC: (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3"
	.section	.note.GNU-stack,"",@progbits
////g++ -S -o hello.s hello.cpp

	.file	"hello.cpp"
	.local	_ZStL8__ioinit
	.comm	_ZStL8__ioinit,1,1
	.text
	.globl	_Z3Addii
	.type	_Z3Addii, @function
_Z3Addii:
.LFB966:
	.cfi_startproc
	pushl	%ebp
	.cfi_def_cfa_offset 8
	.cfi_offset 5, -8
	movl	%esp, %ebp
	.cfi_def_cfa_register 5
	movl	12(%ebp), %eax
	movl	8(%ebp), %edx
	addl	%edx, %eax
	popl	%ebp
	.cfi_def_cfa 4, 4
	.cfi_restore 5
	ret
	.cfi_endproc
.LFE966:
	.size	_Z3Addii, .-_Z3Addii
	.section	.rodata
.LC0:
	.string	"c is "
	.text
	.globl	main
	.type	main, @function
main:
.LFB967:
	.cfi_startproc
	pushl	%ebp
	.cfi_def_cfa_offset 8
	.cfi_offset 5, -8
	movl	%esp, %ebp
	.cfi_def_cfa_register 5
	andl	$-16, %esp
	subl	$48, %esp
	movl	$5, 28(%esp)
	movl	$6, 32(%esp)
	movl	32(%esp), %eax
	movl	%eax, 4(%esp)
	movl	28(%esp), %eax
	movl	%eax, (%esp)
	call	_Z3Addii
	movl	%eax, 36(%esp)
	movl	32(%esp), %eax
	movl	%eax, 4(%esp)
	movl	28(%esp), %eax
	movl	%eax, (%esp)
	call	_Z5multiii
	movl	%eax, 40(%esp)
	movl	40(%esp), %eax
	movl	36(%esp), %edx
	addl	%edx, %eax
	movl	%eax, 44(%esp)
	movl	$.LC0, 4(%esp)
	movl	$_ZSt4cout, (%esp)
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	movl	44(%esp), %edx
	movl	%edx, 4(%esp)
	movl	%eax, (%esp)
	call	_ZNSolsEi
	movl	$_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_, 4(%esp)
	movl	%eax, (%esp)
	call	_ZNSolsEPFRSoS_E
	movl	$0, %eax
	leave
	.cfi_restore 5
	.cfi_def_cfa 4, 4
	ret
	.cfi_endproc
.LFE967:
	.size	main, .-main
	.type	_Z41__static_initialization_and_destruction_0ii, @function
_Z41__static_initialization_and_destruction_0ii:
.LFB976:
	.cfi_startproc
	pushl	%ebp
	.cfi_def_cfa_offset 8
	.cfi_offset 5, -8
	movl	%esp, %ebp
	.cfi_def_cfa_register 5
	subl	$24, %esp
	cmpl	$1, 8(%ebp)
	jne	.L3
	cmpl	$65535, 12(%ebp)
	jne	.L3
	movl	$_ZStL8__ioinit, (%esp)
	call	_ZNSt8ios_base4InitC1Ev
	movl	$_ZNSt8ios_base4InitD1Ev, %eax
	movl	$__dso_handle, 8(%esp)
	movl	$_ZStL8__ioinit, 4(%esp)
	movl	%eax, (%esp)
	call	__cxa_atexit
.L3:
	leave
	.cfi_restore 5
	.cfi_def_cfa 4, 4
	ret
	.cfi_endproc
.LFE976:
	.size	_Z41__static_initialization_and_destruction_0ii, .-_Z41__static_initialization_and_destruction_0ii
	.type	_GLOBAL__sub_I__Z3Addii, @function
_GLOBAL__sub_I__Z3Addii:
.LFB977:
	.cfi_startproc
	pushl	%ebp
	.cfi_def_cfa_offset 8
	.cfi_offset 5, -8
	movl	%esp, %ebp
	.cfi_def_cfa_register 5
	subl	$24, %esp
	movl	$65535, 4(%esp)
	movl	$1, (%esp)
	call	_Z41__static_initialization_and_destruction_0ii
	leave
	.cfi_restore 5
	.cfi_def_cfa 4, 4
	ret
	.cfi_endproc
.LFE977:
	.size	_GLOBAL__sub_I__Z3Addii, .-_GLOBAL__sub_I__Z3Addii
	.section	.ctors,"aw",@progbits
	.align 4
	.long	_GLOBAL__sub_I__Z3Addii
	.weakref	_ZL20__gthrw_pthread_oncePiPFvvE,pthread_once
	.weakref	_ZL27__gthrw_pthread_getspecificj,pthread_getspecific
	.weakref	_ZL27__gthrw_pthread_setspecificjPKv,pthread_setspecific
	.weakref	_ZL22__gthrw_pthread_createPmPK14pthread_attr_tPFPvS3_ES3_,pthread_create
	.weakref	_ZL20__gthrw_pthread_joinmPPv,pthread_join
	.weakref	_ZL21__gthrw_pthread_equalmm,pthread_equal
	.weakref	_ZL20__gthrw_pthread_selfv,pthread_self
	.weakref	_ZL22__gthrw_pthread_detachm,pthread_detach
	.weakref	_ZL22__gthrw_pthread_cancelm,pthread_cancel
	.weakref	_ZL19__gthrw_sched_yieldv,sched_yield
	.weakref	_ZL26__gthrw_pthread_mutex_lockP15pthread_mutex_t,pthread_mutex_lock
	.weakref	_ZL29__gthrw_pthread_mutex_trylockP15pthread_mutex_t,pthread_mutex_trylock
	.weakref	_ZL31__gthrw_pthread_mutex_timedlockP15pthread_mutex_tPK8timespec,pthread_mutex_timedlock
	.weakref	_ZL28__gthrw_pthread_mutex_unlockP15pthread_mutex_t,pthread_mutex_unlock
	.weakref	_ZL26__gthrw_pthread_mutex_initP15pthread_mutex_tPK19pthread_mutexattr_t,pthread_mutex_init
	.weakref	_ZL29__gthrw_pthread_mutex_destroyP15pthread_mutex_t,pthread_mutex_destroy
	.weakref	_ZL30__gthrw_pthread_cond_broadcastP14pthread_cond_t,pthread_cond_broadcast
	.weakref	_ZL27__gthrw_pthread_cond_signalP14pthread_cond_t,pthread_cond_signal
	.weakref	_ZL25__gthrw_pthread_cond_waitP14pthread_cond_tP15pthread_mutex_t,pthread_cond_wait
	.weakref	_ZL30__gthrw_pthread_cond_timedwaitP14pthread_cond_tP15pthread_mutex_tPK8timespec,pthread_cond_timedwait
	.weakref	_ZL28__gthrw_pthread_cond_destroyP14pthread_cond_t,pthread_cond_destroy
	.weakref	_ZL26__gthrw_pthread_key_createPjPFvPvE,pthread_key_create
	.weakref	_ZL26__gthrw_pthread_key_deletej,pthread_key_delete
	.weakref	_ZL30__gthrw_pthread_mutexattr_initP19pthread_mutexattr_t,pthread_mutexattr_init
	.weakref	_ZL33__gthrw_pthread_mutexattr_settypeP19pthread_mutexattr_ti,pthread_mutexattr_settype
	.weakref	_ZL33__gthrw_pthread_mutexattr_destroyP19pthread_mutexattr_t,pthread_mutexattr_destroy
	.ident	"GCC: (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3"
	.section	.note.GNU-stack,"",@progbits
//finally, let's dump the object file to see the assembly, you could see that we have real address here!
//g++ -o hello mult.cpp hello.cpp
//objdump -d hello.o >dump.txt

hello.o:     file format elf32-i386


Disassembly of section .text:

00000000 <main>:
   0:	55                   	push   %ebp
   1:	89 e5                	mov    %esp,%ebp
   3:	83 ec 10             	sub    $0x10,%esp
   6:	c7 45 f4 02 00 00 00 	movl   $0x2,-0xc(%ebp)
   d:	c7 45 f8 03 00 00 00 	movl   $0x3,-0x8(%ebp)
  14:	8b 45 f8             	mov    -0x8(%ebp),%eax
  17:	8b 55 f4             	mov    -0xc(%ebp),%edx
  1a:	01 d0                	add    %edx,%eax
  1c:	89 45 fc             	mov    %eax,-0x4(%ebp)
  1f:	b8 00 00 00 00       	mov    $0x0,%eax
  24:	c9                   	leave  
  25:	c3                   	ret    

00000026 <_Z41__static_initialization_and_destruction_0ii>:
  26:	55                   	push   %ebp
  27:	89 e5                	mov    %esp,%ebp
  29:	83 ec 18             	sub    $0x18,%esp
  2c:	83 7d 08 01          	cmpl   $0x1,0x8(%ebp)
  30:	75 32                	jne    64 <_Z41__static_initialization_and_destruction_0ii+0x3e>
  32:	81 7d 0c ff ff 00 00 	cmpl   $0xffff,0xc(%ebp)
  39:	75 29                	jne    64 <_Z41__static_initialization_and_destruction_0ii+0x3e>
  3b:	c7 04 24 00 00 00 00 	movl   $0x0,(%esp)
  42:	e8 fc ff ff ff       	call   43 <_Z41__static_initialization_and_destruction_0ii+0x1d>
  47:	b8 00 00 00 00       	mov    $0x0,%eax
  4c:	c7 44 24 08 00 00 00 	movl   $0x0,0x8(%esp)
  53:	00 
  54:	c7 44 24 04 00 00 00 	movl   $0x0,0x4(%esp)
  5b:	00 
  5c:	89 04 24             	mov    %eax,(%esp)
  5f:	e8 fc ff ff ff       	call   60 <_Z41__static_initialization_and_destruction_0ii+0x3a>
  64:	c9                   	leave  
  65:	c3                   	ret    

00000066 <_GLOBAL__sub_I_main>:
  66:	55                   	push   %ebp
  67:	89 e5                	mov    %esp,%ebp
  69:	83 ec 18             	sub    $0x18,%esp
  6c:	c7 44 24 04 ff ff 00 	movl   $0xffff,0x4(%esp)
  73:	00 
  74:	c7 04 24 01 00 00 00 	movl   $0x1,(%esp)
  7b:	e8 a6 ff ff ff       	call   26 <_Z41__static_initialization_and_destruction_0ii>
  80:	c9                   	leave  
  81:	c3                   	ret    


//if we are interested in mult.o, we can:
//g++ -g -c mult.cpp -o mult.o
//objdump -d mult.o >mult.txt

mult.o:     file format elf32-i386


Disassembly of section .text:

00000000 <_Z5multiii>:
   0:	55                   	push   %ebp
   1:	89 e5                	mov    %esp,%ebp
   3:	8b 45 08             	mov    0x8(%ebp),%eax
   6:	0f af 45 0c          	imul   0xc(%ebp),%eax
   a:	5d                   	pop    %ebp
   b:	c3                   	ret    

0000000c <_Z41__static_initialization_and_destruction_0ii>:
   c:	55                   	push   %ebp
   d:	89 e5                	mov    %esp,%ebp
   f:	83 ec 18             	sub    $0x18,%esp
  12:	83 7d 08 01          	cmpl   $0x1,0x8(%ebp)
  16:	75 32                	jne    4a <_Z41__static_initialization_and_destruction_0ii+0x3e>
  18:	81 7d 0c ff ff 00 00 	cmpl   $0xffff,0xc(%ebp)
  1f:	75 29                	jne    4a <_Z41__static_initialization_and_destruction_0ii+0x3e>
  21:	c7 04 24 00 00 00 00 	movl   $0x0,(%esp)
  28:	e8 fc ff ff ff       	call   29 <_Z41__static_initialization_and_destruction_0ii+0x1d>
  2d:	b8 00 00 00 00       	mov    $0x0,%eax
  32:	c7 44 24 08 00 00 00 	movl   $0x0,0x8(%esp)
  39:	00 
  3a:	c7 44 24 04 00 00 00 	movl   $0x0,0x4(%esp)
  41:	00 
  42:	89 04 24             	mov    %eax,(%esp)
  45:	e8 fc ff ff ff       	call   46 <_Z41__static_initialization_and_destruction_0ii+0x3a>
  4a:	c9                   	leave  
  4b:	c3                   	ret    

0000004c <_GLOBAL__sub_I__Z5multiii>:
  4c:	55                   	push   %ebp
  4d:	89 e5                	mov    %esp,%ebp
  4f:	83 ec 18             	sub    $0x18,%esp
  52:	c7 44 24 04 ff ff 00 	movl   $0xffff,0x4(%esp)
  59:	00 
  5a:	c7 04 24 01 00 00 00 	movl   $0x1,(%esp)
  61:	e8 a6 ff ff ff       	call   c <_Z41__static_initialization_and_destruction_0ii>
  66:	c9                   	leave  
  67:	c3                   	ret    
//what if we only create object from hello.cpp? 
//you will see this is different w/ the hello.o which is final file from both mult.cpp and hello.cpp

// g++ -g -c hello.cpp -o hello.o
// objdump -d hello.o >hello.txt

hello.o:     file format elf32-i386


Disassembly of section .text:

00000000 :
   0:	55                   	push   %ebp
   1:	89 e5                	mov    %esp,%ebp
   3:	8b 45 0c             	mov    0xc(%ebp),%eax
   6:	8b 55 08             	mov    0x8(%ebp),%edx
   9:	01 d0                	add    %edx,%eax
   b:	5d                   	pop    %ebp
   c:	c3                   	ret    

0000000d :
   d:	55                   	push   %ebp
   e:	89 e5                	mov    %esp,%ebp
  10:	83 e4 f0             	and    $0xfffffff0,%esp
  13:	83 ec 30             	sub    $0x30,%esp
  16:	c7 44 24 1c 05 00 00 	movl   $0x5,0x1c(%esp)
  1d:	00 
  1e:	c7 44 24 20 06 00 00 	movl   $0x6,0x20(%esp)
  25:	00 
  26:	8b 44 24 20          	mov    0x20(%esp),%eax
  2a:	89 44 24 04          	mov    %eax,0x4(%esp)
  2e:	8b 44 24 1c          	mov    0x1c(%esp),%eax
  32:	89 04 24             	mov    %eax,(%esp)
  35:	e8 fc ff ff ff       	call   36 
  3a:	89 44 24 24          	mov    %eax,0x24(%esp)
  3e:	8b 44 24 20          	mov    0x20(%esp),%eax
  42:	89 44 24 04          	mov    %eax,0x4(%esp)
  46:	8b 44 24 1c          	mov    0x1c(%esp),%eax
  4a:	89 04 24             	mov    %eax,(%esp)
  4d:	e8 fc ff ff ff       	call   4e 
  52:	89 44 24 28          	mov    %eax,0x28(%esp)
  56:	8b 44 24 28          	mov    0x28(%esp),%eax
  5a:	8b 54 24 24          	mov    0x24(%esp),%edx
  5e:	01 d0                	add    %edx,%eax
  60:	89 44 24 2c          	mov    %eax,0x2c(%esp)
  64:	c7 44 24 04 00 00 00 	movl   $0x0,0x4(%esp)
  6b:	00 
  6c:	c7 04 24 00 00 00 00 	movl   $0x0,(%esp)
  73:	e8 fc ff ff ff       	call   74 
  78:	8b 54 24 2c          	mov    0x2c(%esp),%edx
  7c:	89 54 24 04          	mov    %edx,0x4(%esp)
  80:	89 04 24             	mov    %eax,(%esp)
  83:	e8 fc ff ff ff       	call   84 
  88:	c7 44 24 04 00 00 00 	movl   $0x0,0x4(%esp)
  8f:	00 
  90:	89 04 24             	mov    %eax,(%esp)
  93:	e8 fc ff ff ff       	call   94 
  98:	b8 00 00 00 00       	mov    $0x0,%eax
  9d:	c9                   	leave  
  9e:	c3                   	ret    

0000009f :
  9f:	55                   	push   %ebp
  a0:	89 e5                	mov    %esp,%ebp
  a2:	83 ec 18             	sub    $0x18,%esp
  a5:	83 7d 08 01          	cmpl   $0x1,0x8(%ebp)
  a9:	75 32                	jne    dd 
  ab:	81 7d 0c ff ff 00 00 	cmpl   $0xffff,0xc(%ebp)
  b2:	75 29                	jne    dd 
  b4:	c7 04 24 00 00 00 00 	movl   $0x0,(%esp)
  bb:	e8 fc ff ff ff       	call   bc 
  c0:	b8 00 00 00 00       	mov    $0x0,%eax
  c5:	c7 44 24 08 00 00 00 	movl   $0x0,0x8(%esp)
  cc:	00 
  cd:	c7 44 24 04 00 00 00 	movl   $0x0,0x4(%esp)
  d4:	00 
  d5:	89 04 24             	mov    %eax,(%esp)
  d8:	e8 fc ff ff ff       	call   d9 
  dd:	c9                   	leave  
  de:	c3                   	ret    

000000df :
  df:	55                   	push   %ebp
  e0:	89 e5                	mov    %esp,%ebp
  e2:	83 ec 18             	sub    $0x18,%esp
  e5:	c7 44 24 04 ff ff 00 	movl   $0xffff,0x4(%esp)
  ec:	00 
  ed:	c7 04 24 01 00 00 00 	movl   $0x1,(%esp)
  f4:	e8 a6 ff ff ff       	call   9f 
  f9:	c9                   	leave  
  fa:	c3                   	ret    

useful bookmark summary

Tags

compiler phases

Tags

compiler

http://stackoverflow.com/questions/11172287/what-is-the-lexical-and-syntactic-analysis-during-the-process-of-compiling-in-c

Consider this code:

     int a = 10;
     if (a < 4)
     {
          printf("%d",a);
     }

In the Lexical Analysis phase: You identify each word/token and assign a meaning to it. In the code above, you start by identifying that i followed by n followed by t and then a space is the wordint, and that it is a language keyword;1 followed by 0 and a space is a number 10 and so on.

In the Syntactic Analysis phase: You verify whether the code follows the language syntax(grammar rules). For example, you check whether there is only one variable on the LHS of an operator(considering language C), that each statement is terminated by a ;, that if is followed by a conditional/Boolean statement etc.

Binary Tree Inorder Traversal

Tags

/*
===>requirements:
Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

===>my comments:
write recursive method first before analysis:
        if(!root)
            return
        it(root->left)
        printout(root)
        it(root->right)

*/

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {       
        List<Integer> l = new ArrayList<Integer>();
        if(root == null)
            return l;
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode cur = root;
        while(!s.empty() || cur!=null)
        {
            if(cur != null)
            {
                s.push(cur);
                cur = cur.left;
            }
            else
            {
                cur = s.pop();
                l.add(cur.val);
                cur = cur.right;
            }
        }
        return l;
    }
}

Insertion Sort List

Tags

,

=======Java===========
/*
Sort a linked list using insertion sort.
"https://www.princeton.edu/~achaney/tmve/wiki100k/docs/Insertion_sort.html"
make sure you understand what is insertion sort first! The whole idea is, have one sorted list, and another unsorted remaining list. now, for each item in the remaining list, insert it into the sorted list.
Pay attention to how fake head is used here: sortedHd, which is pretty common in linked list related algorithm.

T(N) = O(N^2)
space: O(1)

*/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null)
            return null;
        //make a fake head to represent the sorted-list
        ListNode sortedHd = new ListNode(0);
        //current code which will be inserted into the sorted-list
        ListNode cur = head;
        while(cur != null)
        {
            ListNode sortedNd = sortedHd;
            //find the first value in sorted-list which is larger than cur.val
            while(sortedNd.next != null && sortedNd.next.val <= cur.val)
                sortedNd = sortedNd.next;
            //now, cur should be inserted after sortedNd
            ListNode curNext = cur.next;
            cur.next = sortedNd.next;
            sortedNd.next = cur;
            cur = curNext;
        }
        return sortedHd.next;
    }
}