A Basic heap implementation in C++

Why use a heap?

A heap can be thought of as a priority queue; the most important node will always be at the top, and when removed, its replacement will be the most important. This can be useful when coding algorithms that require certain things to processed in a complete order, but when you don’t want to perform a full sort or need to know anything about the rest of the nodes. For instance, a well-known algorithm for finding the shortest distance between nodes in a graph, Dijkstra’s Algorithm, can be optimized by using a priority queue. Here an ample explanation of how the heap data structure works…

https://github.com/pianodaemon/cpp_magic/tree/master/algorithms_experiences/basic_heap

Anuncios

C functions linkage in C++

Hi everybody
To know what will happens with this example I’ll use the nm command (but you could also use readelf -s) which can list symbols from object files.

The main actor extern C
The extern C makes a function-name in C++ have C linkage, so that client C code can link to your function using a ‘C’ compatible header file that contains just the declaration of your function. Your function definition is contained in a binary format (that was compiled by your C++ compiler) that the client ‘C’ linker will then link to using the C name.

Before extern C

#include <stdio.h>

void
hola()
{
   printf("hello");
}

int main(){
   return 0;
   hola();
}
[eplauchu@eplauchu ~]$ gcc borrame.c -o 0.out && nm 0.out 
0000000000601034 B __bss_start
0000000000601034 b completed.6344
0000000000601030 D __data_start
0000000000601030 W data_start
0000000000400470 t deregister_tm_clones
00000000004004e0 t __do_global_dtors_aux
0000000000600e18 t __do_global_dtors_aux_fini_array_entry
00000000004005d8 R __dso_handle
0000000000600e28 d _DYNAMIC
0000000000601034 D _edata
0000000000601038 B _end
00000000004005c4 T _fini
0000000000400500 t frame_dummy
0000000000600e10 t __frame_dummy_init_array_entry
0000000000400738 r __FRAME_END__
0000000000601000 d _GLOBAL_OFFSET_TABLE_
                 w __gmon_start__
000000000040052d T hola
00000000004003e0 T _init
0000000000600e18 t __init_array_end
0000000000600e10 t __init_array_start
00000000004005d0 R _IO_stdin_used
                 w _ITM_deregisterTMCloneTable
                 w _ITM_registerTMCloneTable
0000000000600e20 d __JCR_END__
0000000000600e20 d __JCR_LIST__
                 w _Jv_RegisterClasses
00000000004005c0 T __libc_csu_fini
0000000000400550 T __libc_csu_init
                 U __libc_start_main@@GLIBC_2.2.5
0000000000400542 T main
                 U printf@@GLIBC_2.2.5
00000000004004a0 t register_tm_clones
0000000000400440 T _start
0000000000601038 D __TMC_END__
[eplauchu@eplauchu ~]$ g++ borrame.c -o 1.out && nm 1.out 
0000000000601034 B __bss_start
0000000000601034 b completed.6344
0000000000601030 D __data_start
0000000000601030 W data_start
0000000000400530 t deregister_tm_clones
00000000004005a0 t __do_global_dtors_aux
0000000000600de8 t __do_global_dtors_aux_fini_array_entry
0000000000400698 R __dso_handle
0000000000600df8 d _DYNAMIC
0000000000601034 D _edata
0000000000601038 B _end
0000000000400684 T _fini
00000000004005c0 t frame_dummy
0000000000600de0 t __frame_dummy_init_array_entry
00000000004007f8 r __FRAME_END__
0000000000601000 d _GLOBAL_OFFSET_TABLE_
                 w __gmon_start__
00000000004004a0 T _init
0000000000600de8 t __init_array_end
0000000000600de0 t __init_array_start
0000000000400690 R _IO_stdin_used
                 w _ITM_deregisterTMCloneTable
                 w _ITM_registerTMCloneTable
0000000000600df0 d __JCR_END__
0000000000600df0 d __JCR_LIST__
                 w _Jv_RegisterClasses
0000000000400680 T __libc_csu_fini
0000000000400610 T __libc_csu_init
                 U __libc_start_main@@GLIBC_2.2.5
0000000000400602 T main
                 U printf@@GLIBC_2.2.5
0000000000400560 t register_tm_clones
0000000000400500 T _start
0000000000601038 D __TMC_END__
00000000004005ed T _Z4holav

After extern C

#include <stdio.h>

#ifdef __cplusplus
extern "C"
{
#endif

void
hola()
{
   printf("hello");
}

#ifdef __cplusplus
};
#endif

int main(){
   return 0;
   hola();
}

[eplauchu@eplauchu ~]$ gcc borrame.c -o 0.out && nm 0.out 
0000000000601034 B __bss_start
0000000000601034 b completed.6344
0000000000601030 D __data_start
0000000000601030 W data_start
0000000000400470 t deregister_tm_clones
00000000004004e0 t __do_global_dtors_aux
0000000000600e18 t __do_global_dtors_aux_fini_array_entry
00000000004005d8 R __dso_handle
0000000000600e28 d _DYNAMIC
0000000000601034 D _edata
0000000000601038 B _end
00000000004005c4 T _fini
0000000000400500 t frame_dummy
0000000000600e10 t __frame_dummy_init_array_entry
0000000000400738 r __FRAME_END__
0000000000601000 d _GLOBAL_OFFSET_TABLE_
                 w __gmon_start__
000000000040052d T hola
00000000004003e0 T _init
0000000000600e18 t __init_array_end
0000000000600e10 t __init_array_start
00000000004005d0 R _IO_stdin_used
                 w _ITM_deregisterTMCloneTable
                 w _ITM_registerTMCloneTable
0000000000600e20 d __JCR_END__
0000000000600e20 d __JCR_LIST__
                 w _Jv_RegisterClasses
00000000004005c0 T __libc_csu_fini
0000000000400550 T __libc_csu_init
                 U __libc_start_main@@GLIBC_2.2.5
0000000000400542 T main
                 U printf@@GLIBC_2.2.5
00000000004004a0 t register_tm_clones
0000000000400440 T _start
0000000000601038 D __TMC_END__
[eplauchu@eplauchu ~]$ g++ borrame.c -o 1.out && nm 1.out 
0000000000601034 B __bss_start
0000000000601034 b completed.6344
0000000000601030 D __data_start
0000000000601030 W data_start
0000000000400530 t deregister_tm_clones
00000000004005a0 t __do_global_dtors_aux
0000000000600de8 t __do_global_dtors_aux_fini_array_entry
0000000000400698 R __dso_handle
0000000000600df8 d _DYNAMIC
0000000000601034 D _edata
0000000000601038 B _end
0000000000400684 T _fini
00000000004005c0 t frame_dummy
0000000000600de0 t __frame_dummy_init_array_entry
00000000004007f8 r __FRAME_END__
0000000000601000 d _GLOBAL_OFFSET_TABLE_
                 w __gmon_start__
00000000004005ed T hola
00000000004004a0 T _init
0000000000600de8 t __init_array_end
0000000000600de0 t __init_array_start
0000000000400690 R _IO_stdin_used
                 w _ITM_deregisterTMCloneTable
                 w _ITM_registerTMCloneTable
0000000000600df0 d __JCR_END__
0000000000600df0 d __JCR_LIST__
                 w _Jv_RegisterClasses
0000000000400680 T __libc_csu_fini
0000000000400610 T __libc_csu_init
                 U __libc_start_main@@GLIBC_2.2.5
0000000000400602 T main
                 U printf@@GLIBC_2.2.5
0000000000400560 t register_tm_clones
0000000000400500 T _start
0000000000601038 D __TMC_END__