aarklon-news

power pc 7448 sbc board

2009-11-15T00:22:00.001-08:00

short- circuiting example

2009-07-12T08:22:00.001-07:00

Symmetric Key Encryption

2009-06-25T11:06:00.000-07:00

The most basic form of encryption is symmetric key encryption, so named because both the sender and the receiver of the data use the same key to encrypt and decrypt the data. The problem with symmetric key encryption is that you must have a secure way to transport the encryption key to individuals you wish to exchange data with. If you do not use a secure method to send the key to a recipient, someone may intercept the key. This makes encryption useless, because now the interceptor
can decrypt the data knowing the key. In addition, if you are using encryption techniques for multiple recipients, you may not want one person to have access to another’s data. Now you must keep multiple single keys per person, which can become extremely cumbersome.

Stream Cipher

2009-06-25T11:00:00.001-07:00

Stream cipher algorithms encrypt data one bit at a time. Plain text bits are converted into encrypted cipher text. This method is usually not as secure as block cipher techniques, but it generally executes faster. In addition, the cipher text is always the same size as the original plain text and is less prone to errors. If an error occurs during the encryption process, usually this affects only a single bit instead of the whole string. In contrast, when block ciphers contain errors, the entire block becomes unintelligible.

block cipher

2009-06-25T10:58:00.000-07:00

Instead of encrypting a bit at a time, block cipher algorithms encrypt data in blocks. Block ciphers also have more overhead than stream ciphers, which is provided separately depending on the implementation and the block size that can be modified (the most common size being 64 bits). Because it handles encryption at a higher level, it is generally more secure. The downside is that the execution takes longer. Numerous block cipher options are available, such as Electronic Codebook (ECB), Cipher Block Chaining (CBC), Cipher Feedback (CFB), and Output Feedback Mode (OFB).

D.E.S

2009-06-25T10:54:00.000-07:00

The Data Encryption Standard (DES) was created and standardized by IBM in 1977. It is a 64-bit block symmetric algorithm and is specified in the ANSI X3.92 and X3.106 standards for both enciphering and deciphering operations, which are based on a binary number. In addition, the National Security Agency (NSA) uses it as the standard for all government organizations. There currently exist 72 quadrillion (72,000,000,000,000,000) encryption keys for DES, in which a key is chosen at random. DES uses a block cipher methodology to apply a 56-bit symmetric key to each 64-bit block. An additional form of DES, known as triple DES, applies three keys in succession to each block.

The dining philosophers

2009-03-15T11:32:00.000-07:00

Binky The Pointer fun Video

2009-01-20T09:51:00.000-08:00

strace, ltrace, mtrace

2009-01-11T22:10:00.000-08:00

strace

the strace utility traces all the system calls and signals for the specified program.

ltrace
it traces calls to the dynamic libraries

Ex:-

user@ubuntu:~$ ltrace -t ./hello1
11:39:31 __libc_start_main(0x8048374, 1, 0xbf804e64, 0x80483e0, 0x80483d0
11:39:31 puts("./hello1"./hello1
) = 9
11:39:31 puts("Hello World....."Hello World.....
) = 17
11:39:31 +++ exited (status 0) +++

see man ltrace for more details

mtrace

the mtrace utility is used to trace the use of dynamic memory by a program. it keeps track of the memory allocation and de- allocation operations; it traces memory leaks.

To pin down all potential memory leak areas in your program, you will have to perform the following sequence of steps

1) include the mcheck.h file in the program and place an mtrace() function call at the start of the program .

2) then specify the name of the file, in which memory checking resulots should be stored, by exporting the name into an environment variable, as in the following example

export MALLOC_TRACE=mem.log

running the program now will register all memory alllocating and freeing operations in the mem.log file. Finally, the mtrace utility is called as follows

mtrace your_prog $MALLOC_TRACE

The produced information is examined for records, in which memory was allocated but not freed. For the described procedure to succeed,the program under investigation must terminate normally

ldd, Strings and hexdump utilities

2009-01-11T21:43:00.000-08:00

Ldd

the ldd utility displays all the shared libraries required by each program

Ex:- ldd ./myprogram

strings

the strings utility displays strings of printable ASCII characters in a file longer than four characters.

Ex:-

user@ubuntu:~$ strings ./hello1
/lib/ld-linux.so.2
__gmon_start__
libc.so.6
_IO_stdin_used
puts
__libc_start_main
GLIBC_2.0
PTRh
QVht
[^_]
Hello World.....

Hexdump and od

The hexdump utility displays the contents of the specified file in the deciomal (-d), hexadecimal (-x), octal (-b) and ASCII (-c) modes.

Ex:-
hexdump -c ./yourprog

The od utility is analogous to the hexdump utility.

Nm ,Strip and Size utilities

2008-12-24T00:42:00.000-08:00

Nm utility

The nm utility outputs to the standard device a table of symbols for each file specified in the argument list.symbol tables arec used to debug applications. The utility displays the name of each symbol and in formation about its type: a data symbol(a variable), a program symbol (a label or a function name), and so on.

Ex:-

nm ./hello1
./hello1:
080494bc d _DYNAMIC
08049590 d _GLOBAL_OFFSET_TABLE_
0804848c R _IO_stdin_used
w _Jv_RegisterClasses
080494ac d __CTOR_END__
080494a8 d __CTOR_LIST__
080494b4 d __DTOR_END__
080494b0 d __DTOR_LIST__
080484a4 r __FRAME_END__
080494b8 d __JCR_END__
080494b8 d __JCR_LIST__
080495b4 A __bss_start
080495a8 D __data_start
08048440 t __do_global_ctors_aux
08048320 t __do_global_dtors_aux
080495ac D __dso_handle
w __gmon_start__
0804843a T __i686.get_pc_thunk.bx
080494a8 d __init_array_end
080494a8 d __init_array_start
080483d0 T __libc_csu_fini
080483e0 T __libc_csu_init
U __libc_start_main@@GLIBC_2.0
080495b4 A _edata
080495b8 A _end
0804846c T _fini
08048488 R _fp_hw
08048274 T _init
080482f0 T _start
080495b4 b completed.5843
080495a8 W data_start
08048350 t frame_dummy
08048374 T main
080495b0 d p.5841
U puts@@GLIBC_2.0

Strip utility

when a program has been debugged, the symbol table can be deleted from it. This is accomplished using the strip utility.

ex:- strip ./your_prog

Size

The size utility displays section sizes in each of the specified files. By default, the size of only the command(.text) , data (.data), and un -initialized data (.bss) sections and the total size of these sections are listed in the decimal and hexadecimal format.

to list the sizes of all sections in the file, the -A flag is used.

Ex:-

size ./hello1
text data bss dec hex filename
852 268 4 1124 464 ./hello1

Ex:-

size -A ./hello1
./hello1 :
section size addr
.interp 19 134512916
.note.ABI-tag 32 134512936
.hash 40 134512968
.gnu.hash 32 134513008
.dynsym 80 134513040
.dynstr 74 134513120
.gnu.version 10 134513194
.gnu.version_r 32 134513204
.rel.dyn 8 134513236
.rel.plt 24 134513244
.init 48 134513268
.plt 64 134513316
.text 380 134513392
.fini 28 134513772
.rodata 25 134513800
.eh_frame 4 134513828
.ctors 8 134517928
.dtors 8 134517936
.jcr 4 134517944
.dynamic 208 134517948
.got 4 134518156
.got.plt 24 134518160
.data 12 134518184
.bss 4 134518196
.comment 294 0
.debug_aranges 112 0
.debug_pubnames 64 0
.debug_info 770 0
.debug_abbrev 215 0
.debug_line 358 0
.debug_frame 80 0
.debug_str 187 0
.debug_loc 67 0
.debug_ranges 64 0
Total 3383

NB:- verified on gcc version 4.2.4

polynomial accumalation

2008-12-23T21:06:00.000-08:00

aarklon

the following is what i have seen about polynomial accumulation

http://s529.photobucket.com/albums/dd339/aarklon/?action=view¤t=Screenshot4.png

in the lecture by naveen garg

now my question is on what basis/grounds the values 33,37,39 or 41 is chosen so that it gives only atmost 6 collisions on a vocabulary of 50,000 English words ?

Tobby

Educated guess, trial and error? Or you could use a tool like gperf to construct a perfect hashing function for a predetermined vocabulary: http://www.gnu.org/software/gperf/

stream cipher

2008-12-15T20:22:00.001-08:00

source cisco

"C A Dying Skill"

2008-10-19T09:22:00.000-07:00

linvin

Came across this article in the ComputerWorld website which has included C in the top ten dying languages.

The top 10 dead (or dying) computer skills
http://www.computerworld.com/action/article.do?command=viewArticleBas...

To quote from the article

6. C programming
As the Web takes over, C languages are also becoming less relevant,according to Padveen. "C++ and C Sharp are still alive and kicking, but try to find a basic C-only programmer today, and you'll likely find a guy that's unemployed and/or training for a new skill," he
says."

I personally feel the authors have done very little research on evaluating C to relegate it to a obsolete langauage.

Richard Heathfield

Linny said:

> Came across this article in the ComputerWorld website which has
> included C in the top ten dying languages.

If you can't at least /read/ C, you're cutting yourself off from the huge amount of knowledge to be found in the literature, because so much of it is expressed in C. And if you can't /write/ C, you're not going to be a great deal of use in an embedded systems shop. Nor will you be as employable to a Unix site as someone who /can/ write C.

Like all such lists, it seems to have been put together by someone whose expertise rests not so much in what he's listing as in his ability to make lists.

blufox

> To quote from the article

>
> 6. C programming
> As the Web takes over, C languages are also becoming less relevant,
> according to Padveen. "C++ and C Sharp are still alive and kicking,
> but try to find a basic C-only programmer today, and you'll likely
> find a guy that's unemployed and/or training for a new skill," he
> says."

The guy is either suffering from brain tumour/down's syndrome or is severly mentally retarted.
Did he even program in C?

All crap stuff from some luser.How about embedded world, go write programs in .NET or Java for it.
Kernels still use C. And yes he doesn't find some basic C-only programmer because they are
not interested in being spotted by a braindead random article write who has no knowledge of C.

huh...C is dead, utter nonsense.

And yes maybe he went to Redmond to figure out that they program their
OS in .NET and what not which is not *C*.

Malcom mclean

There's a bit of truth in it. If you just know C and no other language, and you don't have any other skill, such as a knowledge of biochemistry, then opportunities for employment will be limited.

However C is the default language for specifying algorithms. The Graphics Gems series invited submissions in any language, and every single routine submitted was in C.

There are way too many programming languages. I've got perl scripts, shell scripts, C and C++, Fortran and Java programs, all of which do essentially the same things - iterate over datasets in loops, move information from one palce to another, and do a few arithemtical calculations. There's no real reason they couldn't all be written in a common language, but C graphics won't work on the website, I've legacy Fortran, C has no portable directory operations so database hits are better in Perl, C++ is virtually gibberish and there is no way I could inflict it on the non-IT background people, and
so on.

Then I've added to the mix with MinBasic and BASICdraw. So I suppose I am just as responsible.

Rui maciel

Linny wrote:
> To quote from the article

>
> 6. C programming
> As the Web takes over, C languages are also becoming less relevant,
> according to Padveen. "C++ and C Sharp are still alive and kicking,
> but try to find a basic C-only programmer today, and you'll likely
> find a guy that's unemployed and/or training for a new skill," he
> says."
>

The author is an idiot. First he tries to claim that C programming is a dying computer skill but then the only thing that he tries to claim is that, by his own account, C-only programmers are "unemployed and/or training for a new skill". Heck, my area is not CS and, besides C, I have
learnt three other programming languages. Although I've been writing C exclusively for about a year at my job, according to the author's metrics I would've been included in the group supporting the claim that C is a dying art.

Moreover, nowadays every CS graduate is not a C-only programmer. So,according to the author's metrics, all CS graduates could be writing C code for a living and that would still point out that C programming is a dying art.

And let's not even delve into the "C languages" bit. The author is an idiot from start to end.

Jacob Navia

lcc-win32 has a sustained download rate of around 500/day.
Since at least 5 years. Not bad for a dead language.

Chris Thomasson

C is dying? Humm... Try to tell that to the LKML! lol. IMHO, C, C++ and Assembly Language are the kings of the systems languages...

I hope that low-level systems languages like C never die out! What the heck would we use to prototype new things in? Yikes!

Serve Laurijssen

I 100% agree on some of the other skills, but I think nearly every programmer encounters C somewhere in his career. Literature, cross platform libraries, unix/linux tools, hobbyists all use C as main language. Yeah, its not smart to know just C and thats it and if you're only willing to take a job where C is used then you could be unemployed for a while :)

Johan Bengtsson

blufox wrote:
> On Jun 17, 12:29 pm, Linny wrote:

> And yes maybe he went to Redmond to figure out that they program their
> OS in .NET and what not which is not *C*.

I actually think there is a lot in windows that is written in C, most of what is executing in the kernel probably. Ok I have not actually checked but I guess... The .NET platform is surely *not* written in .NET either...

Jack klein

I normally do not bother getting involved in this sot of pointless debate, but I have seen the equivalent of this statement several places lately, so what the heck...

Certain people, and certain publications (paper or electronic) have certain audiences. There are a lot of such publications these days aimed at the "IT" audience, and the "Web 2.0" audience.

It might actually be true for these groups that "C is a dead language". At least at the levels they work at, generating AJAX to provide many new security vulnerabilities.

On the other hand, both the clients and servers run on computers whose operating systems are written almost entirely in C. They execute Java and interpret Javascript in virtual machines and interpreters written almost exclusively in C. The entire internet architecture runs on
switched and routers programmed almost exclusively in C.

Our good friends at ARM claim over 2,000,000,000 ARM cores shipped in 2006, in off-the-shelf microprocessors/microcontrollers and custom ASICs. Virtually every one of them is programmed in C.

So indeed some the authors and readers of some publications may have a world view that doesn't need C anymore. They are way up there in a cloud of trendy and ever-changing tools. The tools they use today (ruby on rails is hot right now), will all be extinct and replaced with some other hot new trends in a few years.

And from there point of view, they might be right. C programming is definitely a dying profession in the "IT" world.

But in the rest of the computer world, C has been, is, and probably will be for quite some time to come, the main language of computing.

There are C implementations, although not all even close to conforming, for everything from the smallest 8-bit microcontrollers to the most advanced 64-bit processors. C applications range from the tiniest embedded system with a few K octets of code space and RAM to the largest operating systems in existence.

The "IT" world gets most of the publicity today, because that's where all the venture capital and publicity are, but that it actually a very small segment of all the computing that's done.

From another, and equally valid, point of view, C programming is essentially all there is, and everything else is down in the noise margin.

Charlton Wilbur

"C, while not very visible to the Web 2.0 market, is still thriving in the embedded space and the operating system development space," while true, does not produce the same kind of ad-viewing traffic.

Chris Hills

Actually they are quite wrong.

Yes, C is dying for PC programming. C++, C# C++/CLI and Java have taken over.

However C++ itself has been superseded by C#, C++/CLI and Java.

C on the other hand is alive and well in a much larger area of programming than desktop. Ie the embedded, real-time and control industries.

*ANYTHING* that has an led, a battery or indeed power "near" it probably has an MCU it in (cars typically have 100 and 3 networks) these systems are by and large programed in C ( some Ada and three people who use Forth)

C is very far from dead outside the PC world but C++ is probably on the way out due to MS moving to it's own languages of C# .Net and C++/CLI which is NOT C++.

stdazi

>
> 6. C programming
> As the Web takes over.......
>

As the web takes over.. With all the applications (apache, mysql, PHP,python) written in C...

CBFalconer

> Actually they are quite wrong.

> Yes, C is dying for PC programming. C++, C# C++/CLI and Java
> have taken over.

> However C++ itself has been superseded by C#, C++/CLI and Java.

Nonsense. You are limiting yourself to the Windoze platform.

Chris Hills

A Lot of the C++ programmers seem to have moved on to the other languages. You are correct that C# and C++/CLI are Windows. However off the desktop C is still the major language.

This is why I think C++ will disappear long before C does. Anywhere there is C++ there are alternatives. However in most of the places where c is used there is no practical alternative.

That said they are using C++ on the JSF

Primary & Extended Partitions

2008-10-13T22:24:00.000-07:00

Deadlock concept

2008-08-31T12:38:00.000-07:00

S-R latch

2008-08-04T02:09:00.000-07:00

sophia

the following is the implementation of S-R latch which i saw in a book,

and the following is the truth table based on it

now in the book it is written that when both s & R are made high simultaneously both the o/p will be low and the value of Q is unpredictable (1 or 0) depending on the circuit condition
now my question is what is this circuit condition that Q depends on ?

bartc

If both outputs are low then Q will also be low, since Q /is/ the value of one of the outputs. Why is that unpredictable?

jean marc bourget

When both S and R are high, Q becomes low as well as Qbar. What is unpredictable is the state of Q when the signals becomes unasserted. It will depend on the precise order in which they are unasserted, the gate delays, the input capacitance, the load on Q and Qbar and probably some other things.

john fields

Assuming that S and R are both high and then go low simultaneously,the gate with the shortest input-to-output delay will force the output of the other gate low.

john popelish

It is not important that they go high simultaneously, only that they *be* high at the same time, since a NOR gate must output a low if either if its inputs is high.So both the S and R force their gates to a low when these signals are high, over riding the cross connections.

> and the value of Q is unpredictable (1 or 0) depending on the
> circuit condition

> now my question is what is this circuit condition that Q depends on ?

It is called a race condition, when both S and R go low at the same time. At that moment, both gates have two low inputs, one from the just transitioned S or R going low, and one from the most recent forced low output from the other gate. That means both gated head toward a high output and
the one that gets there first will force the output of the other back to a low. The circuit conditions involve anything that affects the speed (propagation delay) of each gate, like temperature, transistor gain differences,resistor tolerances, wire lengths, etc.

The more closely matched the two gates are, the longer it takes for the race condition to be resolved into a winner and a loser.

Circuit simulations of such a thing, where both gates and their signals can be mathematically identical to many decimal places, can oscillate for many cycles before the race is decided.

RSA

2008-08-04T01:49:00.000-07:00

Ron Rivest, Adi Shamir, and Leonard Adleman (RSA) were the individuals responsible for creating the RSA standard at MIT, which defines the mathematical properties for using the public-key encryption methodology. The algorithm randomly generates a very large prime number that is used for the public key, which is then consequently used to derive another prime number for the private key via mathematical computations (prime numbers have no pattern). Many forms of RSA encryption are in use today, including the popular PGP.

simple file compression

2008-06-30T10:40:00.000-07:00

sophia

the following is the file compression program ,using elimination of spaces, which I saw in a book

#include
#include

int main(int argc,char * argv[])
{

FILE* fs,*ft;

fs = fopen(argv[1],"r");
if(fs == NULL)
{
printf("\n Cannot open the file %s",argv[1]);
exit(1);
}

ft = fopen(argv[2],"w");
if(fs == NULL)
{
printf("\n Cannot open the file %s",argv[2]);
exit(1);
}

while( (ch=fgetc(fs)) != EOF)
{

if(ch == 32)
{
if( (ch=fgetc(fs)) != EOF)
fputc(ch+127,ft);
}
else
fputc(ch,ft);

}

fclose(fs);
fclose(ft);

return EXIT_SUCCESS;

}

Now my questions are as as follows

1) Is there any other simpler method to compress text files, similar
to the above program(Other than standard algorithms like huffman,LZW)

mstorkamp

sophia wrote:

> if(ch == 32)
> {
> if( (ch=fgetc(fs)) != EOF)
> fputc(ch+127,ft);
> }
> else
> fputc(ch,ft);

What happens when the character represented by the value 32 is the
last character in the file? You are not writing any representation of
that character to your output file. You will not be able to recreate
your source file.

> Now my questions are as as follows

> 1) Is there any other simpler method to compress text files, similar
> to the above program(Other than standard algorithms like huffman,LZW)

yes. Not really a C issue however. First define what you mean by 'text file', then devise a way of mapping the (smaller) domain of your text file into the (larger) domain of an unsigned char. And don't forget to open your destination file for binary access.

walter roberson

sophia wrote:
>the following is the file compression program ,using elimination of
>spaces, which I saw in a book

>#include
>#include

>int main(int argc,char * argv[])
>{

> FILE* fs,*ft;

> fs = fopen(argv[1],"r");
> if(fs == NULL)
> {
> printf("\n Cannot open the file %s",argv[1]);

You are not outputing a \n as the last character. It is implementation defined at to whether the last output line will appear in such a case (and it is also possible that it will appear
but then be immediately overwritten by the next shell prompt, making it seem that it did not appear.)

Error messages are better output to stderr.

> exit(1);

exit(1) does not have a defined effect. The arguments with defined meaning are 0, EXIT_SUCCESS and EXIT_FAILURE

> }

> ft = fopen(argv[2],"w");
> if(fs == NULL)
> {
> printf("\n Cannot open the file %s",argv[2]);
> exit(1);
> }

>while( (ch=fgetc(fs)) != EOF)

You have not declared ch by this point. The exact definition of ch is important to the program. For example, if it were declared as 'char' and 'char' happened to be unsigned on that system, then
it would not be possible for ch to compare equal to EOF, which is always negative.

>{

> if(ch == 32)

What is 32? If you mean a space, code a space, ' ' . The numerical values of particular characters are not specified in C.

> {
> if( (ch=fgetc(fs)) != EOF)
> fputc(ch+127,ft);

As the character set representation is not specified by C, it is possible that ch+127 is a valid character in the character set.

If the file ends in a 32 then that trailing 32 will be lost with your logic.

I note that you do not open the file in binary mode. It could happen that in the input, there were often space characters immediately proceeding end-of-line indicators. The end of line indicators would be read as '\n' and that '\n' would be transformed by your compressor to '\n'+127 which is unlikely to be an end of line indicator. You could thus end up with output lines that exceeded the maximum text output line size supported by the implementation. You could also potentially happen upon characters for which the character + 127 came out as '\n', thus introducing an end of line where there was none before.

> }
> else
> fputc(ch,ft);

>}

> fclose(fs);
> fclose(ft);

> return EXIT_SUCCESS;
>}
>Now my questions are as as follows

>1) Is there any other simpler method to compress text files, similar
>to the above program(Other than standard algorithms like huffman,LZW)

Yes, many of them, most equally inefficient. The code you give at best compresses space followed by a character to a different character code, and leaves everything else alone -- it doesn't even try to compress runs of spaces into something more efficient. If the code were to be applied to typical English text, it would produce a more efficient output if, instead of compressing spaces, it compressed 'e', 't', 'a', 'i', 'o', or 'n', all of which occur in English text with greater frequency than space does.

malcom mclean

squnch compression. It's a sliding dictionarty method that has seen induistrial use because of its super-fast decompress.

barry schwarz

sophia wrote:

>the following is the file compression program ,using elimination of
>spaces, which I saw in a book

Was it listed as a bad example? Perhaps the book was intended as a satire?

>#include
>#include

>int main(int argc,char * argv[])
>{

> FILE* fs,*ft;

> fs = fopen(argv[1],"r");

How does the program know argv[1] is not NULL or for that matter that
it even exists?

> if(fs == NULL)
> {
> printf("\n Cannot open the file %s",argv[1]);
> exit(1);
> }

> ft = fopen(argv[2],"w");
> if(fs == NULL)
> {
> printf("\n Cannot open the file %s",argv[2]);
> exit(1);
> }

>while( (ch=fgetc(fs)) != EOF)

Where is ch declared?

>{

> if(ch == 32)

32 is not the value of ' ' on my system.

> {
> if( (ch=fgetc(fs)) != EOF)
> fputc(ch+127,ft);

On my system adding 127 to a printable character value will produce a value that won't fit in a char. While this technically isn't overflow since fputc takes an int, it will mess up the output file.

It appears to skip only one space. And it does so without regard to whether the space is "significant".

sophia

Barry Schwarz wrote:

> sophia wrote:

> >the following is the file compression program ,using elimination of
> >spaces, which I saw in a book

> Was it listed as a bad example? Perhaps the book was intended as a
> satire?

i don't know if the book was intended as sattire or not .The book ISBN number is 81-7656-537-7 and this program is given in page no: 55

> >while( (ch=fgetc(fs)) != EOF)

> Where is ch declared?

> >{

> > if(ch == 32)

> 32 is not the value of ' ' on my system.

> > {
> > if( (ch=fgetc(fs)) != EOF)
> > fputc(ch+127,ft);

> On my system adding 127 to a printable character value will produce a
> value that won't fit in a char. While this technically isn't overflow
> since fputc takes an int, it will mess up the output file.

> It appears to skip only one space. And it does so without regard to
> whether the space is "significant".

i think to skip more than one space the following changes can be made(assuming 32 stands for ' ')

while( (ch=fgetc(fs)) != EOF)
{
if(ch == 32)
{
count = 1;
while( (ch=fgetc(fs)) == 32)
count++;
fputc(count+127,ft);
}
fputc(ch,ft);

}

fputc takes signed int or unsigned int ?

santosh

It takes a signed int argument, but converts that to an unsigned char before writing to the stream. If the write fails it returns EOF, otherwise the character it wrote converted to int.

pointer variable Vs reference variables

2008-06-07T10:59:00.000-07:00

sulekha

can anyone explain the differences between pointer variable and reference variables ?

thomas o eilidhe

References don't exist in C, they're a C++ thing. A reference is simply a pointer with the following features:

* You don't have to dereference it, it gets dereferenced automagically
* You can't change what it points to

So the following two are equivalent:

void Func(int* constp) { *p = 5; }

void Func(int &i) { i = 5; }

If you want references in C, then you can play around with macroes:

void Func(int* const p)
{
#define i (*p)

i = 5;
}

malcom mclean

References exist in Java and C++, and are basically syntactic sugar for pointers. They point only to one object, and may never be null. However the variable is passed as an address, ie a pointer.

Eric sosman

Malcolm McLean wrote:

> sulekhasweety wrote

>> can anyone explain the differences between pointer variable and
>> reference variables ?

> References exist in Java and C++, and are basically syntactic sugar for
> pointers. They point only to one object, and may never be null. However
> the variable is passed as an address, ie a pointer.

Dunno about C++, but what you say about Java is wrong on all three points (or at least on two and a half points, allowing some wiggle room in interpreting "they" in the second point):

1) A Java "reference" *is* what C calls a "pointer," not a
pointer hiding behind a sugar-coated facade. (Java gives
the programmer little freedom to manipulate its pointers,
but they're indisputably pointers. Note what's thrown for
misuse of a null reference: NullPointerException.)

2) A Java reference value refers to only one object, just as
a C pointer value refers to only one object. A Java
reference variable, just like a C pointer variable, can
refer to different objects at different times.

3) A Java reference value or variable can be null.

middle of a linked list - interview question

2008-05-21T10:56:00.000-07:00

aarklon

The Question goes like this.. while traversing the Node.. Once it is a middle of the Single Linked List it should notify.. This should happen with out further traversal to the next node.

the solution i got from my friends is as follows:-

may be we can do it using two pointers ( although i m not quite sure whether two pointers r allowed in the question or not)one pointer will be incremented by 1 , while other one will be incremented by 2 , when second one reaches the last node, first one will be in the middle.(though nodes after the middle element are traversed by the second pointer in this solution)

can any one give me a correct solution to this problem..... ???

pete

Not better than what you already thought of.

CBfalconer

You've already got it there. Just put it in a function:

node *midpt(node *root) {
node *p = root;

while (p) {
p = p -> next;
if (p) p= p->next;
root= root -> next;
}
return root;
}

juha nieminen

This question is too vague. What kind of list is it? Is it a singly-linked list or a doubly-linked list? Do you know the amount of elements in the list? Are you supposed to do this on an existing list implementation, or are you allowed to modify the list implementation to allow doing things like this?

james harris

Pointers to linked list nodes are not helpful as the nodes are not necessarily adjacent in memory. And to get the second pointer to the end of the list requires traversing the middle node which is
prohibited in the question.

You need one extra piece of information which is missing from the question. For example, if you know the number of nodes - i.e. the length of the linked list, you can stop when you reach the middle.

pete

It's a classic technique for splitting linked lists.

http://www.mindspring.com/~pfilandr/C/lists_and_files/list_lib.h
http://www.mindspring.com/~pfilandr/C/lists_and_files/list_lib.c

static list_type *split_list(list_type *head)
{
list_type *tail;

tail = head -> next;
while ((tail = tail -> next) != NULL
&& (tail = tail -> next) != NULL)
{
head = head -> next;
}
tail = head -> next;
head -> next = NULL;
return tail;

}

Also for detecting circular linked lists.

james harris

Doesn't this include traversal past the middle node (as part of the tail advancing) which is prohibited in the question? It should be said that the question is missing at least some information so maybe your solution is what they were looking for as the head pointer doesn't
pass the middle.

pete

maybe

tree reconstruction

2008-05-21T10:10:00.000-07:00

sophia

Is it possible to re create a binary tree from given preorder and post order traversals ?

Ben pfaff

I believe that there is an exercise in Knuth vol. 1 on this topic or one closely related. I imagine that it has an answer, too.

antonius twink

Well...

There's an ambiguity as soon as you have a node with no left descendant or no right descendant. For example,

a
/
b

and

a
\
b

both have preorder ab and postorder ba.

Of course, these trees are really the same, for some interpretation of "really the same".

walter roberson

Yes. Look for,
"An optimal parallel algorithm to reconstruct a binary tree from its traversals"
by Stephan Olariu, Michael Overstreet and Zhaofang Wen

You might find a linear version more useful,

http://citeseer.ist.psu.edu/andersson90construction.html

Construction of a Tree from its Traversals in Optimal Time and Space (1990)
Arne Andersson, Svante Carlsson

http://citeseer.ist.psu.edu/166720.html

Constructing a Binary Tree Efficiently from Its Traversals (1998) Erkki Makinen

Loop Unrolling

2008-05-21T10:05:00.000-07:00

It is a compilation technique for Instruction-Level Parallelism.Individual loop iterations tend to have relatively low instruction-level parallelism because they often contain chains of dependent instructions, and because of the limited no: of instructions between the branches.

loop unrolling addresses this limitation by transforming a loop with N iterations into a loop with N/M iterations, where each iteration in the new loop does the work of M iterations of the old loop.This increases the no: of instructions between the branches, giving the compiler and the hardware more oppurtunity to find instruction level parallelism

Ex 1:- Orginal loop

for(i=0;i<100;i++)
{
a[i] = b[i] + c[i];
}

Unrolled loop

for(i=0;i<100;i += 2)
{
a[i] = b[i] + c[i];
a[i+1] = b[i+1] + c[i+1];
}

Ex 2:-
Orginal loop

for(i=0;i<100;i++)
{
a[i] = b[i] + c[i];
}

Unrolled loop

for(i=0;i<100;i+=8)
{
a[i] = b[i] + c[i];
a[i+1] = b[i+1] + c[i+1];
a[i+2] = b[i+2] + c[i+2];
a[i+3] = b[i+3] + c[i+3];
a[i+4] = b[i+4] + c[i+4];
a[i+5] = b[i+5] + c[i+5];
a[i+6] = b[i+6] + c[i+6];
a[i+7] = b[i+7] + c[i+7];
}

A loop is said to have unrolled n times if each iteration of the unrolled loop performs a work of n iterations of the orginal loop

Is node deletion in BST commutative ?

2008-05-13T23:38:00.000-07:00

sophia

is node deletion in BST commutative?,commutative in the sense,deletion of a node x and then y leave the tree same as that ofdeleting y first and then x?

moi

Why would you want to know ?
As long as the resulting trees still represent the right ordering af,they can be _considered_ equal.

(re-)Balancing is another aspect, which may need to be taken care of.Do you consider the trees before and after balancing the same ?

Please first give your definition of "same tree"

richard harter

If by "the tree the same" you mean having the same shape and linkage then the answer depends upon how you implement the deletion. What happens when you delete a node that has both left
and right childre is that the tree is split into two trees that must then be relinked. There are many ways that this can be done.That said, one fairly standard way to do this is to replace the
node by its immediate successor.IIANM replacement by the successor (or predecessor) is commutative in your sense.

moi

Simplest case (delete node X from a tree):
X has no children: we are done.
X has only one non-null child: put the child in X's place
X has two non empty children: choose one of them to take X's place,

insert the other (including subtree, which is already ordered, and guaranteed not to overlap) onto the new X'.

This cheap method will maintain order, but destroys balance.It is up to you to decide if it is "commutative" :-}

Electricity

2008-05-10T11:43:00.000-07:00

Electricity

Mains Electricity - The Three Wires - Do Not Touch.

The UK mains electricity supply has three wires.They are called Live, Neutral and Earth and each wire has its own colour. Live is Brown, Neutral is Blue, Earth is Green and Yellow stripes.

The Live wire is connected directly to the generators of the electricity supply company.NEVER touch this wire, it can kill you!!

The Neutral wire returns the electricity to the generator after it has passed through the appliance, to complete the circuit. NEVER touch this wire!!
In a complete circuit, it carries the same electricity as the Live wire.

The Earth wire usually carries no electricity,it is there as a safety device.
If something in the appliance goes wrong, or it is wired incorrectly,then the Earth wire carries the same electricity as the Live wire.To be completely safe, NEVER touch this wire either!!

Earthing.

If the outer casing (the outside bit) of an appliance is a conductor (made of metal), then it can be made safe by Earthing

The Earth wire usually carries no electricity,it is connected to the metal case on the inside of the appliance.

If something goes wrong inside the appliance and the Live wire touches the metal case,then the Earth wire acts like a Neutral wire and completes the circuit for the electricity.A very large current suddenly flows because the metal case has little resistance. This large current blows the fuse in the plug and disconnects the appliance from the power supply.

C program

2008-05-10T11:08:00.000-07:00

sulekha

can any one give a brief outline of the different stages in the execution of a C program , in terms of compilation, pre-processing,linking etc

pete

No.
A C implementation can do two different things.
It can translate a C program.
It can execute a C program.

Compilation, pre-processing, linking are related to translation.

N869

5.1.1.2 Translation phases

[#1] The precedence among the syntax rules of translation is
specified by the following phases.5)

1. Physical source file multibyte characters are mapped
to the source character set (introducing new-line
characters for end-of-line indicators) if necessary.
Trigraph sequences are replaced by corresponding
single-character internal representations.

2. Each instance of a backslash character (\) immediately
followed by a new-line character is deleted, splicing
physical source lines to form logical source lines.
If, as a result, a character sequence that matches the
syntax of a universal character name is produced, the
behavior is undefined. Only the last backslash on any
physical source line shall be eligible for being part
of such a splice. A source file that is not empty
shall end in a new-line character, which shall not be
immediately preceded by a backslash character before
any such splicing takes place.

3. The source file is decomposed into preprocessing
tokens6) and sequences of white-space characters
(including comments). A source file shall not end in
a partial preprocessing token or in a partial comment.
Each comment is replaced by one space character. New-
line characters are retained. Whether each nonempty
sequence of white-space characters other than new-line
is retained or replaced by one space character is
implementation-defined.

4. Preprocessing directives are executed, macro
invocations are expanded, and _Pragma unary operator
expressions are executed. If a character sequence
that matches the syntax of a universal character name
is produced by token concatenation (6.10.3.3), the
behavior is undefined. A #include preprocessing
directive causes the named header or source file to be
processed from phase 1 through phase 4, recursively.
All preprocessing directives are then deleted.

5. Each source character set member and escape sequence |
in character constants and string literals is
converted to the corresponding member of the execution
character set; if there is no corresponding member, it
is converted to an implementation-defined member.

6. Adjacent string literal tokens are concatenated.

7. White-space characters separating tokens are no longer
significant. Each preprocessing token is converted
into a token. The resulting tokens are syntactically
and semantically analyzed and translated as a
translation unit.

8. All external object and function references are
resolved. Library components are linked to satisfy
external references to functions and objects not
defined in the current translation. All such
translator output is collected into a program image
which contains information needed for execution in its
execution environment.

richard heathfield

There are eight translation phases. They are documented in the C Standard.Briefly, they are:

1) physical source file characters are mapped to the source character set,
and trigraph replacements happen;
2) line splicing happens;
3) source file is decomposed into pp-tokens; comments are removed (replaced
by one space character);
4) preprocessing directives are executed and macro invocations are
expanded;
5) escape sequences are converted into characters;
6) string literal concatenation occurs;
7) pp-tokens are converted to tokens, and translation (compilation, if you
like) occurs;
8) linking.

smarty

1.the file u create in editor is saved as ".c" file
2. this '.s' file is then PREPROCESSED for compilation .
3. the preprocessed file undergoes compilation to generate a
'.asm' (assembly file) or '.s' or '.src' file.
4. this source file is assembled to generate a '.obj' file
5. this .obj file is combined with other '.obj' or '.lib' files to
generate an executable file.

chris H

smarty wrote
>1.the file u create in editor is saved as ".c" file
>2. this '.s' file is then PREPROCESSED for compilation .
>3. the preprocessed file undergoes compilation to generate a
>'.asm' (assembly file) or '.s' or '.src' file.
>4. this source file is assembled to generate a '.obj' file
>5. this .obj file is combined with other '.obj' or '.lib' files to
>generate an executable file.

1 You write text (C source) in to a TEXT editor. Often the editor in an IDE

2 You "Compile" the source.

These days this will give you an object file for linking.Under the hood there are several steps

2.1 The pre-processor does a *textual* replacement of macros and defines. This is why it is often required that macros have ( ) around them when they are defined.

2.2 the now expanded text file is compiled. At one time this could be up to THREE passes and the command "CC file.c" actually fed file.c to a batch file called cc that called the three parts of the compiler.This would turn our assembler code in a text file. You then needed to
assemble the text file to object code.

Modern compilers are "single pass" which means they hide all the messing about and go from the source code text to object files in "one pass" and do not generate assembler code. Thus a separate assembler is not needed. In reality there is usually a pre-proccessor phase and the compiler will generate intermediate files and tables.

These days there is more memory. In the Good old Days you use to have to swap floppy disks for compile, assemble and link phases :-) (and 8inch floppies at that :-))))

3 linking. This links the various program object files and the library
files

linking needs to sort out all the extern function and data calls between modules and the library. It knits the modules together in one object file

In some cases years ago where there is only a single file and no calls to the library the object file from the assembler or compiler could run without linking.

The out put from the linker can be further processed to give S-Rec,Intel Hex or other files for downloading to eprom/flash programmers.

The cutting sticks problem

2008-05-10T09:31:00.000-07:00

aarklon

The cutting sticks problem---given a stick of length L and a set of points where it has to be cut. If the cost of making a cut is equal to the length of the stick, what is the best algorithm to find the optimal sequence of cuts(giving minimum cost)

nathaniel calloway

This is not the cutting sticks problem I've heard of before.

Your problem has an intuitive answer: minimize the geometric mean of stick lengths as they are cut. Now you can either just write some code based on that, or you can write some inefficient but sexy tail recursive algorithm that converges on the intuitive answer.

Or you can change the problem to make it sufficiently complex that there are different schemes based on the initial conditions. That's how a CS professor would approach the subject.

greg herlihy

would advise always cutting the stick at whichever point is closest to the middle. After all, if we were able to divide the sticks exactly in half with each cut - we would always have the shortest possible set of sticks for the number of cuts we had made.

And - in order to reduce the cost of each cut - we must reduce the length of our sticks as rapidly as we can with our cuts. Therefore, it makes sense for us to cut each stick at the point closest to its middle - in order for our cuts to come closest to the ideal stick- shortening cutting protocol.

willem

Greg wrote:

) I would advise always cutting the stick at whichever point is closest
) to the middle. After all, if we were able to divide the sticks exactly
) in half with each cut - we would always have the shortest possible set
) of sticks for the number of cuts we had made.
)
) And - in order to reduce the cost of each cut - we must reduce the
) length of our sticks as rapidly as we can with our cuts. Therefore, it
) makes sense for us to cut each stick at the point closest to its
) middle - in order for our cuts to come closest to the ideal stick-
) shortening cutting protocol.

Counterexample:

Assuming a stick of unit length.
Suppose the three cuts have to be placed at 0.45, 0.50 and 0.55.

As per your algorithm, the first cut is at the center (0.50).If we cut first at 0.50 and then at 0.45 and 0.55, the total cost would be 1 + 0.50 + 0.50 = 2

However, if we first cut 0.45, then 0.55 and finally 0.50, the total cost would be 1 + 0.55 + 0.10 = 1.65

greg herlihy

Then there probably is no practical algorithm to find the optimal solution (or at least none has ever been discovered). Instead, a program would have to try every possible combination of cuts to find out which is the cheapest (of course such an exhaustive search would quickly become prohibitively slow as the number of cuts grew).

Essentially, this problem appears to be the "knapsack" problem (given a knapsack containing sticks of different lengths - find the combination of sticks that add up to a particular length) in disguise.

B-tree

2008-05-09T11:38:00.000-07:00

allan teo

Can someone tell me what does b-trees stand for?
Balanced trees? Or is it just simply b-trees (without any meaning)?

ken pizzini

*NO!* B-trees are not at all binary trees! B-trees are balanced multiway trees designed for external (read: disk) storage of data with efficient data access operations. Binary trees are two-way trees designed for effecient internal (read: RAM) access. Beyond the fact that they both start with a B and are both instances of tree structures they are completely different.

lawrence kirby

If it has any meaning I believe it would be "balanced". However it really just refers to a specific datastructure

kai zimmerman

B-tree's are not binary trees and most times not balanced. They are efficient for indexing large amounts of data on slower storage medias. They try to reduce the access time to these medias.

chris bitmead

B=Balanced. The reason is that the algorithm forces the tree to have uniform depth at all times.

Gareth McCaughan

Also, saying "it's a balanced tree" may mislead some people;note that it's not a balanced *binary* tree, but a balanced tree with rather more branching than that.

Andrew hamilton wright

In the excellent article I have "The Ubiquitous B-Tree" (Douglas Comer, Purdue University) from the ACM "Computing Surveys", vol 11, No. 2, 1979, when referring to the original Bayer/MacCreight article he states:

The origin of "B-tree" has never been explained by the authors. As we shall see, "balanced", "broad" or "bushy" might apply. Others suggest that the "B" stands for Boeing (where Bayer worked, parenthesis mine).Because of his contributions, however, it seems appropriate to think of B-trees as "Bayer"-trees.

Hans amund rosbach

Knuth writes about the B-tree in his "The art of computer programming" in chapter 6.2.4 Multiway trees. He gives the original source [Acta Informatica (1972), 173-189], but does not give any explanation for the name.

I'll give his description of it though:

A B-tree of order m is a tree which satisfies the following properties:

1. Every node has <= m sons.
2. Every node, except for the root and the leaves, has >= m/2 sons.
3. The root has at least 2 sons (unless it is a leaf).
4. All leaves appear on the same level.
5. A nonleaf node with k sons contains k-1 keys.

no: of nodes in each level of binary tree

2008-05-07T13:25:00.000-07:00

sophia

How good is this function which is used to find the no: of nodes
in each level of the binary tree. ?

int arrlev[100];

void preorder(struct btree *n,int lev)
{
if(!(n))
return;

arrlev[lev]++;
lev++;

preorder(n->left,lev);
preorder(n->right,lev);
}

walter roberson

sophia wrote:
>How good is this function which is used to find the no: of nodes
>in each level of the binary tree. ?
>int arrlev[100];
>void preorder(struct btree *n,int lev)
>{
> if(!(n))
> return;

> arrlev[lev]++;

When you restrict the number of levels in the counters (which you do in your declaration of arrlev), then before you write into arrlev[lev] you need to check that you are not overflowing the end of the array.

> lev++;
> preorder(n->left,lev);
> preorder(n->right,lev);

You could avoid a bunch of do-nothing calls:

if (n->left) preorder(n->left,lev);
if (n->right) preorder(n->right,lev);
>}

Eric sosman

"How good" is a slippery question, because there are many criteria of goodness, some of them in conflict. So I'll offer observations, not judgements.

1) It will fail badly on a tree with more than a hundred levels. Do such trees really exist? Try this: write a program to build a binary search tree from an input stream of words, then feed it a list of ten thousand words -- in alphabetical order.

2) Even if arrlev[] is made larger, the function is likely to fail on very tall trees (or degenerate trees, as above). Remember, each function invocation needs to "remember" where it was called from so it can return there. The amount of space
set aside for this bookkeeping is often rather limited, and if the recursive calls go too deep they may exhaust it.

3) You might gain some speed by handling the left branch (say) in a loop while making recursive calls only for the right branches.

4) You might gain still more speed by using recursion only when you encounter a node where both the left and right branches are non-NULL. This also offers some defense against degeneracy.

5) Adding `const' to the first argument might be nice.

6)Adding some commentary about what the function does and how to use it might be even nicer.

7)Passing a pointer to the totals array instead of using the global variable
arrlev[] might be nice.

example program

2008-05-07T12:39:00.000-07:00

aarklon

can any one give a example program where recursive version is faster
than iterative version ?

rahul

Recursive programs can be faster than the iterative versions when the only changes you have introduced in the iterative version is saving and restoring states. The system is of course faster in performing push and pop as it simply means issuing 1 or 2 machine instructions.In case of factorials, the stack frame is completely unnecessary. So the iterative version is magnitudes faster than the recursive one.

Towers of Hanoi is faster in recursive version than the iterative one.I am not sure about the quick sort. I will have to profile it but surely the recursive version is more clear than the iterative one.

bartc

aarklon wrote:

> can any one give a example program where recursive version is faster
> than iterative version ?

For trivial programs there may or may not be examples where recursion is faster.

But recursion is a natural fit for many kinds of programming which would be a pain to implement with iterative methods.

Especially with making arrangements to save/restore complex data which may well end up slower than just using recursion. But even if recursion was slower, the difference would be minimal in a real application, while keeping the code much cleaner.

richard heathfield

Bartc said:

> aarklon wrote:

>> can any one give a example program where recursive version is faster
>> than iterative version ?

> For trivial programs there may or may not be examples where recursion is
> faster.

There is, however, no shortage of examples where recursion is /slower/.

> But recursion is a natural fit for many kinds of programming which would
> be a pain to implement with iterative methods.

Right. We don't recurse for speed, but for clarity (where it /is/ clearer) - and even then only if the cost in terms of speed loss is more than adequately compensated by the gain in clarity.

To take a famous example, the following code:

unsigned long factorial(unsigned long n)
{
return n < 2 ? 1 : (n * factorial(n - 1));
}

is horribly inefficient compared to its iterative version (and more so,compared to the Stirling Approximation). In a production environment, it would be inappropriate. But in a teaching environment, it might well be considered a reasonable way to /illustrate/ recursion, given suitable "don't do factorials this way in Real Life" caveats.

barry schwarz

aarklon wrote
>can any one give a example program where recursive version is faster
>than iterative version ?

Primary concern: You need two versions of the program. How do you confirm they are truly equivalent and that each is really coded for highest efficiency?

Secondary concerns: On which hardware? Using which operating system? Using which compiler? With what options? Which measure of speed, CPU time or wall clock?

Are you getting the hint that there is no general answer?

pete

Iterative mergesorts that I've seen for arrays,tend to split less evenly than the recursive versions do. When I race array sorting functions,I can't get any speed from the iterative mergesorts. I still haven't figured out how to mergesort a linked list iteratively.

vamsi krishna ak

Try doing a BFS (Breadth First Search) or DFS of a dense graph recursively and iteratively (using lists) you will see a lot of difference.

paul hseih

aarklon wrote
> Can any one give a example program where recursive version is faster
> than iterative version ?

I can think of two:

1) Return the ith term of a fibonacci.

No, seriously. Its a matter of *WHICH* recursive formula you use.There is a quadratic formula for {fib(n+1),fib(n)} in terms of {fib(floor(n/2)+1),fib(floor(n/2))} which means that you can calculate fib(n) in O(log(n)) steps (using recursion) instead of O(n) steps as is usually the case with the typical iterative solution. For very large n in big integer systems this is, in fact, that fastest algorithm I know of for calculating fib(n). Anywhere where the direct exponential formula can be used (when n is relatively small), tables can also be used and are tremendously faster.

2) a challenge was recently posted
there which asked how to output the nodes of a binary search tree in order without using any recursion or a growable stack/array. My solution which did not modify the tree (imagine that the tree was a mapping of URLs or was in ROM or through a file system with no write permissions) took O(n*log(n)) time, and AFAIK, was not improved upon. However, the recursive solution takes O(n) time.

chris thomasson

IMVHO, it's not really a matter of whether recursion is faster than iteration, but which one is "safer" in practice... Recursion has a side-effect of blowing the stack on some platforms when the depth exceeds the stack size of the calling thread. This does not happen for iteration; here is an example:

I personally find that using recursion to traverse trees can be somewhat dangerous because certain trees can potentially blow the stack. To get around recursion, I tend to use an auxiliary node, and use that as a link into a traversal queue. Something like:

_______________________________________________________________
struct tnode {
struct tnode* left;
struct tnode* right;
struct tnode* next;

};

/* Tree Iteration Support */
struct tnode_iterq {
struct tnode* head;
struct tnode* tail;

};

void tnode_iterq_push(
tnode_iterq* const _this,
tnode* const node
) {
if (node) {
node->next = NULL;
if (! _this->head) {
_this->head = node;
} else {
_this->tail->next = node;
}
_this->tail = node;
}

}

tnode* tnode_iterq_pop(
tnode_iterq* const _this
) {
tnode* const node = _this->head;
if (node) {
if (! (_this->head = node->next)) {
_this->tail = NULL;
}
}
return node;

}

/* Tree Iterator */
void* tnode_iterate(
tnode* const _this,
void (*fp_iterate) (tnode*, void*),
void* const state
) {
unsigned count = 0;
tnode* node = _this;
tnode_iterq iterq = { NULL };
do {
tnode_iterq_push(&iterq, node->left);
tnode_iterq_push(&iterq, node->right);
fp_iterate(node, state);
++count;
} while (! (node = tnode_iterq_pop(&iterq)));
return state;
}

_______________________________________________________________

Now there is no chance of blowing the stack because all recursion is eluded...

chriss thomasson

paul hseih wrote

a challenge was recently posted
> there which asked how to output the nodes of a binary search tree in
> order without using any recursion or a growable stack/array. My
> solution which did not modify the tree (imagine that the tree was a
> mapping of URLs or was in ROM or through a file system with no write
> permissions) took O(n*log(n)) time, and AFAIK, was not improved upon.
> However, the recursive solution takes O(n) time.

Did your solution use something similar my technique:

I basically add an auxiliary pointer per-node and use that as a link in a traversal queue. I believe that is easier than explicitly threading the tree.

paul hseih

No, mine did not augment or write to the tree at all. It uses O(1) space:

http://www.azillionmonkeys.com/qed/treeO1.c

In any event, the recursive solution is *faster* than this which is what the OP was looking for. I just happen to be able to demonstrate that "this" even existed.

rahul

So basically if we try simply to convert a recursive solution to iterative by manually creating a stack frame and simulating function calls, the resulting code is both ugly and slow. But if obvious optimizations can be done for the stack frame, and in some cases it is even completely eliminated ( factorial ), then the iterative code is more efficient. As per my understanding, there are various algorithms in which recursive solutions are faster - towers of hanoi, BFS, DFS to name a few.

The recursive solution for X is faster than iterative does not necessarily mean it is faster. It may mean that an optimized iterative algorithm is yet to be written. A bit off the topic, but many a times tail recursion (where applicable) significantly increases the execution speed. I think the choice between recursive and iterative approach is highly situation dependent and there is no right answer.

Decision Tree

2008-05-07T11:18:00.000-07:00

Look for SOAP implementation for C (not C++)

2008-05-05T21:57:00.001-07:00

swen

Could anyone point me to a SOAP implementation for C? What I would like to do is call out to Web Services from C, and may be later also the reverse- expose C functions as a Web Service...At the moment we are using GNU C on a UNIX system.

christopher browne

gSOAP is the one that is being maintained at present... It speaks both C and C++.

let name="aa454" and tld="freenet.carleton.ca" in name ^ "@" ^ tld;;

http://cbbrowne.com/info/soap.html

"...you might as well skip the Xmas celebration completely, and instead sit in front of your linux computer playing with the all-new-and-improved linux kernel version." -- Linus Torvalds

web services with c

2008-05-05T21:45:00.000-07:00

h

Is it possible to consume web services with c? If not, what other languages would be needed to accomplish this?

richard hethfield

Sure, given an appropriate library.

pawel lesik

yes it is possible for example with gSOAP

h
what about http://www.sqldata.com/

flash gordon

I can definitely say that gSOAP is not always the answer, and C is not always the best language.

michael wojcik

Yes, if by "consume" you mean either "invoke" or "provide". Both are possible in C. They may even be possible entirely in portable C,given a sufficiently flexible definition of "web services" or a sufficiently generous implementation.

For most applications, however, you would have to use facilities outside the C standard (which is what we discuss here), such as an API for network communications.

I suggest that rather than reinventing the wheel, you look for a C web services client or server implementation that suits your needs,or at least for libraries that provide facilities such as HTTP and XML parsing

michael wojcik

Flash Gordon writes:

> The C language has absolutely no abilities for
> the most fundamental things required for a web service, such as
> communications over a network.

This is arguably true (there's a possible quibble over "fundamental" and "required"), but not necessarily relevant. While network communication is "fundamental" to web services, that does not mean that a provider or consumer of web services need be responsible for network communications.

Consider, for example, a portable C program running in an environment where stdin and stdout are the required network communications channel. Such environments are actually very common: inetd and its analogues, CGI programs, and so forth. (There are client-side examples as well.)

It might not be practical, for most applications, to provide or consume web services entirely in portable C, in an environment where this is possible; but I'd like to avoid the false generalization that any task (such as using web services) which is associated with some
facility outside the C standard therefore cannot be done in portable C. Even here we must entertain various unguaranteed expectations about the execution environment, QoI, and so forth.

I'm of the opinion that the original question itself was marginally topical (if considered as "can this be done in standard C?"), but answers other than redirections to implementation-specific groups or those that describe what standard C does not provide (eg network communications, XML parsing, etc) would be off-topic. h's claim of topicality for the larger question ("how can this be done in C?") on the grounds that all C programs are topical is spurious, of course, for the reasons you outline and we're all familiar with, but it's legitimate (again, IMO) for someone to ask here whether some task *can* be accomplished in standard C. And in that event I for one would prefer to see responses that are a bit more cautious in delimiting what is and is not covered by the standard language.

An ideal response, in my opinion, might be along the lines of "it is possible, in some environments, to consume web services in a portable C program, which is what we discuss here; but in practice you are likely to want to use implementation- and environment-specific
features and facilities, and you should ask about those in a news-group relevant to your platform".

keith thompson

The manner in which the network communications channel is associated with stdin and stdout is implementation-specific and non-portable -but of course the manner in which *anything* is associated with stdin and stdout is implementation-specific and non-portable.

keith thompson

To be perhaps a bit clearer:

Standard C has absolutely no support for networking. That doesn't mean it's impossible to write networking code in C (obviously a great deal of networking code is written in C); it just means it's impossible to write networking code in C without using system-specific extensions.

If you can arrange for the environment in which your program runs to associate any necessary network communications channels with your program's stdin and/or stdout, you may be able to write your program in 100% standard C, perhaps even strictly conforming C. But it's not clear that it would be worth the effort. You're going to have to do *some* system-specific work regardless; keeping the system dependencies entirely out of your C program may or may not make sense.

It should be possible to write networking code that's not 100% portable C, but that's probably as portable as you need it to be.The POSIX standard, though it's off-topic here, provides facilities for networking and a number of other operating system interfaces.If your code is expected to run only on POSIX-compliant systems, you can use the POSIX-defined interfaces and your program will still be "portable enough".

ISBN 0-07-044759-4

2008-04-27T00:24:00.000-07:00

I was going through the book "Test your skills in C" by Thamarai selvi and R murugesan, publisheb by Tata Mcgraw-Hill,ISBN 0-07-044759-4 , the following are from this book, now my question is to what extent the following are true..???

1) a function with no action is allowed and is known as dummy function

2) (int(*(*)[3])(char*))ptr is the correct way to cast ptr to a pointer to a 3 element array of function pointers with a return value of int and a single parameter of a pointer to char

3)how could stderr be re directed from within a program to force all error messages to be written to the end of the text file "error.log" instead of location specified by the operating system

a) stderr = fopen("error.log","w");
b) freopen("error.log","a",stderr);
c) stderr = freopen(stderr,"a","error.log");
d) stderr = fopen("error.log","a");

the answer is given as d option

4) #include < stdlib.h >
#include < stdio.h >
char *format="%d";
void func();

int main(void)
{
int x;
func(scanf,&x);
printf("%d\n",x);

return EXIT_SUCCESS;
}

referring to the sample code given above, which of the following would be correct implementation for func ?

a) void func( int (*y)(const char*,...),int* x)
{ (*y)(format,x); }

b) void func( int (*y)(const char*,...),int* x)
{ (*y)(format,&x); }

answer is given as a option

a function with no action is allowed and is known as dummy function

santosh

True. Sometimes they are also called as stub functions.

flash gordon

It is true that it is allowed. It is also true that such functions are often known (by me at least) as dummy functions. However, whether they
are called dummy functions is nothing to do with C.

Malcom mclean

You mean the standard doesn't define anything known as the "dummy" function.
However it is implicit in that

void dummy(void)
{ }

is allowed by C rules of grammar. It wasn't a necessary decision to allow functions with no code in the body at all.

Dummy functions differ from stub functions. A dummy function does nothing, a stub function returns valid but trival data. For instance if you wanted to read a bar code, but had no barcode reader, you might write a stub function

int readbarcode(char *code)
{
strcpy(code, "123456789012345");
return 0;

}

as a placeholder until the real reader arrives.Both are perfectly valid C programming concepts.

(int(*(*)[3])(char*))ptr is the correct way to cast ptr to a pointer to a 3 element array of function pointers with a return value of int and a single parameter of a pointer to char

Flash gordon

I can't think of a good reason for doing such a thing. If there ever was a good reason I would not do it like that (and would reject anything like that in a code review) since it can be made far clearer by using a typedef for the function type (or function pointer type if you prefer).

how could stderr be re directed from within a program to force all error messages to be written to the end of the text file "error.log" instead of location specified by the operating system

a) stderr = fopen("error.log","w");
b) freopen("error.log","a",stderr);
c) stderr = freopen(stderr,"a","error.log");
d) stderr = fopen("error.log","a");

santosh

Wrong. The correct option is (b). The pre-defined streams need not be lvalues.

flash gordon

stderr need not be a modifiable lvalue. I.e. you may not be able to do the assignment in d. According to the standard the primary use of freopen is to change the file associated with stdin/out/err for this very reason! So that leave b as the only possibility, so if the book really does say d it is wrong.

#include < stdlib.h >
#include < stdio.h >
char *format="%d";

void func();

int main(void)
{
int x;
func(scanf,&x);
printf("%d\n",x);

return EXIT_SUCCESS;
}

referring to the sample code given above, which of the following
would be correct implementation
for func ?

a) void func( int (*y)(const char*,...),int* x)
{ (*y)(format,x); }

b) void func( int (*y)(const char*,...),int* x)
{ (*y)(format,&x); }

answer is given as a option

santosh

Yes. That's right. Note though that the call could as well have been:

y(format, x); or (****y)(format, x);

flash gordon

Of the two, a is the only possible valid answer (the correct answer depends on the version of the C standard in use). However, I don't like the code anyway :-)

printf("%d",*(&ptr2 + 2))

2008-04-25T06:01:00.000-07:00

sophia

why in the following program
#include < stdio.h >
#include < stdlib.h >

int main(void)
{
int x[] = {99,2,3,4,5};
int *ptr,**ptr2;

ptr = x;
ptr2 = &ptr;
printf("%d",*(&ptr2 + 2));

return EXIT_SUCCESS;
}

printf("%d",*(&ptr2 + 2)); is printing the first element of the array x ? can anybody explain ?

Ian collins

Where do people find these contrived examples?

The answer is luck.I just happens that's the way the variables are laid out in memory.Try building 64 bit and see what you get then.

sophia

There is something more than luck, that is my conclusion.

I tried changing the value of x[0] to different values but still it will print the o/p correctly.

Has it any thing to do with the compiler ?
I checked this program on lcc-win32 compiler

santosh

What it prints is purely by chance.
Did your compiler not produce a warning?

What is the type of &ptr2? It's int ***. What is the type of (&ptr2 +2). Again the same. Then what's the type of *(&ptr2 + 2)? It's int **.What type does %d expect. It expects an int.

What you want is:printf("%d\n", **ptr2);

santosh

> There is something more than luck, that is my conclusion.

Your conclusion is wrong. What it prints is purely by chance, since there is a type discrepancy between what printf expects and what it gets.

> I tried changing the value of x[0] to different values but still
> it will print the o/p correctly.

That's irrelevant.

> Has it any thing to do with the compiler ?

Certainly your output, because your program invokes undefined behaviour,is likely to be specific to your implementation or even specific to each run of the program

Ian collins

> There is something more than luck, that is my conclusion.
> I tried changing the value of x[0] to different values but still
> it will print the o/p correctly.

The luck is in the memory layout, not the values. The address of &ptr2 + 2 just happens to be the address of x[0].

> Has it any thing to do with the compiler ?

Everything, memory layout is compiler and platform specific, although most 32 bit compilers on x86 probably use the same layout.

> I don't have a 64 bit compiler
Every home should have one :)

santosh
the question is broken and the program is undefined according to the language standard. Even if it were to be assumed that the array 'x' starts 2 * sizeof &ptr2 bytes after &ptr2, the program is still broken because the printf call is incorrect.

#define vs typedef

2008-04-25T05:52:00.000-07:00

The right way to think about typedef as being a complete encapsulated type - you can't add to it after you have declared it.

ex:-

#define peach int
unsigned peach i; /*works fine*/

typedef int banana ;
unsigned banana i; /*illegal*/

a typedef'd name provides the type for every declarator in a declaration

Ex:-

#define int_ptr int*
int_ptr chalk, cheese;

after macro expansion, the second line effectively becomes
int* chalk,cheese;

In contrast a typedef like this:

typedef char* char_ptr;
char_ptr bentley,rolls_royce;

declares both bentley and rolls_royce to be the same . the name on the front is different, but they are both a pointer to a char.

simple AVL tree program

2008-04-22T20:38:00.000-07:00

/*Program for insertion in AVL tree*/

#include < stdio.h >
#include < stdlib.h >

#define FALSE 0
#define TRUE 1

typedef struct node
{
int val;
int balfact;

struct node* left;
struct node* right;

}node;

node* buildtree(node*,int,int*);
node* allocate(int);
void display(node*);
void deltree(node*);

int main(void)
{
node* avl = NULL;
int h;

avl = buildtree(avl,20,&h);
avl = buildtree(avl,6,&h);
avl = buildtree(avl,5,&h);
avl = buildtree(avl,29,&h);
avl = buildtree(avl,12,&h);
avl = buildtree(avl,25,&h);

printf("\n AVL TREE\n");
display(avl);

printf("\n checking root value %d", avl-> val);
printf("\n checking root balance value %d", avl-> balfact);

deltree(avl);

return EXIT_SUCCESS;
}

node* buildtree(node* root,int data,int *h)
{
node* n1,*n2;

if(!root)
{
root = allocate(data);
*h = TRUE;
return root;
}

if(data < root -> val)
{
root -> left = buildtree(root -> left,data,h);
/*if left sub tree is higher*/

if(*h)
{
switch(root -> balfact)
{

case -1:
root -> balfact = 0;
*h = FALSE;
break;

case 0:
root -> balfact = 1;
break;

case 1:

n1 = root -> left;

if(n1-> balfact == 1)
{
printf("\n Right rotation along %d", root -> val);
root -> left = n1 -> right;
n1 -> right = root;
root -> balfact = 0;
root = n1;
}
else
{
printf("\n Double rotation ...left along %d",n1-> val);
n2 = n1 -> right;
n1 -> right = n2 -> left;
n2 -> left = n1;
root -> left = n2 -> right;
n2 -> right = root;

if(n2 -> balfact == 1)
root -> balfact = -1;

else
root -> balfact = 0;

if(n2 -> balfact == -1)
n1 -> balfact = 1;
else
n1-> balfact = 0;

root = n2;
}

root -> balfact = 0;
*h = FALSE;
break;
}
}

}

if(data > root -> val)
{
/*if the right sub tree is higher*/
root -> right = buildtree(root -> right,data,h);

if(*h)
{

switch(root -> balfact)
{
case 0:
root -> balfact = -1;
break;

case 1:
root -> balfact = 0;
*h = FALSE;
break;
case -1:

n1 = root -> right;

if(n1 -> balfact == -1)
{
printf("\n Left rotation along %d",root -> val);
root -> right = n1 -> left;
n1 -> left = root;
root-> balfact = 0;
root = n1;
}
else
{

printf("Double rotation right along %d ", n1-> val);
n2 = n1 -> left;
n1 -> left = n2 -> right;
n2 -> right = n1;
root -> right = n2 -> left;
n2 -> left = root;

if(n2 -> balfact == -1)
root -> balfact = 1;
else
root -> balfact = 0;

if(n2 -> balfact == 1)
n1 -> balfact == -1;
else
n1 -> balfact = 0;

root = n2;
}

root ->balfact=0;
*h = FALSE;
}

}

}

return root;

}

void display(node* root)
{
if(root)
{
display(root -> left);
printf("\t %d",root -> val);
display(root -> right);
}
}

void deltree(node* root)
{
if(root)
{
deltree(root -> left);
deltree(root -> right);
}

free(root);
}

node* allocate(int val)
{
node *temp;

temp = malloc(sizeof(*temp));

if(!temp)
{
printf("\nMemory allocation failed\ngoing to exit");
exit(1);
}

temp -> val = val;
temp -> left = NULL;
temp -> right = NULL;
temp -> balfact = 0;

return temp;
}

memset o/p not correct

2008-04-20T07:36:00.000-07:00

aarklon

The following is actually a part of the pattern matching program which I tried ,memset is not setting the entire integer array with -1

#include < string.h >
#include < stdio.h >
#include < stdlib.h >

int main(void)
{
int maxpat[80],i;
memset(maxpat,-1,80);

for(i=0;i<80;i++)
printf("%d\t",maxpat[i]);

return EXIT_SUCCESS;
}

but i am getting o/p as

-1 -1 -1 -1 -1 -1 -1 -1
-1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1
-370086 -370086 -370086 -370086 -370086 -370086 -370086 -370086
-370086 -370086
-370086 -370086 -370086 -370086 -370086 -370086 -370086 -370086
-370086 -370086
-370086 -370086 -370086 -370086 -370086 -370086 -370086 -370086
-370086 -370086
-370086 -370086 -370086 -370086 -370086 -370086 -370086 -370086
-370086 -370086
-370086 -370086 -370086 -370086 -370086 -370086 -370086 -370086
-370086 -370086
-370086 -370086 -370086 -370086 -370086 -370086 -370086 -370086
-370086 -370086

"D:\siju\lcc6\noisedisp.exe"
Return code 0
Execution time 0.048 seconds
Press any key to continue...

why is this so..????

Ian collins

You are only setting the first 80 bytes of the the array, not 80 ints.

Bartc

You're setting 80 bytes. The array is bigger than that (80*sizeof(int)).
Try: memset(maxpat,-1,sizeof maxpat);

Flash gordon

Check the definition of memset in your reference book, it sets a specified number of *bytes*. This also means that having corrected the error (sizeof *maxpat is your friend) it won't be portable to implementations using 1s complement or sign-magnitude if you can find such an implementation.

Richard tobin

Unless you really on the machines being 2s-complement, which is true of all general-purpose computers today.

CBFalconer

What's the point of the foolishness, when:

#define MPSIZE 80
#define VALUE -1
int maxpat[MPSIZE], i;

for (i = 0; i < MPSIZE; i++) maxpat[i] = VALUE;

handles it accurately and portably, doesn't care about what VALUE is, and preserves the value of MPSIZE for any other uses. Note that the bit of code above doesn't have to be in the scope of maxpat, rather it can receive it as a parameter.

pattern matching

2008-04-19T14:35:00.000-07:00

/*program to find the maximum matching pattern in the string*/

#include < string.h >
#include < stdio.h >
#include < stdlib.h >

void findmaxpat(char*,char*,int*);
void printmaxpat(char*,int*);

int main(void)
{

int i;

char s[80];
char pat[80];
int maxpat[80];

memset(maxpat,-1,80);

printf("\n Enter the main string:: ");
gets(s);

while(*s)
{
printf("\n Enter the pattern to be searched:: ");
gets(pat);

findmaxpat(s,pat,maxpat);
printmaxpat(s,maxpat);

printf("\n Enter the main string:: ");
gets(s);
}

return EXIT_SUCCESS;
}

void findmaxpat(char* s,char* pat,int* maxpat)
{

int i;

for(i=0;*s && *pat;i++,s++)

if(*s == *pat)
*maxpat++ = i,pat++;

if(!*pat)
puts("whole pattern found...");

else
printf("pattern not found in the string ");

*maxpat = -1;

}

void printmaxpat(char* s,int* maxpat)
{

char *temp = s;

(*maxpat == -1)? printf("\"%s\"\n",s) :puts(s);

for(;*temp && *maxpat != -1;++temp)
{

if(temp-s == *maxpat)
{
printf("^");
maxpat++;
}
else
printf("%c",' ');
}

puts("");
}

Pseudo-code for array implementation of circular queue

2008-04-19T10:14:00.000-07:00

why this does n't works

2008-04-19T10:08:00.000-07:00

aarklon

#include< stdio.h >
#include< stdlib.h >
#include< string.h >

int main(void)
{
char *t[5]; /*= {"BASIC"};*/

strcpy(t[0],"BASIC");
printf("....%s",t[0]);

return EXIT_SUCCESS;
}
/* i am getting segmentation violation in lcc compiler*/

is not working whereas

int main(void)
{
char *t[5] = {"BASIC"};

/*strcpy(t[0],"BASIC");*/
printf("....%s",t[0]);

return EXIT_SUCCESS;
}

is working ?

Does this mean that while using strcpy the char pointer should
always be initialized ...?????

pereges

i guess the problem arises because you have not allocated any memory for the string. Probably you can try this because it seems to work for me:

#include < stdio.h >
#include < stdlib.h >
#include < string.h >

int main(void)
{
char *t[5]; /*= {"BASIC"};*/
int i;
i = strlen("BASIC");
t[0] = malloc(i * sizeof(char));
strcpy(t[0],"BASIC");
printf("....%s",t[0]);

return EXIT_SUCCESS;
}

Richard heathfield

this call attempts to copy SIX bytes, but you only reserved five (assuming the malloc worked, which you didn't check) - so you've written into memory you don't own, and the behaviour of your program is now undefined.

kenneth brody

Isn't this second version perfectly well-defined? Doesn't the line:

char *t[5] = {"BASIC"};

mean: t is an array of 5 character pointers, the first one points to the literal "BASIC", and the rest are NULL and so the reference to t[0] means the string "BASIC"?

Barry schwarz

Yes
>and so the reference to t[0] means the string "BASIC"?

Yes but it might be better phrased as'"the string literal "BASIC"'.

It is only well defined as long as there is no attempt to update the characters pointed to by t[0]. Any attempt to do so (as implied by the commented call to strcpy) invokes undefined behavior.

memory management using list

2008-04-19T00:24:00.000-07:00

/*design a storage management scheme where all requests for memory are of the same size,say K. Write functions to free and allocate storage in this scheme*/

#include < stdio.h >
#include < stdlib.h >

#define N 90
#define K 10
#define SUCCESS 0
#define ERROR -1

typedef struct node
{
void *ptr;
struct node* next;

}node;

struct head
{
node *next;
char *bytes;

}freelist;

void init();
void memfree(void*);
void *memalloc();
void print();

int main(void)
{

void *p1,*p2,*p3,*p4;

init();
printf("\n after init\n");
print();

p1 = memalloc();
printf("\n after memalloc p1.....\n");
print();

p2 = memalloc();
printf("\n after memalloc p2.....\n");
print();

p3 = memalloc();
printf("\n after memalloc p3.....\n");
print();

p4 = memalloc();
printf("\n after memalloc p4.....\n");
print();

memfree(p4);
printf("\n after memfree p4.....\n");
print();

memfree(p3);
printf("\n after memfree p3.....\n");
print();

memfree(p2);
printf("\n after memfree p2.....\n");
print();

memfree(p1);
printf("\n after memfree p1.....\n");
print();

free(freelist.bytes);
return EXIT_SUCCESS;
}

void init()
{
int i;

freelist.next = NULL;
freelist.bytes = malloc(N);

for(i=N/(K-1);i >=0;i--)
memfree(freelist.bytes + K*i);
}

void memfree(void *p)
{
/*adds p to free list*/

node *temp;

if(!p)
return;

temp = malloc(sizeof(*temp));
temp -> ptr = p;
temp -> next = freelist.next;
freelist.next = temp;
}

void print()
{
node* temp;

puts("");
for(temp = freelist.next;temp;temp = temp -> next)
printf("%u \t",temp -> ptr);

puts("");
}

void* memalloc()
{
void *p;
node *temp;

if(freelist.next == NULL)
return NULL;

temp = freelist.next;
p = temp -> ptr;

freelist.next = freelist.next->next;
free(temp);

return p;
}

pointer normalization

2008-04-16T09:23:00.000-07:00

sophia

can any one explain what is meant by pointer normalization given here:-
http://c-faq.com/ansi/norml.html

Richard heathfield
It is possible for a pointer value to have more than one object representation. If p1 and p2 are two pointers to the same object, but with different object representations, then p1 == p2 is required to yield 1, so the implementation must (behave as if to) supply code to "normalise" the pointer values used in the comparison - i.e. to convert one or the other or both to a common form. (This was perfectly common in MS-DOS days.)

Note that the same requirement (of identifying the equality of those two pointers) is not imposed on memcmp(&p1, &p2, sizeof p1).

sophia

Object in C means region of data storage isn't it ?
i am not getting your point,same object with different representations ?

kenneth brody

Consider, for example, "real mode" on an x86 CPU. On that particular platform, addresses are represented by a 16-bit segment and a 16-bit offset. (The physical address is segment*16+offset.) Using this particular architecture, the following segment/offset pairs all point to the same physical address:

1234:0000
1230:0040
1200:0340
1000:2340
and even
1111:1230
0235:FFF0

Richard heathfield

Consider MS-DOS's 20-bit pointers, where logical addresses are described by
two 16-bit values, called "segment" and "offset" respectively. To get the
physical address, we left-shift the segment value by four bits, and then
add the offset value.

Logical Logical Physical
segment offset address
address address
0001 1030 01040
0002 1020 01040
0003 1010 01040
0004 1000 01040
0005 00F0 01040

etc.

Five different pointer representations, all pointing to the same physical
object. All must compare equal when compared with ==. The implementation
is responsible for making this work.

kenny mccomarck

A nitpick surely worthy of this group...

It's not "MS-DOS's 20-bit pointers".This is a feature of the 8086 processors (and its descendants, running in "real mode"). It is not a function of the OS in any way.

Further note that the descendants still maintain this functionality; it is just that it is rarely used. It is no longer necessary (at least up to the 4G mark. I'm not sure what happens if you have a machine with more than 4G RAM).

kenny mccomarck

And note that a *real* first-class nitpicker would point out that it's not even *MS*-DOS, as if this functionality were someone unique to and/or invented by Microsoft...

nick keighley

sophia wrote
>i am not getting your point,
> same object with different representations ?

not possible on a sane architecture, but see the "Segmentation" section of http://en.wikipedia.org/wiki/Intel_8086

Morris dovey

There are cases where it actually is sane. Consider a uP with 16-bit addressing, but where all of the memory actually available can be accessed using only the low-order 12 bits - this means that, in a "sane" design, the high-order four address bits are
"don't cares", and that for every real location in memory, there are _sixteen_ valid addresses.

linear search Vs Binary search

2008-04-16T04:57:00.000-07:00

In which all situations linear search will be more efficient than binary search ?

jongware

Unsorted data.

Richard Harter

I assume that the data is sorted; if it is not the question is moot. Your question really doesn't have an answer until you specify what is meant by "more efficient". How are you measuring efficiency?

A further issue is that performance is variable,depending on the item being searched.

That said, in terms of wall clock time, linear search will run faster than binary search on average for N < C where N is the data set size and C is an implementation specific constant that depends upon the costs of various operations. A critical factor is whether you can place a sentinel in the data. If you can the value of C approximately doubles. Here are some typical values for C:

C = 12, if sentinels are not permitted
C = 25, if sentinels are permitted.
C = 50, if sentinels are permitted and do one bisection

Incidentally, what you do in a sentinel based search is to place the value you are searching for at the end of the array you are searching. By doing this you eliminate the need to check for having exhausted the array since you are guaranteed to find the item.

String -- Anagrams

2008-04-15T20:25:00.000-07:00

sophia

The following is the program which i have done to find all the
combination of letters in the string "hello"

#include < stdio.h >
#include < stdlib.h >
#include < string.h >

#define MAX 6

int main(void)
{
char t[MAX];
int i,j,k,l,m,n=1;

strcpy(t,"hello");

printf("\n words formed from the combinations of all characters from \
the word hello\n\n");

for(i = 0 ;i < MAX ;i++)
for(j = 0 ;j < MAX ;j++)
{
if(j == i)
continue;

for(k = 0 ;k < MAX ;k++)
{
if( (k==i) || (k == j) )
continue;

for(l = 0 ;l < MAX ;l++)
{

if( (l==i) || (l == j) || (l == k) )
continue;

m = 10 - (i + j + k + l);
printf("%c%c%c%c%c ",t[i],t[j],t[k],t[l],t[m]);

if(n %10 == 0) puts("");
n++;
}

}
}

printf("\n no: of words formed = %d",--n);

puts("");
return EXIT_SUCCESS;
}

can any one suggest a more general method so that i can find the combination of letters of any inputted string ?

Richard

For a start think about moving it all to another "non main" function where you call it with the string you are interested in checking. This "MAX" everywhere is horrible. Instead in your new function

displayAnagrams(char *s){
int len = strlen(s); /* or size_t ...... */
...
...
}

Bartc

The following code (showpermutations()) displays all permutations of the
characters in any string.

But: it does not deal with repeated characters (so perms of aaa would be
aaa,aaa,aaa,aaa,aaa,aaa). And capturing the output is tricky; here it justs
prints the results. And, I suspect there's a much more elegant way to do
this..

I've built-in a maximum word length of 99 characters; however such a word
would print 99! lines of output.

Maybe this helps.

/* Display all permutations of characters in a word. Ignores duplicate chars
*/

#include < stdio.h >
#include < string.h >

void showpermutations(char *prefix, char *word);

#define maxwordlen 100

int main(void) {
showpermutations("","abcd");

}

void showpermutations(char *prefix, char *word) {
char newprefix[maxwordlen];
char newword[maxwordlen];
char c[2]={0,0};
char d[2]={0,0};
int i,j,len;

if (prefix==NULL || word==NULL) return;

len=strlen(word);

if (len<=1) {
printf("%s%s\n",prefix,word);
return;

};

for(i=0; i < len; ++i) {
c[0]=word[i];
newword[0]=0;

for (j=0; j < len; ++j)
if (j!=i) {
d[0]=word[j];
strcat(newword,d);
};

strcpy(newprefix,prefix);
strcat(newprefix,c);
showpermutations(newprefix,newword);

}
}

Willem

To print all permutations of a string, you have to print each of its characters as a first character, and then print all the permutations of the remaining characters.

One way to get 'each of the characters' and 'the remaining characters' is to rotate the string in-place so that each character is put at the front in turn.

Given this, here's a recursive solution:

void rotate(char *ptr, int len)
{
char tmp = *ptr;
memmove(ptr, ptr+1, len-1);
ptr[len-1] = tmp;
}

void recurse_perms(char *str, char *ptr, int len)
{
int i;
if (len) {
for (i = 0; i < len; i++) {
recurse_perms(str, ptr+1, len-1);
rotate(ptr, len);
}
} else {
printf("%s\n", str);
}
}

void print_perms(char *str)
{
/* NB: If str can be const, make a copy here */
recurse_perms(str, str, strlen(str));
}

If you want more performance, you can also use a swap operation instead of a rotate, but then it's a bit harder to figure out exactly what to swap to where.

Note that the recursive function returns the substring at *ptr to its original state. This is needed for the function to work. (And that's why swapping is a lot harder conceptually.)

user923005

This is a modification of an IOCCC entry:

E:\dict>foo.bat hellosophia

E:\dict>anagram -1 hellosophia 0hellosophia

E:\dict>anagram -2 hellosophia 0>hellosophia

E:\dict>anagram -3 hellosophia 0>hellosophia

E:\dict>anagram -4 hellosophia 0>hellosophia
E:\dict>type foo.bat
anagram -1 %1 < big.dict > %1
anagram -2 %1 < big.dict >>%1
anagram -3 %1 < big.dict >>%1
anagram -4 %1 < big.dict >>%1

E:\dict>type anagram.c

#include < stdio.h >
#include < stdlib.h >
#include < io.h >
#include < string.h >

char *getsafe(char *buffer, int count)
{
char *result = buffer,
*np;
if ((buffer == NULL) || (count < 1))
result = NULL;
else if (count == 1)
*result = '\0';
else if ((result = fgets(buffer, count, stdin)) != NULL)
if (np = strchr(buffer, '\n'))
*np = '\0';
return result;

}

static long a[4],
b[4],
c[4],
d[0400],
e = 1;

typedef struct f {
long g,
h,
i[4],
j;
struct f *k;

} f;

extern long n(long *o, long *p, long *q);
extern void t(int i, long *p);
extern int u(struct f * j);
extern int v(struct f * j, int s);
extern int w(struct f * o, int r, struct f * j, int x, long p);
extern int y(void);
extern int main(int o, char **p);

static f g,
*l[4096];

static char h[256],
*m,
k = 3;

long n(long *o, long *p, long *q)
{
long r = 4,
s,
i = 0;
for (; r--; s = i ^ *o ^ *p, i = i & *p | (i | *p) & ~*o++, *q++ =
s, p++);
return i;

}

void t(int i, long *p)
{
*c = d[i], n(a, c, b), n(p, b, p);
}

int u(struct f * j)
{
j->h = (j->g = j->i[0] | j->i[1] | j->i[2] | j->i[3]) & 4095;
return 0;
}

int v(struct f * j, int s)
{
int i;
for (j->k->k && v(j->k, ' '), fseek(stdin, j->j, 0); i =
getchar(), putchar(i - '\n' ? i : s), i - '\n';);
return 0;
}

int w(struct f * o, int r, struct f * j, int x, long p)
{
f q;
int
s,
i = o->h;
q.k = o;
r > i ? j = l[r = i] : r < i && (s = r & ~i) ? (s |= s >> 1, s |=
s >> 2, s |= s >> 4, s |= s >> 8, j = l[r = ((r & i | s) & ~(s >> 1))
- 1 & i]) : 0;
--x;
for (; x && !(p & i); p >>= 1);
for (; !x && j; n(o->i, j->i, q.i), u(&q), q.g || (q.j = j->j,
v(&q, '\n')), j = j->k);
for (; x; j = x ? j->k : 0) {
for (; !j && ((r = (r & i) - 1 & i) - i && (r & p) ? 2 : (x =
0)); j = l[r]);
!x || (j->g & ~o->g) || n(o->i, j->i, q.i) || (u(&q), q.j = j-
>j, q.g ? w(&q, r, j->k, x, p) : v(&q, '\n'));

}
return 0;
}

int y(void)
{
f
j;
char *z,
*p;
for (; m ? j.j = ftell(stdin), 7, (m = getsafe(m, sizeof h)) ||
w(&g, 315 * 13, l[4095], k, 64 * 64) & 0 : 0; n(g.i, j.i, b) ||
(u(&j), j.k = l[j.h], l[j.h] = &j, y())) {
for (z = p = h; *z && (d[*z++] || (p = 0)););
for (z = p ? n(j.i, j.i, j.i) + h : ""; *z; t(*z++, j.i));
}
return 0;
}

int main(int o, char **p)
{
for (; m = *++p;)
for (; *m - '-' ? *m : (k = -atoi(m)) & 0; d[*m] || (d[*m] =
e, e <<= 1), t(*m++, g.i));
u(&g), m = h, y();
return 0;

}

sophia

> E:\dict>type anagram.c
> #include
> #include
> #include

but is a non standard , non ANSI header file is n't it ?

E:\dict>type hellosophia|more

I think this should be rather E:\dict>anagram hellosophia|more

Bartc

It also generates anagrams of course rather than just all the combinations of the letters.It could also have done with small.dict rather than big.dict.

CBFalconer

This generates full anagrams.

#include < stdio.h >
#include < string.h >
#include < stdlib.h >

/* Public domain, by C.B. Falconer. *//* 2003-Aug-21 */
/* Attribution appreciated. */

/* Things can get out of hand when larger than 8 */
#define MAXWORD 17

/* ------------------ */

/* exchange 0th and ith char in wd */
void trade(char *wd, unsigned int i)
{
char c;

c = *wd;
*wd = wd[i];
wd[i] = c;

} /* trade */

/* ------------------ */

/* Form all n char permutations of the characters in the
string wd of length lgh into outstring at index ix.
Output the results to stdout. */
void jumble(char *wd, unsigned int lgh,
unsigned int ix, /* output place to fill */
unsigned int n, /* max out places to fill */
char *outstring)
{
unsigned int i;

if (0 == n) {
outstring[ix] = '\0';
puts(outstring);
}
else
for (i = 0; i < lgh; i++) {
trade(wd, i); /* nop when (0 == i) */
outstring[ix] = *wd;
jumble(wd+1, lgh-1, ix+1, n-1, outstring);
trade(wd, i); /* restore the wd string */
}

} /* jumble */

/* ------------------ */

int main(int argc, char *argv[])
{
unsigned int n, lgh, min;
double max;
char outstring[MAXWORD];

if (argc < 2) {
fprintf(stderr,
"Usage: jumble [lgh]\n"
" where the (optional) lgh specifies the\n"
" maximum length of the output words\n");
return 0;
}
lgh = strlen(argv[1]);
if (lgh >= MAXWORD) argv[1][lgh = MAXWORD-1] = '\0';

min = lgh;
if ((argc > 2) && (1 == sscanf(argv[2], "%u", &n)))
if (n && (n <= lgh)) min = n;

for (n = lgh, max = 1.0; n > (lgh - min); n--)
max = max * n;

fprintf(stderr, "string=\"%s\", max=%.0f, len=%u\n",
argv[1], max, min);

jumble(argv[1], lgh, 0, min, outstring);
return 0;

} /* main */

y >> (8 * (sizeof(int) -1))

2008-04-15T20:14:00.000-07:00

aarklon

Is y >> (8 * (sizeof(int) -1)) portable expression to find The MSB of an unsigned integer y ??
will this work in all the cases, all three of the representations C allows:

1) two's complement 2) ones'complement 3) signed magnitude.

joachim schmitz

Probably better and more portable:
#include
...
y >> (CHAR_BIT * (sizeof y -1))

Harald van Dijk

No, it isn't.

> 1) two's complement
> 2) ones'complement
> 3) signed magnitude.

These differ in how negative values are represented. Why do you think negative values matter, given that you've got an unsigned integer?

Peter Nilsson

Define MSB in the following case...

CHAR_BIT = 8
UINT_MAX = 262143

If you want the top CHAR_BIT bits from an unsigned int y, use...

y / ((UINT_MAX >> (CHAR_BIT - 1) >> 1) + 1)

> will this work in all the cases, all three of the representations C
> allows:

> 1) two's complement
> 2) ones'complement
> 3) signed magnitude.

Unsigned integers use pure binary representation.

Jack klein

> Is y >> (8 * (sizeof(int) -1)) portable expression to find The MSB of
> an unsigned integer y ??

It is absolutely not portable, even if you change 8 to CHAR_BIT.

I do a lot of work on a DSP where sizeof(char), sizeof(short), and sizeof(int) are all 1. CHAR_BIT happens to be 16, of course, and sizeof(long) is 2, sizeof(long long) is 4.
So on this implementation, either of the expressions:

(8 * (1 - 1))

...or:

(16 * (1 - 1))

...will not tell you anything about the MSB.

> will this work in all the cases, all three of the representations C
> allows:

> 1) two's complement
> 2) ones'complement
> 3) signed magnitude.

As others have stated, the representation of the signed int types in a C implementation has nothing to do with the unsigned types.

Try this:

#include < limits.h >

#define UINT_MSB_MASK (UINT_MAX - (UINT_MAX >> 1))

if (some_unsigned_int & UINT_MSB_MASK)
/* do stuff because it is set */
else
/* do stuff because it is not set */

aarklon

harald van dijk wrote

> These differ in how negative values are represented. Why do >you think negative values matter, given that you've got an >unsigned integer?

what about finding the MSB of a signed integer ?

Flash gordon

You cannot find that by shifting since right shifting a negative value gives an implementation defined result and left shifting a 1 in to the MSB invokes undefined behaviour. If you want to know the sign and don't care about negative zero then just use either <0 or >=0 as appropriate

printf("....%d",sizeof((int)(double)(char) i))

2008-04-15T20:08:00.000-07:00

aarklon

why printf("....%d",sizeof((int)(double)(char) i)) always gives the size of int ???
is it because sizeof doesn't evaluate its operand....???

Peter Nilsson

>is it because sizeof doesn't evaluate its operand....???

With the exception of variable length arrays in C99, yes.

The object i doesn't even have to be initialised. Even the following is valid...

sizeof( (int) (int (*)(void)) -1 )

...even though there is no well defined conversion involved at any stage.

Joachim schmitz

It is because your code is just the longer version of printf("....%d",sizeof(int))

Ivar

By doing printf("....%d",sizeof((int)(double)(char) i)), you're finally casting i to an int, so it would print the sizeof(int) value.

nodes in a linked list

2008-04-15T19:59:00.000-07:00

Is there any condition / requirement that nodes in linked list must be stored in contigous memory locations ?

gw7rib

Far from it. Some of the main advantages of a linked list are that you can delete nodes in the middle of a list without having to move anything, add new nodes at the end, add extra nodes in the middle (again without moving anything), and change the order of the nodes without actually moving them. This would not be possible if the nodes had to be stored in contiguous locations.

Node deletion in binary tree

2008-04-15T07:49:00.001-07:00

Complete Binary Tree

2008-04-14T13:16:00.000-07:00

catalan numbers

2008-04-14T06:54:00.000-07:00

Catalan numbers

for n >= 0, the nth catalan number is given as

cat(n) = C(2n,n)/(n+1) => (2n)!/(n+1)!n!

The no: of distinct binary trees with n vertices, n >= 0 , is the nth catalan number cat(n)

see:- http://en.wikipedia.org/wiki/Catalan_numbers

Heap creation

2008-04-14T06:33:00.000-07:00

program which shows the creation of heap from an array of elements

#include < stdio.h >
#include < stdlib.h >
#define MAX 50

void restoreup(int,int*);
void restoredown(int,int*,int);
void makeheap(int*,int);
void add(int,int*,int*);
void display(int*,int);
int readval(void);
int del(int*,int*);

int main(void)
{

int a[MAX] = {1000,7,10,25,17,23};
int n = 5,i;

makeheap(a,n);
display(a,n);

printf("\n\nEnter the element you want to add:: ");
i= readval();
add(i,a,&n);

printf("\nAfter adding the element %d\n",i);
display(a,n);

i = del(a,&n);
printf("\n\nAfter Deletion\n");
display(a,n);

puts("");
return EXIT_SUCCESS;
}

void makeheap(int *a,int n)
{
int i;

for(i= (n/2);i>= 1;i--)
restoredown(i,a,n);
}

void restoredown(int pos,int *a,int n)
{
int i,val;
val = a[pos];

while(pos <= n/2)
{
i = 2 * pos;

if((i < n) && (a[i] < a[i+1]))
i++;

if(val >= a[i])
break;

a[pos] = a[i];
pos = i;
}

a[pos] = val;
}

int readval()
{
int i,ch;

while( (1 != scanf("%d",&i)) )
{
while( (ch= fgetc(stdin)) != EOF && ch != '\n');
printf("\nSorry i could n't read that\nplease re enter the value:: ");

if(1 == scanf("%d",&i))
break;
}

return i;
}

void display(int *a,int n)
{
int i;

printf("\n**********");
printf("\n HEAP ");
printf("\n**********\n");

puts("");
for(i=1;i <= n;i++)
printf("%d\t",a[i]);

}

void add(int val,int* a,int* n)
{
(*n)++;
a[*n] = val;
restoreup(*n,a);
}

void restoreup(int i,int *a)
{

int val;
val = a[i];

while(a[i/2] <= val)
{
a[i] = a[i/2];
i = i/2;
}

a[i] = val;
}

int del(int* a , int *n)
{
int temp,i;

temp = a[1];
a[1] = a[*n];
(*n)--;

restoredown(1,a,*n);
return temp;
}

Tree from preorder and inorder traversals

2008-04-14T06:18:00.000-07:00

program which shows the re-construction of a binary tree from inorder and preorder traversals

#include < stdio.h >
#include < stdlib.h >
#include < string.h >
#include < limits.h >

typedef struct node
{
struct node *left;
int val;
struct node *right;
}sn;

void inordert(sn*);
void freetree(sn*);

int getcount(int*);
int getroot(int*,int);
int getminindex(int*,int);
int* getleft(int,int*,int*);
int* getright(int,int*,int*);

sn* reconst(int,int*,int);
sn* allocate(int);

int preorder[] = {'A','B','D','G','H','C','E','F','I','K','J',0};

int main(void)
{
int inorder[] = {'B','G','H','D','A','E','C','I','K','F','J',0};
int i,arc;

sn* t=NULL;

arc = getcount(inorder);

t= reconst(preorder[0],inorder, arc);

printf("after reconstruction of the binary tree\n");
inordert(t);

freetree(t);

return EXIT_SUCCESS;
}

sn* reconst(int root,int *inorder,int arc)
{

int *nla,*nra,nlarc,nroot,i;
int nrarc;

sn* temp =NULL;
nlarc=nrarc=0;

if(arc == 0)
return NULL;

temp = allocate(root);

if(arc == 1)
return temp;

nla = getleft(root,inorder,&nlarc);
nroot = getroot(nla,nlarc);
temp -> left = reconst(nroot,nla,nlarc);
free(nla);

nra = getright(root,inorder,&nrarc);
nroot = getroot(nra,nrarc);
temp -> right = reconst(nroot,nra,nrarc);
free(nra);

return temp;
}

int getcount(int *inorder)
{
int count=0,i;
for(i=0;inorder[i] != 0;i++)
count++;

return count;
}

sn* allocate(int n)
{
sn* temp;
temp = malloc(sizeof(*temp));

if(!temp)
{
printf("\n memory allocation failed....");
printf("\n going to abort.....");
exit(1);
}

temp -> val = n;
temp -> left = NULL;
temp -> right = NULL;

return temp;
}

int* getleft(int root,int *inorder,int *larc)
{

int i,count;
int *nla;

i=0,count=0;

while(inorder[i] != root)
{ i++;count++;}

nla = malloc((count+1) * sizeof(*nla));
nla[count] =0;

for(i=0;i < count;i++)
nla[i] = inorder[i];
*larc = count;

return nla;
}

int getroot(int *in,int n)
{
int i,j=0,k;
int* indxarray = malloc(n * sizeof(*indxarray));

if(indxarray == NULL)
{
printf("\n memory allocation failed....");
exit(1);
}

memset(indxarray,-1,n);

for(k=0;k < n;k++)
{
i=0;
while(preorder[i])
{
if(preorder[i] == in[k])
indxarray[k] = i;
i++;
}
}
j = getminindex(indxarray,n);
return in[j];
}

int getminindex(int *index,int n)
{
int loc = -1;
int min = INT_MAX;
int i;

for(i=0;i < n;i++)
{
if(index[i] < min)
{
min = index[i];
loc = i;
}
}

return loc;
}

int* getright(int root,int *inorder,int *larc)
{
int i,count,pos,k;
int *nra,ncount;
i=0,count=0,pos=0,ncount=0;

while(inorder[i] != root)
{ i++;pos++;}

count = getcount(inorder);
ncount = (count-pos-1);

nra = malloc( (ncount+1) * sizeof(*nra));
nra[ncount] =0;
k = (pos+1);

for(i=0;i < ncount;i++)
{
nra[i] = inorder[k];
k++;
}

*larc = ncount;
return nra;

}

void inordert(sn *hd)
{
if(hd != NULL)
{
inordert(hd -> left);
printf("\t %c",hd -> val);
inordert(hd -> right);
}
}

void freetree(sn* hd)
{
if(hd)
{
freetree(hd -> left);
freetree(hd -> right);
}
free(hd);
}

scanf(" \"%[^\"]\"",s)

2008-04-10T20:53:00.000-07:00

sulekha

scanf(" \"%[^\"]\"",s); means

The scanf will expect a string enclosed within double quotes for correctly reading the input. Within the double quotes it will acceptany input other than ". It will stop reading at the second " character.

is this explanation correct..???

Eric sosman

Almost. In addition to what you've described, the scanf() will also read and discard white space (if any) prior to the first quote mark.

STRONG recommendation: Use something like "%100[" instead of just "%[", to avoid re-inventing the hazards of gets().

sulekha

suppose if I change scanf(" \"%[^\"]\"",s); to

scanf("\"%[^\"]\"",s);

the scanf() won't read and discard white space (if any) prior to the first quote mark. isn't it ?

Eric sosman

No. The format string now starts with " so scanf() will try to match a " at the start of the input. Any other input character would be a mismatch, and would cause scanf() to stop (and leave the mismatched character unread).

robert gamble

In addition to Eric's comments, it is worth noting that the "%[" conversion specifier matches *one or more* characters so it will fail if there are no characters between the quotes, i.e. "".

Evaluating arithmetic expressions

2008-04-10T11:36:00.000-07:00

producing the memory layout you really want is non-portable and deprecated

2008-04-10T10:47:00.000-07:00

aarklon

I used to argue at this point that using memory-mapped IO made it easier to write device drivers in C, since you could map devices to C structures. Unfortunately, modern C compilers pad structures for performance reasons, and trying to coerce the compiler into producing the memory layout you really want is non-portable and deprecated. So I'm leaving the argument in place, but it's really for historical interest at this point. The comments about trying to create in and out instructions do remain valid, however.

Also, when writing device drivers in C, it's a lot easier to work with when devices are in memory space. Let's suppose you have a simple device (for concreteness, let's look at the A/D convertor on an HC11. It's controlled by five registers (not counting the OPTION register), located at addresses $1030-$1034. We can define a struct that looks like this:

see:- http://www.cs.nmsu.edu/~pfeiffer/classes/473/notes/io.html

Richard

Which begs the question : since people have known for a long time that C was going to be used primarily for embedded systems in the future, why oh why is the support for non padded structures so bad? Sure some compilers have a pragma to remove padding but thats not "standard".

The FAQ says this:

http://c-faq.com/struct/padding.html

I would be interested in seeing a general approach to this

,----
| If you're worried about wasted space, you can minimize the effects of padding by ordering the members of a structure based on their base types, from largest to smallest.
`----

that is "standards compliant" and not "hard coded".

Ian collins

Every embedded compiler (ant that's quite a lot!) I've used supported packed structures. I certainly would think many times about using one that didn't.

Richard
Is the pragma line itself "standard"?

ian collins
Don't be silly, how can you standardise something a lot of machinescan't do?

Richard
It could stop the compilation? Hence standard code base.

Philip potter
The same way you standardise IEEE floating point - that is, make it an optional part of the standard.

Eric sosman

aarklon wrote:

> I used to argue at this point that using memory-mapped IO made it
> easier to write device drivers in C, since you could map devices to C
> structures. Unfortunately, modern C compilers pad structures for
> performance reasons, and trying to coerce the compiler into producing
> the memory layout you really want is non-portable and deprecated.
> [...]

Another problem that's frequently overlooked is that just getting the struct to match the hardware may not be enough. Quite commonly, such magical memory addresses are "sensitive" only when accessed in the right way: A word-sized register might respond only to a word-sized fetch or store, but not to partial accesses in byte units nor to doubleword accesses that touch two adjoining registers. Careful use of volatile can enforce the proper ordering of events (e.g., write to the "data" register *before* writing to the "strobe" register), but isn't enough to prevent an aggressive optimizer from using "store immediate byte" instead of "load word to register,store word."

That's part of what the Standard means when it says that what constitutes an "access" to a volatile variable is implementation-defined.

Morris dovey

aarklon wrote:

> I used to argue at this point that using memory-mapped IO made it
> easier to write device drivers in C, since you could map devices to C
> structures.
>Also, when writing device drivers in C, it's a lot easier to work
> with when devices are in memory space. Let's suppose you have a simple
> device (for concreteness, let's look at the A/D convertor on an HC11.
> It's controlled by five registers (not counting the OPTION register),
> located at addresses $1030-$1034. We can define a struct that looks
> like this:

It's at least as easy to use #defines to create pointer values to do the same job. In the case of your A/D, a base address ($1030) and offsets ($0-$4) is sufficient to #define five pointer values
to access (probably volatile) registers of whatever size needed.

It's simple, it's easy, and it removes all possible concerns about structure padding and the chance that different toolchains might produce different results.

... and to provide an example of this method I've posted a copy of a header file I once actually used. The register offsets for the various devices were placed in separate device-specific
header files that included this.

The file can be found at http://www.iedu.com/c/mips_io.h

Interpositioning in C-code

2008-04-10T04:46:00.000-07:00

x&(x-1) ... why only 2's complement system?

2008-04-09T23:18:00.000-07:00

Lax

Why is the "x&(x-1)" trick for removing the least significant set bit from an integer only valid on 2's complement systems?

CBFalconner

It works fine on unsigned integers also. Just write down the bit patterns involved.

walter roberson

Consider signed-magnitude and the number -2. 1 for the sign, a bunch of binary 0s, then binary 10 at the end. x-1 is -3, which is 1 for the sign, a bunch of binary 0s, then binary 11 at the end.
Bitwise and the two together and you get 1 for the sign, a bunch of binary 0s, then binary 10 at the end. Which is the representation of -2 which is the number you started with, so the technique does not work for signed-magnitude.

With this example in mind, you should easily be able to determine whether the technique works for 1's complement systems.

Eric sosman

It is valid on all systems if `x' is non-negative.That means, as a particularly useful special case, that it is always valid if `x' is unsigned.

For negative values of `x', I suggest you take pencil and paper and work through a few examples, using all three of the representations C allows: two's complement, ones'complement, and signed magnitude. To save some writing,pretend your computer uses a narrow int of maybe six oreight bits. Try a few different `x' values like -1, -2,-10, and see what happens.

Lax

So is this a good implementation-independent way of doing it?:
(signed)( x & ( (unsigned)x-1 ) )

Peter Nilsson

No, the right way is to make x unsigned to begin with, and to forget about testing bits in negative integers.

CBFalconer

>Lax wrote
>So is this a good implementation-independent way of doing it?
> (signed)( x & ( (unsigned)x-1 ) )

NO.It is a good way of getting undefined behaviour.

print output

2008-04-09T22:37:00.000-07:00

aarklon

Is it possible to write a C program to print o/p without using library functions( in standard C )..????

Walter roberson

On -some- implementations.

There are some implementations that have memory-mapped I/O --writing a byte to a particular address causes the byte to be sent to I/O (e.g., to a serial port or to a printer or whatever.)

Standard C does not -promise- that there is any way to write data to a particular absolute address, but Standard C says thatit is implementation defined as to what the meaning is of converting an integral value into a pointer. Hence an implementation is allowed to define the conversion of magic absolute I/O addresses into valid pointers to write to and thus to potentially trigger I/O.

Any program that used this technique would not be portable to any other system that did not use memory-mapped I/O, or which used different addresses for memory-mapped I/O, or to any system that had memory-protection that prevented users from writing to the magic addresses -- and of course it would not be portable to any system that basically defines the result of converting an integral value to a pointer as creating a useless junk pointer.

But any program that used this technique successfully for a specific system would not be violating any constraint in C.

The ability to create arbitrary pointers is fairly common in C implementations -- the C standard doesn't promise it will work though.

Default user

Why do you want to?

walter roberson

When I gave my reply earlier, I assumed that it yet another "job interview" type question.

Now, 25 years ago, I had real reasons for wanting to know similar information, as I was working on a multiuser 128 Mb system with no shared libraries, and being able to omit the C library from the (static) link meant a (relatively) major reduction in executable size.

LDAP Application Program Interface

2008-04-09T11:15:00.000-07:00

The LDAP Application Program Interface, described by RFC 1823, is an Informational RFC that specifies an application programming interface in the C programming language for version 2 of the Lightweight Directory Access Protocol. Version 2 of LDAP is historic. Commonly available LDAP C APIs do not strictly adhere to this specification.

see:-http://tools.ietf.org/html/rfc1823

A* algorithm

2008-04-06T02:16:00.000-07:00

/*This is the program showing implementation of a* algorithm, given n integers and a sum m ,write a program to find the set of integers summing to m using a* algorithm. */

#include< stdio.h >
#include< stdlib.h >
#include< string.h >

char bln;
int subsetsum(int*,int,int,char* ,int);
int compare(const void*,const void*);
void printanswer(int*,int,char*);

int main(void)
{

int a[] = {5,3,4,8,9,6};
int sum = 15;
int size = sizeof(a)/sizeof(*a);
int i;
char *selected = calloc(size,sizeof(*selected));

qsort(a,size,sizeof(int),compare);

for(i=0;i < (size-1);i++)
{
printf("\n i = %d",i);

if( subsetsum(a,size,sum,selected,i))
printanswer(a,size,selected);

memset(selected,0,size * sizeof(*selected));
}

return EXIT_SUCCESS;
}

int subsetsum(int *a,int n,int sum,char *selected ,int start)
{
int i;

if(sum == 0)
return 1;

for(i=start;i <= (n-1);i++)
if(selected[i] == 0 && a[i] <= sum)
{
selected[i] = 1;
if(subsetsum(a,n,sum - a[i],selected,i+1))
return 1;

selected[i] = 0;
}

return 0;
}

void printanswer(int* a,int n,char* selected)
{
int i;

for(i=0;i< n;i++)
if(selected[i])
printf("\t%d",a[i]);

puts("");
}

int compare(const void* e1,const void* e2)
{
return *(int*)e2 - *(int*)e1;
}

see:- http://www.policyalmanac.org/games/aStarTutorial.htm

padding and enums

2008-04-04T08:56:00.001-07:00

aarklon

arrays are guaranteed to be contiguous with no padding before or after any array member , but what about enums ..???

keith thompson

An enumerated type is compatible with some implementation-defined integral type. That type may have padding bits. Is that what you're asking?

aarklon

I just wanted to clear the doubt that, whether the concept structure padding also applies to enums ..???

walter roberson

Your original wording about arrays is not completely correct.It is possible for there to be padding after the final array member in a structure. For example:

struct foo { char bar[3]; int baz };

then there could be padding after bar[2] and before baz.An enumeration type is some integral type (implementation-defined which),so the same rules apply to it as apply to other integral types.

default user

Enumerations are not an aggregate. The concept of padding means nothing in that context. It seems like you think that declaring an enum means making some data structure with all those in some sort of sequence. It doesn't. It creates a type, which is in reality some sort of alias for one of the integral types, with some predefined aliased values.

keith thompson

But that padding isn't part of the array. In effect, there can be padding after the array, but not after an element of an array (a debatable distinction, but I think that's the best way to look at it)

andrey tarasevich

aarklon wrote:
> I just wanted to clear the doubt that, whether the concept structure padding also applies to enums ..???

"Structure padding" is something that is inserted between small pieces (members) of a larger composite object. Such composite objects are referred as "aggregates" in C. Structures are aggregates, they can have padding between their members. Arrays are aggregates, although they cannot have any array-specific padding between their elements.

Enums are not aggregates. They don't consist of smaller pieces. There's nowhere in enum you can insert that padding to. So I don't see how could anyone even start applying the concept of "struct padding" to enums.

CBFalconer

aarklon wrote:

> arrays are guaranteed to be contiguous with no padding before or after any array member , but what about enums ..???

No they are not.

keith thompson

What are not what?

If you're disputing the statement that arrays are guaranteed to be contiguous, I'm afraid you're mistaken; there can be no padding before or after any array element. (Depending on the context, there can be padding before or after the whole array, just as for any object.)

If you're trying to answer the "what about enums" question, I'd like to know how you've managed to interpret the question so it has a meaningful yes or no answer.

CBFalconer

If, for example, the basic element is an array of 3 bytes, but requires the alignment of 4, the individual element will be padded with an extra byte. Something like:

typedef struct elem {
int i;
char c;

} elem;

and, to me, each element of:

elem array[MAX};

will be padded accordingly. This is why such arrays cannot be compared for equality with simple code.

Andrey tarasevich

Yes, but this really has nothing much to do with the array itself. This trailing padding exists as an integral part of the above struct, not as something inserted additionally _between_ the elements of the array and specific to the the array itself.

For arrays, the following relation must hold

sizeof array = sizeof element * number_of_elements

This eliminates any possibility of the array inserting any additional padding between its elements. Any necessary padding should be already present in the element itself (in terms of it size, as returned by 'sizeof').

> and, to me, each element of:

> elem array[MAX};

> will be padded accordingly. This is why such arrays cannot be compared for equality with simple code.

I'm not really sure what exactly you mean here. But if you are saying that arrays can't be compared by raw memory comparison because padding areas might contain unpredictable bit patterns, then first of all this issue actually already applies to structs. It already exists for standalone structs, no arrays necessary. And it applies to arrays of structs just as mere consequence of that, not because of some specific property of arrays.

If array elements contain no padding of any kind (i.e. if they can be compared by raw memory comparison), then whole arrays of such elements can also be compared by raw memory comparison because, once again, arrays are not allowed to introduce any additional padding between their elements.

keith thompson

First off, your element type isn't an array of 3 bytes. If it were,it would have to be byte-aligned. For example:

typedef unsigned char tri_byte[3];
tri_byte arr[10];

Type tri_byte cannot require 4-byte alignment, and sizeof arr must be 30 in any conforming implementation. No padding is permitted within either array type.

As for the example you actually used, I assume you intend sizeof(int)== 2. If int requires word alignment, then sizeof(struct elem) must be (at least) 4; padding is inserted within the structure itself, probably after c (or possibly after i). This padding is required because of the requirements on arrays, but it applies to all objects of type struct elem.

Every object type must have a size that's a multiple of its required alignment. Padding can exist within structures, but not between array elements.

Richard tobin

CBFalconer wrote:
>>>> arrays are guaranteed to be contiguous with no padding before or after any array member

Note the phrase "before or after".

>typedef struct elem {
> int i;
> char c;
>} elem;

>and, to me, each element of:

> elem array[MAX};

>will be padded accordingly.

As you say, each element will be padded. There will be no padding *before or after* each element. The padding is *in* the elements.

Robbie Hatley

"aarklon at gmail dot com" blythely made this abstraction error:

> Arrays are guaranteed to be contiguous with no padding before > or after any array member, but what about enums?

Arrays are objects.

Enums are types.

Objects may have padding, or they may not.

Types, on the other hand, are incapable of either "having" or "not having" padding.

Perhaps you're confused by the fact that enums are declared using curly braces and lists of constant names, like so:

enum Robbie
{
Alpha,
Bravo,
Charlie,
Delta,
Echo,
Foxtrot,
Golf

};

That just defines "Alpha" as an alias for "0", "Bravo" as an alias for "1", etc. It does not store any data,so there's no place to put any padding.

Compare that to a struct instance:

struct Bobbie
{
char Tom;
int Jack;

} Fred;

Object Fred will have (on most 32-bit machines and compilers)8 bytes: 1 byte for Tom, 3 bytes of padding, and 4 bytes for Jack. That's so that the members of Fred start on word boundaries ("word" meaning the width of the CPU's registers). Makes the compiled program more efficient.

Towers of Hanoi

2008-04-03T09:39:00.000-07:00

a simple program implementing towers of hanoi problem

#include< stdio.h >
#include< stdlib.h >

void toh(int,char,char,char);

int main(void)
{

char source= 'A',temp = 'B', dest='C';

int n=4;

toh(n,source,temp,dest);

return EXIT_SUCCESS;
}

void toh(int n,char s, char t,char d)
{
if(n > 0)
{
toh(n-1,s,d,t);
printf("\nmove disk %d %c ---> %c",n,s,d);
toh(n-1,t,s,d);

}
}

-------------------------------------------------------------------------------

#include "stdio.h"
#include "stdlib.h"

void move(int,char,char,char);

int main(void)
{
int n,ch;

while(scanf("%d",&n) != 1 )
{

while( (ch = fgetc(stdin)) != EOF && ch != '\n');
printf("\n Sorry, I couldn't read that");
printf("\n Please re-enter the values:: ");
fflush(stdout);

if(scanf("%d",&n) == 1)
break;
}

move(n,'X','Y','Z');

return EXIT_SUCCESS;
}

void move(int n,char x, char y, char z)
{

if(n == 1)
printf("\n Move disk from peg %c to peg %c",x,z);
else
{
move(n-1,x,z,y);
move(1,x,'',z);
move(n-1,y,x,z);
}
}

Review of C elements of style,ISBN 8170293030, BPB publications

2008-04-02T22:30:00.000-07:00

aarklon

I was going through the book "C Elements of style" by steve oualline.
in this book many guidelines are given.the following were seen in the book as rules

1) while(1) is preferred over for(;;)
2) use of const is preferred over #define
3) unless extreme efficiency is warranted, use printf instead of putc & puts
4) always split a for statement into 3 lines

5) when splitting up a conditional clause(?:),write it on three lines: the condition line,the true-value line, and the false-value line.indent the last two lines an extra level

6)allow no more than 5 parameters to a function
7)avoid do/while use while and break instead.

8)use the comma operator inside a for statement only to put together
two statements. never use it to combine three statements

9)always put a break at the end of the last case in a switch statement

10) do not use absolute paths in #include directives. let the -I
compile option do the work

11) begin all debug printfs with ## ex:- printf("## state=%d",state);

12) the best indentation is 4 spaces

13) if a macro contains more than one statement, use a do while structure to enclose the macro

ex:- #define ABORT \
do{ \
puts("abort"); \
exit(8); \
}while(0);

can anyone give examples for the justification of above rules ..????
OR
To what extent these rules are true..???

while(1) is preferred over for(;;)
user923005

I am opposite here. The constructs create identical results and the meaning for both is obvious. Some lints and compilers will whine about while (1) but they do not add any noise for for(;;).

Eric sosman

(1) is an expression of somebody's personal preference,in the form of a rule. It seems to me to have as much force as "indent in multiples of three spaces" or "adverbAlways verbUse adjectiveHungarian nounNotation."

Richard Tobin

An experienced C programmer will of course be familiar with both, but I don't think the meaning of "for(;;)" is obvious. It doesn't follow from anything else that an empty continuation condition is true; the best you can do is say that it would be pointless if it worked the other way. "while(1)" on the other hand is not a special case at all.

Default user

This will lead to warnings in some cases. That being said, it's my preferred way.

Richard Heathfield

Balderdash. Preferred by him, possibly, but not by me. In the vanishingly rare circumstances where an infinite loop is appropriate, for(;;) expresses the intent without inducing some implementations to have a giddy fit over a constant conditional expression.

Marc mclntyre

any decent compiler will convert them into exactly the same opcodes.

use of const is preferred over #define

user923005

This one is obvious. #define can unexpectedly change something if you are not careful.

Eric sosman

2) has appeared in the draft CERT "Secure C Coding Standard," and some justification is given there. For what it's worth, I find the justifications unconvincing.

Flash Gordon
The problem is that const does not introduce a compile time constant so it is not suitable for a lot of purposes and can cause confusion in others. I would say that (ab)using enum to create constants of type int has value and #define for the rest often makes more sense.

defaultuser

That won't work for array dimensions. There should at least be exceptions for that case.

Keith thompson

If your compiler supports VLAs, it *will* work for array dimensions.
And that could be a problem.
"const" doesn't create a constant expression. If you don't need a constant expression (i.e., one that must be evaluable at compile time), then by all means use "const"; it's cleaner IMHO than #define.But if you need a constant expression, "const" just won't do the job.

Richard Heathfield

Balderdash. Try it and see.
const int MAX = 10;
main()
{
int class[MAX] = {0};
}

The above code is carefully designed to break everywhere! But the reason it breaks differs depending on what language you're using. In C++, it's okay for an array size to be specified using a const (but you can't use class as an object name). In C99, it's okay to specify a variable-length array's size using a const (but the code breaks because implicit int has gone). But in C90, the code breaks because you can't use const to specify array sizes, which are a large part of what #defines are used for (and most of the other uses for #define are better dealt with by enum than by const).

keith thompson

It breaks for the reasons you specify under any compiler that conforms to *some* standard. But if it weren't for one thing that you don't mention, it would compile without so much as a warning under at least one compiler that provides (in a non-conforming mode) several language extensions.
That one thing is the initializer. Providing an initialization for a VLA is a constraint violation (C99 6.7.8p3). Which is too bad; being able to initialize it with the {0} idiom would be handy.

Mark mclntyre

Try using a const to define an array size (in C89), or as a case label.

Himanshu chauhan

One benefit of using (2) I can see is, while debugging you can see the symbol rather than a value.

unless extreme efficiency is warranted, use printf instead of putc & puts

user923005

Nonsense. If there is no format string, use puts(). If you are outputting a single character, use putc().

Eric sosman

(3)seems silly. It might make sense if inverted ("Don't switch from printf() to putchar() just for a tiny speed gain"), but in the actual form used ... Does this Rulemaker go on to recommend pow(x,2) instead of x*x, or pow(2,6) instead of 64?

Walter robinson

My -speculation- would be that the reasoning is that for text output, printf() appears so often that when putc() or puts() appears, people may have to stop and think about whether there is anything "special" or "magic" about what is being output or about the way that putc() or puts() operate so as to warrant the use of those functions instead of printf().For example, I see puts() seldom enough that I tend to forget that puts() adds \n automatically and then when I glance at code that uses puts() I tend to think, "Hold on, where's the \n ??" So there is some "magic" about puts() that has to be remembered. (especially as fputs() does not add a \n ). putc(), though, I personally find immediately obvious.
defaultuser

I can't see why this would be preferable. Besides being possibly less efficient, printf() is often less readable and more prone to error.

keith thompson

puts() also avoids problems like: char *message = "Hello, %d world"; printf(message); But the solution to that is to understand who printf works. I have no strong preference one way or the other for printf vs. puts in cases where either will do the job.

mark mclntyre
again identical if you have a decent compiler.

keith thompson

No, it's the compiler that's relevant. A library implementation of printf can't avoid parsing the format string, even if it optimizes the case where there are no '%' characters. A compiler, on the other hand, can sometimes convert a printf call to an equivalent puts call. always split a for statement into 3 lines

always split a for statement into 3 lines

Flash gordon
As an "always" I definitely disagree. In the simple case of something like: for (i=0; i < lim; i++)it is completely pointless in my opinion. On some longer or more complex instances it can make sense to split it.

5) when splitting up a conditional clause(?:),write it on three lines: the condition line,the true-value line, and the false-value line.indent the last two lines an extra level

Flash gordon

Again, a stupid rule in my opinion. Think what it would do to...
fprintf(fp,"stuff %d more stuff",ptr?*ptr:0);

Then imagine you have more parameters before and after that one. I come across requirements most easily implemented like this when producing interfacing files to be sent to other systems.

allow no more than 5 parameters to a function

Flash gordon
A bit arbitrary and people will certainly argue about precisely what the limit should be, but makes more sense.

avoid do/while use while and break instead.

flash gordon

This is just plain stupid. If the problems maps properly on to a
do/while loop then use that rather than trying to bend some other
construct to your needs. I don't use them very often, but when they are the correct construct they are the correct construct.

8)use the comma operator inside a for statement only to put together two statements. never use it to combine three statements

Flash gordon
Again, rather arbitrary, people will definitely argue over what the limit should be.

9)always put a break at the end of the last case in a switch statement

Dan corbitt

My addition:
a switch statement *must* contain a default branch, even if it only
contains:
default:
assert(0);
break;
because you know it will never be exercised.

Ben pfaff

I have mixed feelings about this, because it (in my experience) defeats the ability of the compiler to remind you that you forgot to add a case for some value of an enumeration type.

Richard Tobin

Dann Corbit wrote:
> a switch statement *must* contain a default branch, even if it only
> contains:
> default:
> assert(0);
> break;
>because you know it will never be exercised.

I often do that, but I wouldn't make it an absolute rule. For example, if the branches of a switch exhausted all the values of an enum, and I was confident that the variable only had instances of that enum assigned to it, I probably wouldn't bother with the default. Similarly, if an integer variable represented a boolean, I wouldn't bother to write

if(t == 0)
... false case ...;
else if(t == 1)
... true case ...;
else
assert(0);

even though a value of 2 would imply an bug just as much as an unexpected value in a switch.

keith thompson

(Richard Tobin) writes:
> Dann Corbit wrote:
>>a switch statement *must* contain a default branch, even if it only
>>contains:
>> default:
>> assert(0);
>> break;
>>because you know it will never be exercised.
> I often do that, but I wouldn't make it an absolute rule. For
> example, if the branches of a switch exhausted all the values of an
> enum, and I was confident that the variable only had instances of that
> enum assigned to it, I probably wouldn't bother with the default.
And, as others have pointed out, adding a "default:" might inhibit a
warning if you leave something out.
> Similarly, if an integer variable represented a boolean, I wouldn't
> bother to write
> if(t == 0)
> ... false case ...;
> else if(t == 1)
> ... true case ...;
> else
> assert(0);
> even though a value of 2 would imply an bug just as much as an
> unexpected value in a switch.
If t represents a boolean value, I wouldn't compare it to either 0 or
1:
if (t) {
... true case ...
}
else {
... false case ...
}
(Or use !t and reverse the order if you prefer.)
For that matter, if t really is boolean, then a value of 2 *doesn't* necessarily imply a bug.

if a macro contains more than one statement, use a do while structure to enclose the macro

ex:- #define ABORT \
do{ \
puts("abort"); \
exit(8); \
}while(0);

Kenneth brody

Doesn't that violate rule 7?

Chris Thomasson

How about: #define ABORT(msg, status) (puts(msg), exit(status))

keith thompson

Good advice, bad example. Since a function call is an expression,there's no need for the do{}while(0) trick. I'd write the above as:

#define ABORT (puts("abort"), exit(8))

(Assuming, of course, that 8 is a sensible exit value on the system I'm using, and that the "abort" message really should go to stdout rather than stderr.)

And didn't an earlier rule say to use printf rather than puts? Efficiency is hardly a concern if you're aborting the program.

The do-while trick is very useful when you can't avoid putting statements in a macro, but the "," and "?:" operators make it easier to avoid statements than you might think.

Finally, the semicolon at the end of the macro definition defeats the purpose of the do-while trick. Is that really there in the book?

Ben bacarisse

I hope it does not include the ; at the end. As you have it,

if (C)
ABORT;
else
go_on();

is a syntax error.

Ben pfaff

If you do this, then you should omit the ; at the end of the do...while statement. Otherwise it defeats the purpose, because you cannot use the macro as if it were a statement.

It is unconventional, in my experience, to define an object-like macro this way. It would be more conventional to name it ABORT(), so that it looks like a function.

The value 8 is not a portable exit status.

aarklon

Ben Pfaff wrote:

> The value 8 is not a portable exit status.

Then can you give examples for portable exit status, other than
EXIT_FAILURE,EXIT_SUCCESS

walter roberson

0 is the only other portable exit status.

For example, under VMS, the exit status was logically divided into bit fields, with some of the bits assigned to represent the error severity, some of them to represent the facility, and some of them to represent the particular error for that facility. If you randomly choose an exit value, you could end up with some rather strange error messages getting printed out by the VMS CLI.

aarklon

why 1 is not considered as a portable exit status, AFAIK exit(1)is usually used to indicate error conditions isn't it ...????

Walter roberson

"usually" is not the same as "portably". There are real operating systems (with real C compilers) for which exit(1) means something specific to the operating system.

Ben pfaff

>>aarklon writes:
>>Ben Pfaff wrote:

>>The value 8 is not a portable exit status.
>>then can you give examples for portable exit status, other than
>>EXIT_FAILURE,EXIT_SUCCESS
>> 0 is the only other portable exit status.

> why 1 is not considered as a portable exit status, AFAIK exit(1)
> is usually used to indicate error conditions isn't it ...????

Here is what the standard says:

If the value of status is zero or EXIT_SUCCESS, an implementation-defined form of the status successful termination is returned.If the value of status is EXIT_FAILURE, an implementation-defined form of the status unsuccessful termination is returned. Otherwise the status returned is implementation-defined.

Here is what the rationale says:

The argument to exit is a status indication returned to the invoking environment. In the UNIX operating system, a value of zero is the successful return code from a program.As usage of C has spread beyond UNIX, exit(0) has often been retained as an idiom indicating successful termination, even on operating systems with different
systems of return codes. This usage is thus recognized as standard. There has never been a portable way of indicating a non-successful termination, since the
arguments to exit are implementation-defined.The EXIT_FAILURE macro was added to C89 to provide such a capability. EXIT_SUCCESS was added as well.

As I understand it, on some operating systems, e.g. OpenVMS,particular return values are interpreted with specific and nuanced meanings, and so it is best not to wantonly return values other than the ones with standard meanings.

begin all debug printfs with ##
ex:- printf("## state=%d",state);

Eric sosman

It's nice to distinguish them in *some* consistent way.It's also nice to mark "ordinary" messages in a way that aids automated scanning of log files and so on. Also, consider whether such messages might be better on stderr than stdout.

keith thompson

That's one approach. It's certainly not the only one.(Insert lengthy flame war about printf vs. debuggers.)

do not use absolute paths in #include directives. let the -I compile option do the work

Keith thompson

That's good advice for those systems on which it's relevant.

Eric sosman

Usually good, but follow established convention for the environment you're writing in. E.g., POSIX code should
include rather than .

Ben pfaff

I would ordinarily consider both sys/types.h and types.h to be relative paths. /usr/include/sys/types.h would be an absolute path (and indeed, I avoid them in #include directives to the extent that I don't recall ever using one).

Eric sosman

Yeah, I think the author's use of "absolute" is suspect. Most likely (it seems to me), he was talking about

#include "libfoo/foo.h"
#include "../../libbar/bar.h"

... and the like.Not "absolute" in any usual sense, but certainly "location-dependent."

Richard heathfield

Relatively absolute?

joachim schmitz

Absolutly relative!

the best indentation is 4 spaces

Keith thompson
That happens to be what I like, but I wouldn't argue that it's "the best". Consistency is far more important than the choice of 4 vs. 3 vs. whatever.

Eric sosman
Does the author cite any research for this conclusion? The only study I've ever seen -- and it was long ago and I can no longer cite the source -- found that a two-space indent was too narrow and four just a bit too wide; that study's conclusion was that a three-space indent was most likely "best."

Richard Heathfield

The study was correct to identify that four space indent is too wide, but erroneous in recommending three spaces because, obviously, it has to be a power of two. One space is clearly too few, but two is just right.

Walter roberson

3 is representable as a power of 2. Not an integral power, but you didn't specify integral power ;-) (And if you had, some wag like me would have specified 1/2 a space, since -1 is integral.)

eric sosman

... but three *is* a power of two! It's

Now that I think of it, though, the study's conclusion was indeed probably wrong. The interpolation should have been on the exponent, and the recommended indentation width should have been 2^1.5 = 2.82842712474619009760+ spaces.)

default user

Now, this is just insane. All right-thinking people know that the correct answer is "three". Everything else is morally repugnant and/or
a terrorist plot.

richard heathfield

Anyone who is concerned that you may be part of some kind of comp.lang.c clique or cabal can now rest easy. No self-respecting cabalier would use a
three-space indent.

joachim schmitz

What's wrong with TAB? So everyone can adjust the tab width to his/her liking?

Richard Heathfield

Firstly, it doesn't work terribly well on Usenet, since some news clients strip tabs out before display. Worse, some clients strip tabs out *before reply* - so it looks fine in the reader, but goes pear-shaped in a quote.

Secondly, let's take an example like this:

rc = myfunctioncall(arga,
argb,
argc);

which looks lovely with spaces. Now let's try it with an eight-space tab (which I'm imitating with spaces, for the sake of Usenet clients!):

rc = myfunctioncall(arga,
argb,
argc);

If we replace those eight-space sequences with \t markers, we get this:

\trc = myfunctioncall(arga,
\t\t\t argb,
\t\t\t argc);

That's fine, although it looks messy, because the editor will expand the tabs to eight spaces.

Now let's use a three-space tab setting, and see what it expands to:

rc = myfunctioncall(arga,
argb,
argc);

argb and argc still line up with each other, of course, but they no longer line up with arga. So the three-space tabber takes code that was written with eight-space tabs and loads it into his editor, and much of the indentation is suddenly far less readable than the writer intended.

Either of these reasons is sufficient for a Usenetting programmer to stick to spaces, and the latter is, in my view, sufficient even for a non-Usenetting programmer, which is why I started using spaces-not-tabs some time before I began posting to Usenet (so it's just as well for me that the two reasons both point in the same direction!).

Incidentally, I generally set up my editor to convert tabs to spaces, so that I can still /use/ the TAB key. My decision to drop from a four-space indent to a two-space indent was a direct consequence of beginning to post to Usenet - I haven't yet found a newsreader that converts tabs to spaces (let alone a user-configurable number of spaces) on *writing*, and I got sick and tired of typing spacespacespacespace at the start of practically every code line.

Joachim schmitz

I don't usually write code for Usenet (and if, I'd indeed rather use spaces
and avoid // comments). And I guess most programmers don't.

Not in my case

C certifications

2008-04-02T08:08:00.000-07:00

sophia
where can i get a good/valid certification in C programming similar to the one given below
http://www.brainbench.com/xml/bb/common/testcenter/taketest.xml?testId=52

Gerry Ford
The first thing I would do is turn to English orthography. The whole "certification" thing I associate outside of the C programming language. Maybe you can make it germane. --

Richard Heathfield
Make up your mind - did you want a good test, or the test you mention? We looked at the Brainbench test some years ago, and identified a number of serious issues with it.

Santosh
Don't you think a certification with an institute is better than an online one? You'll find that in general online certifications are not well regarded.

Jack thomson
I'm a Brainbench C certified professional, believe me it doesn't make any difference. The only certifications that are considered valuable are the domain related certifications. Ex: Cisco Certifications.

Broli
Do you know of some institute/organization which provide such certifications in C ??

santosh
This depends on the country doesn't it? Usually for a job in country X, it's best to get a certification from a good organisation in country X. And even a small amount of actual experience is worth several certifications.

Jack Thomson

May be, i don't know about different country preferences, But brainbench is not a standard certification to go for, I just went for it when I was just out of my college hoping it could add a great value to my resume. But it doesn't add any value, no body actually knows about it, I was asked what is this Brainbench in almost all interviews... So I finally took it out of my resume :-(.
If somebody wants to show their language and technical skill then I think writing their own tools and making it free source may add value, Since it shows that the candidate possesses most of the skills required for a project development.

rot-13 algorithm

2008-03-30T09:11:00.001-07:00

Diagram showing the working of recursive functions

2008-03-27T23:49:00.000-07:00

precedence rule for understanding C-declarations

2008-03-27T02:27:00.001-07:00

magic decoder ring for C declarations

2008-03-27T02:03:00.000-07:00

Minimum height of a binary tree

2008-03-26T12:06:00.000-07:00

Maximum height of a binary tree

2008-03-24T04:25:00.000-07:00

Tree Operations

2008-03-24T01:06:00.000-07:00

1) to compute the no: of nodes in the binary tree
int count(struct node* node)
{
if(node == NULL) return 0;
else
return( 1 + count(node-> left) + count(node-> right));
}

2) to count the internal nodes
int internal(tree* t)
{
if( (t==NULL) ((t ->left == NULL) && (t -> right == NULL)))
return 0;
else
return( 1 + internal(t -> left) + internal(t -> right) );
}

3) to count external nodes
int external(tree *t)
{
if(t == NULL) return 0;
else
if( (t -> left== NULL) && (t ->right == NULL))
return 1;
else
return(external(t -> left) + external(t -> right));
}
3. /* Compute the "maxDepth" of a tree -- the number of nodes along the longest path from the root node down to the farthest leaf node. */

int maxDepth(struct node* node)
{
if (node==NULL) { return(0); }
else { // compute the depth of each subtree
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);
// use the larger one
if (lDepth > rDepth) return(lDepth+1);
else return(rDepth+1);
}
}

4)
/* Given a non-empty binary search tree, return the minimum data value found in that tree. Note that the entire tree does not need to be searched. */
int minValue(struct node* node)
{
struct node* current = node;
// loop down to find the leftmost leaf
while (current->left != NULL)
{current = current->left;}
return(current->data);
}

5)hasPathSum() Solution

/* Given a tree and a sum, return true if there is a path from the root down to a leaf, such that adding up all the values along the path equals the given sum. Strategy: subtract the node value from the sum when recurring down, and check to see if the sum is 0 when you run out of tree. */

int hasPathSum(struct node* node, int sum)
{ // return true if we run out of tree and sum==0
if (node == NULL) { return(sum == 0); }
else { // otherwise check both subtrees
int subSum = sum - node->data;
return(hasPathSum(node->left, subSum) hasPathSum(node->right, subSum)); }
}

6) printPaths()
/* Given a binary tree, print out all of its root-to-leaf paths, one per line. Uses a recursive helper to do the work. */

void printPaths(struct node* node)
{ int path[1000];
printPathsRecur(node, path, 0);
}

/* Recursive helper function -- given a node, and an array containing the path from the root node up to but not including this node, print out all the root-leaf paths. */

void printPathsRecur(struct node* node, int path[], int pathLen)
{ if (node==NULL) return;
// append this node to the path array
path[pathLen] = node->data; pathLen++;
// it's a leaf, so print the path that led to here
if (node->left==NULL && node->right==NULL)
{ printArray(path, pathLen); }
else {
// otherwise try both subtrees
printPathsRecur(node->left, path, pathLen);
printPathsRecur(node->right, path, pathLen);
}
}
// Utility that prints out an array on a line.
void printArray(int ints[], int len) { int i; for (i=0; i{ printf("%d ", ints[i]); } printf("\n"); }

8. mirror() Solution
/* Change a tree so that the roles of the left and right pointers are swapped at every node.

void mirror(struct node* node)
{
if (node==NULL) { return; }
else {
struct node* temp;
// do the subtrees
mirror(node->left);
mirror(node->right);
// swap the pointers in this node
temp = node->left;
node->left = node->right;
node->right = temp;
}
}

9)
sameTree() Solution
/* Given two trees, return true if they are structurally identical. */

int sameTree(struct node* a, struct node* b)
{ // 1. both empty -> true
if (a==NULL && b==NULL) return(true);
/* 2. both non-empty -> compare them */
else
if (a != NULL && b != NULL)
{ return( a->data == b->data && sameTree(a->left, b->left) &&
sameTree(a->right, b->right) );
}
// 3. one empty, one not -> false

else return(false);
}

10) /* Returns true if a binary tree is a binary search tree. */
int isBST(struct node* node)
{
if (node==NULL) return(true);
/* false if the max of the left is > than us */
if (node->left!=NULL && maxValue(node->left) > node->data) return(false);
/*false if the min of the right is <= than us */
if (node->right!=NULL && minValue(node->right) <= node->data) return(false);
// false if, recursively, the left or right is not a BST
if (!isBST(node->left) !isBST(node->right)) return(false);
// passing all that, it's a BST
return(true);
}

Euler tour traversal

2008-03-20T01:27:00.000-07:00

Printing an arithmetic expression

2008-03-20T01:05:00.000-07:00

in sufficiency of pre and post order

2008-03-19T23:32:00.000-07:00

Binary tree creation special case

2008-03-18T23:58:00.000-07:00

Stupid Indian MCA Kids Question

2008-03-18T11:47:00.000-07:00

Mention the type of applications which can be developed using C language?

Prakash T

This is Prakash from in India at tamilnadu. I am a MCA Student.
Please answer the Que: Mention the type of applications which can be developed using C language?

Thomas Mathews

Gosh, that is going to be a huge list.Let us start off with two categories: embedded systems and
non-embedded (desktop, etc.). Many applications can be developed for each category. Now the task is to list uses of each category and that would lead to applications.

Perhaps the easier question to answer is:
"What applications can't be written using the C language?"

Here are some applications that can be wrriten, I know of:

1. Operating systems.

Enumerate at your risk.MS Windows, Linux, Unix, VxWorks, Nucleus Plus,VMS, MS-DOS, Vrtx, etc.

2. Controllers (ahh, a wide field)

Tape drives, disk drives, laser printers, ink jet printers, vending machines, microwave ovens, industrial mills, mailing machines, VCRs, DVD players, airplane controllers, car controllers, etc.

3. Desktop applications (yes, another wide field)

Video games, databases, database front-ends, spreadsheets,word processors, editors, image editors, architecture tools, schematic routers, assemblers, compilers,web & internet applications.

4. Scientific applications
{I don't have much knowledge in this arena.}

I'm just curious how much time it will take you to enumerate or list all of the applications that can be written using the C language. I think it might be one of those NP-Complete problems, such as finding the last digit of PI (3.14....).

E Robert Tisdale

Any application that can run on modern digital computers as long as there is a C compiler for the target computer.

Walter Roberson

>Prakash T. wrote:
>> Mention the type of applications
>> which can be developed using C language?
>Any application that can run on modern digital computers
>as long as there is a C compiler for the target computer.

That's a close approximation, but not completely true -- at least not without using undefined behaviour or compiler extensions.

Modern digital computers can have operations which are not part of the C language, and which are not representable in C.

For example, if you have memory-mapped I/O (which is common), then you need the ability to convert numeric addresses into C pointers in order to perform the I/O. Now, for files that can be hidden in the implimentation of the C f*() routines such as fopen() and fwrite(), but anything beyond pure files (such as serial ports or graphics) is beyond the scope of fopen(),so even if the graphics can be responsably be handled via fopen()/fwrite() [rather than, e.g., being a video page written to directly] then one is getting into Undefined Behaviou.

The same thing happens if you have special I/O instructions instead of memory-mapped I/O: you are only within the boundaries of the C standard when the library routines are talking to file subsystems.

Thus, what can be implimented in *standard* C with no extensions is in actuality only a subset of what can be "run" on "modern digital computers". Roughly speaking, *standard* C corresponds [at most] to that which is "Turing computable".

The problem with that is, as a friend of mine explored in depth in his PhD thesis, that the majority of computers do not "compute" particular results within the traditional meaning of Turing machines.

What, for example, is a toaster "computing" ? Considering differences in moisture content and Brownian motion of air currents,and differences in thickness and slize of slices, a toaster isn't
likely to get the same "inputs" twice in a row.

Erik De Castro lopo

Absolutely anything.

I'm a Linux user and I can point you to the following:

- the Linux kernel (99% C, the rest assembler)
- nearly all user space programs (bash shell, and most
command line tools).
- The GNU compiler collection (gcc, g++ etc).
- apache web server
- The X sindow system
- Most of the programs for the GNOME desktop
- mail servers (postfix, sendmail etc)
- filter servers (SAMBA, NFS)
- graphics manipulation (the gimp)
- email client programs (eg sylpheed)

and probbly much more.

Stupidity revealed to the fullest extent......

sathyashrayan

We have achieved a success in chess games. Thanks for the 9 GM from India. But regarding programming, that too in c and asm we still stand behind. I could see some c questions from Indian named posters in this Usenet. But comparing those questions with that of the questions asked and answers given by those experts in this Usenet responder, we are at the beginning.

Programming is an art but not a science. A 10-year-old student can program well if he is given a proper training. There are lot of very young programmers in Europe, US, and other countries. If we look at the track records in this Usenet it will be more than 10 years.

Once I wanted to learn the implementation of tree-data-struct. I tried several different ways and asked some help from this Usenet news group. In replay I got an American saying "WTF you are doing as a programming". WTF is an American expression.Then I went through his web site I come across the excellent work done by him in tree data-struct as a Stanford Grad student. I don't blame him for those words because if I would have been in his position I will have the same kind of expression. But I blame our system.

My conclusion of that is the system that is been followed in India. MCA and BE students are considered as a programmers. But when I come across some MCA and BE students they don't even take the C and ASM programming as a serious one. Even if some body programs well then it is his or her own personal interest and self-study but not because of the way they have been thought. They will learn and write the data-struct as in the book without knowing the concept! Example: They
will cast malloc()'s return and allocate mem. So taking the MCA and BE as a qualification is a bad for future Indian programmers.

But I don't know about NCST teachings.

In my view the industry's approach must change and there should be a school of programming as a full academics background India.

Creating Tree from In-order and Pre-Order Traversals

2008-03-18T11:22:00.001-07:00

hierarchy of computer system software

2008-03-16T10:26:00.000-07:00

2008-03-16T08:07:00.000-07:00

2008-03-16T02:41:00.000-07:00

2008-03-16T02:08:00.000-07:00

2008-03-15T20:27:00.000-07:00

2008-03-15T20:22:00.000-07:00

2008-03-14T23:07:00.000-07:00

2008-03-14T22:34:00.000-07:00

Famous Software Failures

2008-03-13T10:43:00.000-07:00

The following is a testimony to software failures and famous bugs...

Therac-25 (1985-1987)

Six people were overexposed during radiation treatments for cancer by Canada's Therac-25 radiation therapy machine. Three of these patients were believed to have died from the overdoses. The root cause was a lack of quality assurance, which lead to an over-complex, inadequately tested, under-documented system developed, and subsequently to the failure to take adequate corrective action. (Pooley & Stevens, 1999)

London Ambulance System (1992)

A succession of software engineering failures, especially in project management, caused 2 failures of London's (England) Ambulance dispatch system. The repair cost was estimated at £9m, but it is believed that people died who would not have died if ambulances had reached them as promptly as they would have done without the failures.

Denver baggage handling system

The Denver airport baggage handling system was so complex (involving 300 computers) that the development overrun prevented the airport from opening on time. Fixing the incredibly buggy system required an additional 50% of the original budget - nearly $200m.

Taurus (1993)
Taurus, the planned automated transaction settlement system for the London Stock Exchange was canceled after 5 years of failed development. Losses are estimated at £75m for the project and £450m to customers. (Pooley & Stevens, 1999)

Ariane 5 (1996)
The Ariane 5 rocket exploded on its maiden flight in June [4], 1996 because the navigation package was inherited from the Ariane 4 without proper testing. The new rocket flew faster, resulting in larger values of some variables in the navigation software. Shortly after launch, an attempt to convert a 64-bit floating-point number into a 16-bit integer generated an overflow. The error was caught, but the code that caught it elected to shut down the subsystem. The rocket veered off course and exploded. It was unfortunate that the code that failed genereated inertial reference information useful only before lift-off; had it been turned off at the moment of launch, there would have been no trouble. (Kernighan, 1999)

E-mail buffer overflow (1998)
Several E-mail systems suffer from a "buffer overflow error", when extremely long e-mail addresses are received. The internal buffers receiving the addresses do not check for length and allow their buffers to overflow causing the applications to crash. Hostile hackers use this fault to trick the computer into running a malicious program in its place.

USS Yorktown (1998)

A crew member of the guided-missile cruiser USS Yorktown mistakenly entered a zero for a data value, which resulted in a division by zero. The error cascaded and eventually shut down the ship's propulsion system. The ship was dead in the water for several hours because a program didn't check for valid input. (reported in Scientific American, November 1998)

Mars Climate Orbiter (September 23rd, 1999)

The 125 million dollar Mars Climate Orbiter is assumed lost by officials at NASA. The failure responsible for loss of the orbiter is attributed to a failure of NASA’s system engineer process. The process did not specify the system of measurement to be used on the project. As a result, one of the development teams used Imperial measurement while the other used the metric system of measurement. When parameters from one module were passed to another during orbit navigation correct, no conversion was performed, resulting in the loss of the craft. http://mars. jpl.nasa. gov/msp98/ orbiter/

2008-03-13T10:37:00.000-07:00

2008-03-13T09:39:00.000-07:00

2008-03-13T06:25:00.000-07:00

2008-03-11T22:21:00.000-07:00

execute a different function before main()

2008-03-11T22:15:00.000-07:00

aarklon

Hi all,
recently i read the following passage in a site

it is a compiler dependent thing if some feature is available that allows you to execute some function before main() is called. In turbo C compiler, there's one such fearture....the #pragma startup directive.
I m giving an example of its use:-

#include"stdio.h"
void fun();
#pragma startup fun
int main()
{
printf("Arun");
}

void fun()
{
printf("Anand \n");

}

The o/p of the program given above will be :- Anand

my question is there a standard way in ANSI-C
to execute a different function before main() is called....??????

Richard Bos

No. But why would you? Call that function as the first thing you do in main() itself. The only reason I can think of why that wouldn't work is when you call main() recursively, and
a) that's a very bad idea in the first place; b) the trivial workaround is left as an exercise for the reader.

Eric sosman

Yes. Two ways, in fact:

1) Run your program in a freestanding environment, where "the name and type of the function called at program startup are implementation-defined."

2) Use an editor to change the name of your existing main() to something else, and to change the name of your desired startup function to main().

(Yes, this is somewhat tongue in cheek. But there's a serious point behind it: If you can modify the program source, you are in control of what main() does. You can therefore make it do whatever you wanted this other, magical function to do -- so you don't need any magic.)

aarklon

is it possible to modify the start up code in a hosted environment so as to change the name and type of the function called at program startup..???

santosh

If you have the source, yes. But you'll need to recompile and reinstall the library. Just what is your actual problem that apparently seems to be forcing you to massive hacks?

walter robinson

wrote:
> is it possible to modify the start up code in a hosted environment
> so as to change the name and type of the function called at program
>startup..???

It depends on the environment.

[OT]

For example on SGI IRIX, there is the following linker option:

-init ifuncsymbol
Puts a call to ifuncsymbol into the code that rld(5)
exercises before the main program begins. The ifuncsymbol
contains initialization code to be called before control is
passed to main. In the case of a DSO opened with dlopen(3C)
or sgidladd(3C) an initialization function is called after
the DSO is loaded but before it is referenced.

George peter staplin

aarklon wrote:
> Eric Sosman wrote:
>> aarklon wrote:
>> > Hi all,
>> > recently i read the following passage in a site

>> > it is a compiler dependent thing if some feature is available that
>> > allows you to execute some function before main() is called.
>> > In turbo C compiler, there's one such fearture....the #pragma startup
>> > directive.
>> > I m giving an example of its use:-

>> > #include"stdio.h"
>> > void fun();
>> > #pragma startup fun
>> > int main()
>> > {
>> > printf("Arun");
>> > }
>> > void fun()
>> > {
>> > printf("Anand \n");
>> > }
>> > The o/p of the program given above will be :- Anand
>> > my question is there a standard way in ANSI-C
>> > to execute a different function before main() is called....??????

>> Yes. Two ways, in fact:

>>1) Run your program in a freestanding environment, where
>> "the name and type of the function called at program startup
>> are implementation-defined."

> is it possible to modify the start up code in a hosted environment
> so as to change the name and type of the function called at program
> startup..???

Yes, it's possible with a hosted environment but not from standard C.

When a program is loaded with most (Windows and Unix-like) systems, the OS jumps to an offset for _start in assembly code.

If you're using gcc in Windows or a POSIX system you can see what startup files gcc links with via: gcc -v somefile.c

The startup files are typically named like crt0.o. They are implemented in assembly code usually and the various crt*.o do tasks like implementing exit(main(argc,argv)); and setting up the environment

Wang cong

It depends on the environment.
Sure. In gcc you can use __attribute__((constructor)). ;)

santosh

no, because different implementations will do this differently. Even for Linux the start-up sequence is very different under x86 and Itanium. For hosted implementations the system will typically jump into a predefined entry point in your program. This normally enters the initialisation code of your C runtime library that will linked in with your program. Often the entry point is specified in source with the label _start:. This code does some system specific initialisation and ten calls the function called main, which of course, then enter your
program. After you return from main, fall of it's end, or call exit,_Exit or abort, execution once again enters the shutdown code in your C library, which may do a whole host of things like flushing streams, closing file handles, calling handlers registered with atexit etc.,before finally handing control over to the host system.

To know the details you need to look at the source for your system C runtime library. The details are very system specific and no one explanation will suffice.

Kenneth brody

aarklon wrote:-

> it is a compiler dependent thing if some feature is available that
> allows you to execute some function before main() is called.
> In turbo C compiler, there's one such fearture....the #pragma startup
> directive.
> I m giving an example of its use:-

> #include
> void fun();
> #pragma startup fun
[...]
> my question is there a standard way in ANSI-C
> to execute a different function before main() is called....??????

I assume you want something equivalent to atexit(), which lets you specify functions to call after exit() [or a return from main()]? Obviously, unlike atexit(), you can't have your function call a
function to tell it to do so.

You can't do this in any standard way. The closest thing you can do is to simply call them at the very top of main().

Can you specify more than one "#pragma startup", and call more than one function before main()?

[Warning: Untested code follows. Typos may be present. I leave it
as an exercise for the reader to fix them.]

If you only need a single function, why not declare some global variable:

extern void (*RunAtStartup)(void);

At the start of main, add:

if ( RunAtStartup != NULL )
(*RunAtStartup)();

Then, in whatever module needs this special startup function, you include:

extern void TheFunctionINeed(void);
void (*RunAtStartup)(void) = TheFunctionINeed;

Unfortunately, this only works if there is only a single function that needs to be run. If you need more than one, then you need to build an array of function pointers, all in one place, in which case you might as well just call the functions.

Merge sort

2008-03-11T10:56:00.000-07:00

/* Program of sorting using merge sort through recursion*/

#include"stdlib.h"
#include"stdio.h"
#define MAX 20
void merge (int[], int, int, int);
void merge_sort (int[], int, int);
int
main (void)
{
int i, n, a[MAX], ch;
printf ("Enter the number of elements : ");
fflush (stdout);
while (scanf ("%d", &n) != 1)

{
while ((ch = fgetc (stdin)) != EOF && ch != '\n');
printf ("\n Sorry, I couldn't read that");
printf ("\n Please re-enter the values:: ");
fflush (stdout);
if (scanf ("%d", &n) == 1)
break;
}
for (i = 0; i < n; i++)

{
printf ("Enter element %d : ", i);
fflush (stdout);
while (scanf ("%d", &a[i]) != 1)

{
while ((ch = fgetc (stdin)) != EOF && ch != '\n');
printf ("\n Sorry, I couldn't read that");
printf ("\n Please re-enter the values:: ");
fflush (stdout);
if (scanf ("%d", &a[i]) == 1)
break;
}
}
printf ("\nUnsorted list is :");
for (i = 0; i < n; i++)
printf ("%d\t", a[i]);
merge_sort (a, 0, n - 1);
printf ("\nSorted list is :");
for (i = 0; i < n; i++)
printf ("%d\t", a[i]);
puts ("");
return EXIT_SUCCESS;
}

void
merge_sort (int a[MAX], int low, int high)
{
int mid;
if (low != high)

{
mid = (low + high) / 2;
merge_sort (a, low, mid);
merge_sort (a, mid + 1, high);
merge (a, low, mid, high);
}
}

void
merge (int a[MAX], int low, int mid, int high)
{
int temp[MAX];
int i = low;
int j = mid + 1;
int k = low;
while ((i <= mid) && (j <= high))

{
if (a[i] <= a[j])
temp[k++] = a[i++];

else
temp[k++] = a[j++];
} /*End of while */
while (i <= mid)
temp[k++] = a[i++];
while (j <= high)
temp[k++] = a[j++];
for (i = low; i <= high; i++)
a[i] = temp[i];
}

Dann corbitt

This sort routine has to be recompiled for every new sized array.

> int i = low;
> int j = mid + 1;
> int k = low;
> while ((i <= mid) && (j <= high))

> {
> if (a[i] <= a[j])
> temp[k++] = a[i++];

> else
> temp[k++] = a[j++];} /*End of while */

> while (i <= mid)
> temp[k++] = a[i++];
> while (j <= high)
> temp[k++] = a[j++];
> for (i = low; i <= high; i++)
> a[i] = temp[i];

> }- Hide quoted text -

> - Show quoted text -

If you want simplicity then maybe something like this:
/*
** The following routines are for a horrible but easily understandable
** form of merge-sort. Here, we actually join the ordered data
*/
template < class Etype >
void MMERGE(Etype A[], Etype B[], size_t l, size_t m,
size_t r)
{
size_t i = l;
size_t j = m + 1;
size_t k = l;
/* Put the smallest thing into array B */
while ((i <= m) && (j <= r)) {
if (A[i] < A[j]) /* Etype needs a < operator. */
B[k++] = A[i++];
else
B[k++] = A[j++];
}
/* Copy leftover (if any) */
while (i <= m) {
B[k++] = A[i++];
}
while (j <= r) {
B[k++] = A[j++];
}
/* Transfer back to original array */
for (k = l; k <= r; k++) {
A[k] = B[k];
}

}

/* Helper function for icky(tm) merge sort */
template < class Etype >
void MSORT(Etype A[], Etype B[], size_t l, size_t r)
{
size_t m; /* The middle */
if (l < r) { /* Cut problem to half size until 1
unit */
/* Divide partition by 2, sort and merge */
m = ((l + r) >> 1);
MSORT(A, B, l, m);
MSORT(A, B, m + 1, r);
MMERGE(A, B, l, m, r); /* A single element is ordered */
}

}

#ifdef UNIT_TEST
#define M_S_SIZE 10000000
int a[M_S_SIZE];
int t[M_S_SIZE];
#include
#include
#include
using namespace std;

int checksort(int arr[], size_t arr_size)
{
size_t i;
for (i = 0; i < arr_size - 1; i++) {
if (arr[i] > arr[i + 1]) {
cout << "OUT OF SORT! arr[" << i << "] = " << arr[i] << "
arr[" << i + 1 << "] = " << arr[i + 1] << endl;
return 0;
}
}
return 1;
}

int main(void)
{
size_t i;
time_t start,
end;
double delta;
srand(time(NULL));
for (i = 0; i < M_S_SIZE; i++)
a[i] = rand();
start = time(NULL);
MSORT(a, t, 0, M_S_SIZE - 1);
delta = difftime(time(NULL), start);
cout << "Mergesort used " << delta << " seconds to sort " <<
M_S_SIZE << " values." << endl;
checksort(a, M_S_SIZE);
return 0;
}

#endif

If you want a really useful sort, then examine the possibility of external merge sorting.

Gene

You can do the job with half the temporary space (or less) and less code. Sorry this is in Ada rather than C or C++. But it is not too hard to recode. 'First in C is 0 (the first index of the array). Similarly 'Last and 'Length have the obvious meaning. Ada arrays allow arbitrary index ranges. Declare creates a new scope variables in the middle of code.

procedure Sort(List : in out List_Type) is
Mid, First : Positive;
begin
if List'Length > 1 then
Mid := (List'First + List'Last) / 2;
Sort(List(List'First .. Mid));
Sort(List(Mid + 1 .. List'Last));

-- Find index of merge start (efficiency hack).
First := List'First;
while List(First) < List(Mid + 1) loop
First := First + 1;
end loop;

-- Merge.
declare
Temp : List_Type := List(First .. Mid);
P1 : Positive := First;
P2 : Positive := Mid + 1;
I : Positive := First;
begin
while P1 <= Mid loop
if P2 > List'Last or else Temp(P1) < List(P2) then
List(I) := Temp(P1);
P1 := P1 + 1;
else
List(I) := List(P2);
P2 := P2 + 1;
end if;
I := I + 1;
end loop;
end;
end if;
end Sort;

binary tree from array

2008-03-10T10:48:00.000-07:00

/* This program illustrates the concept of creating binary tree from array*/

#include "stdio.h"
#include "stdlib.h"

typedef struct node
{
struct node *left;
char data;
struct node *right;
} sn;

sn *buildtree (int);
void inorder (sn *);
void freetree (sn *);

char a[] = {
'Z', 'X', 'C', 'V', 'B', 'N', 'M', '\0', '\0', 'A', '\0',
'\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0'
};

int
main (void)
{
struct node *root;
root = buildtree (0);
printf ("In-order Traversal:\n");
inorder (root);
puts ("");
freetree (root);
return EXIT_SUCCESS;
}

sn *
buildtree (int n)
{

sn *temp = NULL;
if (a[n] != '\0')
{
temp = malloc (sizeof (*temp));
if (temp == NULL)
{
printf ("Error\nmalloc failed");
exit (1);
}

temp->left = buildtree (2 * n + 1);
temp->data = a[n];
temp->right = buildtree (2 * n + 2);
}
return temp;
}
void
inorder (sn * root)
{
if (root != NULL)
{
inorder (root->left);
printf ("%c\t", root->data);
inorder (root->right);
}
}

void
freetree (sn * root)
{
if (root != NULL)
{
freetree(root->left);
freetree(root->right);
}
free (root);
}

Application BInary interface

2008-03-10T10:27:00.000-07:00

In computer software, an application binary interface (ABI) describes the low-level interface between an application program and the operating system, or the interface between an application and its libraries, or that between component parts of an application. An ABI is similar to an application programming interface (API), however the latter defines a source code interface.[1] Simply put, ABIs enable binary compatibility, whereas APIs enable source code compatibility.

see:
developer.apple.com/documentation/DeveloperTools/Conceptual/LowLevelABI/Articles/32bitPowerPC.html

indegree and outdegree of each node of a graph

2008-03-09T07:00:00.000-07:00

/*
* Program to compute the indegree and outdegree of each node of a graph
* by using adjacency matrix representation of graph
*
* */

#include"stdio.h"
#include"stdlib.h"

void
buildadj (int a[][10], int n)
{
int i, j;

for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
printf ("Enter 1 if there is a node from %d to %d else 0\n:: ", i, j);
scanf ("%d", &a[i][j]);
}
}

int
outdegree (int adj[][10], int x, int n)
{
int i, count = 0;

for (i = 0; i < n; i++)
if (adj[x][i] == 1)
count++;

return count;
}

int
indegree (int adj[][10], int x, int n)
{
int i, count = 0;

for (i = 0; i < n; i++)
if (adj[i][x] == 1)
count++;

return count;
}

int
main (void)
{

int adj[10][10];
int i, n;

printf ("\nEnter the no: of nodes(max 10) :: ");
scanf ("%d", &n);

buildadj (adj, n);

for (i = 0; i < n; puts (""), i++)
{
printf ("\n Out-Degree of the node = %d", outdegree (adj, i, n));
printf ("\n In-Degree of the node = %d", indegree (adj, i, n));
}

puts ("");
return (EXIT_SUCCESS);
}

Depth first traversal

2008-03-09T06:59:00.001-07:00

/*
* Program to compute depth first traversal of a graph
* it makes use of an array visited of n elements where
* n is the no: of vertices of the graph and the elements are boolean
* if visited[i] = 1 then it means that ith vertex is visited
* */

#include"stdio.h"
#include"stdlib.h"

void
buildadj (int a[][10], int n)
{
int i, j;

for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
printf ("Enter 1 if there is a node from %d to %d else 0\n:: ", i, j);
scanf ("%d", &a[i][j]);
}
}

void
dfs (int x, int visited[10], int adj[][10], int n)
{

int j;
visited[x] = 1;
printf ("node visited id = %d\t", x);

for (j = 0; j < n; j++)
if (adj[x][j] == 1 && visited[j] == 0)
{
/* printf("\n adj[%d][%d]",x,j); */
dfs (j, visited, adj, n);
}
}

int
main (void)
{

int adj[10][10];
int i, j, n, visited[10];

printf ("\nEnter the no: of nodes(max 10) :: ");
scanf ("%d", &n);

buildadj (adj, n);

for (i = 0; i < n; puts (""), i++)
for (j = 0; j < n; j++)
printf ("%d\t", adj[i][j]);

for (i = 0; i < n; i++)
visited[i] = 0;

for (i = 0; i < n; i++)
if (visited[i] == 0)
dfs (i, visited, adj, n);

puts ("");
return (EXIT_SUCCESS);
}

padding and arrays

2008-03-09T06:50:00.000-07:00

sophia

arrays are guaranteed to be contiguous with no padding before or after any array member
Is it because all the elements are of the same type ?

now consider this

int a[] = {10,20,30,40,50};
float f = 3.14f;
void *p[]= {&a[1],&a[0],&a[2],&a[4],&f};

now my question is In all cases all the elements of p will be stored contiguous with no padding before or after any array member ?

mark bluemel

You've said p is an array of pointers to void. Why should you expect them to be stored otherwise? How they are initialised is not important.

Richard heathfield

.5.7 of C89: "All the expressions in an initializer for an object that has static storage duration or in an initializer list for an object that has aggregate or union type shall be constant expressions."

An array has aggregate type.

3.4: " More latitude is permitted for constant expressions in initializers. Such a constant expression shall evaluate to one of the following:

* an arithmetic constant expression,

* an address constant, or

* an address constant for an object type plus or minus an integral
constant expression.

[...] An address constant is a pointer to an lvalue designating an object of static storage duration, or to a function designator".

So the initialization of p[] is illegal (but does not violate a constraint, so no diagnostic message is required, but the behaviour of the program is undefined).

You could fix this by making a[] and f static.

Once you've done that, the answer is "yes" - p[] will be an array of five void *, each of which occupies exactly sizeof(void *) bytes.

Richard Tobin

The elements of p are still all the same type: they're all void *.The fact that they're initialized from values of other types doesn't change that.

what will be the o/p

2008-03-06T21:53:00.000-08:00

what will be the output of

#include "stdio.h"
#include "stdlib.h"

int main(void)
{
int a[] = {10,20,30,40,50};
int *p;
p = (int*)((char*)a + sizeof(int));

printf("%d",*p);
return EXIT_SUCCESS;
}

This question may have different answers depending on the compiler used(16/32 bit) and the processor used

case 1:- a 32 bit compiler and a little endian machine

here sizeof int will be 4. now a points to first element in the array i.e 10 ( 00001010 00000000 00000000 00000000) and (char*)a points to 00001010.
now (char*)a + 4 means (char*)a + 4 * sizeof(char)
i.e (char*)a + 4 points to 4 byte positions away from the current position i.e it will point to byte position (00010100) of 20(00010100 00000000 00000000 00000000 ) so output will be 20 itself

case 2:- a 16 bit compiler and a little endian machine

Here size of int will be 2 now a points to the first element in the array i.e 10 now (char *)a + 2 points to 2 byte positions away from the current position i.e it will point to lower byte position of 20 1.e( 00010100 00000000) so output will be 20 itself

Richard Heathfield

int a[] = {10,20,30,40,50}; defines an array of int with five elements.
int *p; defines a pointer to int.
a yields &a[0], the address of the lowest-address byte in the a array,
which is guaranteed to be aligned correctly for int because it's an int
array.

(char *)a yields the same address, but with type char *.
Because arrays are guaranteed to be contiguous with no padding before or
after any array member, (char *)a + sizeof(int) yields the address of the
second int in the array, with type char *. Again, this is guaranteed to be
aligned correctly for int.

(int *) yields the same address as its operand, but with type int *.
p = assigns that address to p.
printf("%d", *p); will write "20" to the standard output device.
Guaranteed. (Well, printf can fail, and of course there's no newline, but
you know what I mean.)

Ian collins

No, it will not. p points the the second int in the array, byte order (or sizeof int ) has no effect.

Robert Hatley

#include
#include

int main(void)
{
int a[] = {10,20,30,40,50};
int b = 0;

b = (int)(*((char*)a + sizeof(int)));
printf("%d\n", b);
return EXIT_SUCCESS;

}

the pointer is now a char pointer, not an int pointer, so when you dereference it with the "*" I think it gives the byte that it points to (the lowest-RAM-address byte of the "20"), cast back to an int. So I think it will print "20" for little-endian and "0" for big-endian,regardless of sizeof(int).

2008-03-06T05:24:00.000-08:00