C, and data structures, and.. stuff

[Barnaby W. Füi]

I already have dealt with threading in Python, can be extremely not fun. :Q But for some situations it's cool. Generally I either avoid it, unless there's a simple way to go about it (i.e. I can get away with only a few semaphores, and it's easy to tell when/where they get acquired and released).

Not really sure what my goal is with C.. I guess mostly to be able to hack other software, considering most stuff (well, unix stuff) is written in C. I have had countless situations where I want to play with something or try to track down a bug, and I either get nowhere, or I don't get very far, because my C sucks. 🙂

edit: also, so I can make non-trivial Python C modules. 😀

 

[PowerMacG5]

If you sit down and learn Binary Tree's, they are a pretty amazing structure. In the simplest terms, it is a doubly linked list. Each node of a Binary Tree has two pointers, which can point to two memory locations, one, or NULL. Binary tree's are very easy to navigate using recursion. You have the base case, and the condition's, and once you figure out how what these should be, it's easy as cake. One major use for Binary Trees are something called Binary Search Trees. In a Binary Search Tree, each node to the left or right of the parent node meets a certain condition, so this makes navigation a very easy task. The time it takes in the worst case is O(Length of tree). The Length of the tree is the length of the root node to the longest leg. Binary Tree's can come in handy when you want a quick way to search. In a Binary Search tree of numbers, all numbers to the left of its parent node are less than it, and all to the right are greater. This mean the recursive navigation is very simple. I hope this helps in some way.

 

[Mucman]

The more reason you should play with threads in C! Since you already know many of the fundamentals, it might be an interesting exercise so see how
they are implemented in C.

Oh, and another project (my OS course was awesome 🙂), try creating a pseudo-shell, but only using system calls. I got some C source code if you want
to take a gander. I've emulated about 10 shell commands (ls, du, ls -la, cp, mv, pwd, cd). It would be cool to expand on it so that it actually executes
code and forks new processes etc... Since you want to get into the programming of your favorite OS's, learning system calls is very important 🙂

 

[Barnaby W. Füi]

Originally posted by: KraziKid
If you sit down and learn Binary Tree's, they are a pretty amazing structure. In the simplest terms, it is a doubly linked list. Each node of a Binary Tree has two pointers, which can point to two memory locations, one, or NULL. Binary tree's are very easy to navigate using recursion. You have the base case, and the condition's, and once you figure out how what these should be, it's easy as cake. One major use for Binary Trees are something called Binary Search Trees. In a Binary Search Tree, each node to the left or right of the parent node meets a certain condition, so this makes navigation a very easy task. The time it takes in the worst case is O(Length of tree). The Length of the tree is the length of the root node to the longest leg. Binary Tree's can come in handy when you want a quick way to search. In a Binary Search tree of numbers, all numbers to the left of its parent node are less than it, and all to the right are greater. This mean the recursive navigation is very simple. I hope this helps in some way.

Cool. That's why I linked to that ternary article; a ternary tree should be even more efficient than a binary one. If you draw out a binary and a ternary tree, with the same number of items, it'll always take fewer hops to find your item in the ternary tree. Hm, I guess a base-four would be even more efficient, wouldn't it? And so on. I guess it gets to a point where the number of comparisons needed to take each step outweighs the shallowness of the items. Hm, maybe that's the whole point of a binary tree.. it DOES relate to the binary nature of computers! A comparison is either matching or not, and that's how it decides which branch to follow. On a base-3 computer, comparisons would be like cmp() and return less than, equal, or greater than, so only on a ternary computer would a ternary tree be more efficient.

... I guess.

 

[PowerMacG5]

Originally posted by: Mucman
The more reason you should play with threads in C! Since you already know many of the fundamentals, it might be an interesting exercise so see how they are implemented in C. Oh, and another project (my OS course was awesome 🙂), try creating a pseudo-shell, but only using system calls. I got some C source code if you want to take a gander. I've emulated about 10 shell commands (ls, du, ls -la, cp, mv, pwd, cd). It would be cool to expand on it so that it actually executes code and forks new processes etc... Since you want to get into the programming of your favorite OS's, learning system calls is very important 🙂

System calls are important, but they aren't a hard thing to understand. I can make a C program in 10 seconds (including compile time) that will turn the ls command on Linux into the dir command in Windows. You can do it even faster by using a batch script, but thats not what he's after.

 

[Barnaby W. Füi]

Originally posted by: Mucman
The more reason you should play with threads in C! Since you already know many of the fundamentals, it might be an interesting exercise so see how
they are implemented in C.

Hm, I probably will at some point.. will probably have to find a reason to do so first, though. 😛

Oh, and another project (my OS course was awesome 🙂), try creating a pseudo-shell, but only using system calls. I got some C source code if you want
to take a gander. I've emulated about 10 shell commands (ls, du, ls -la, cp, mv, pwd, cd). It would be cool to expand on it so that it actually executes
code and forks new processes etc... Since you want to get into the programming of your favorite OS's, learning system calls is very important 🙂

I've already made a shell-like interface before, but I dunno about learning OS-type stuff, I don't know if I want to dig into that or not. Right now I have the most fun coding user-level software.

 

[Barnaby W. Füi]

Originally posted by: KraziKid

Originally posted by: Mucman
The more reason you should play with threads in C! Since you already know many of the fundamentals, it might be an interesting exercise so see how they are implemented in C. Oh, and another project (my OS course was awesome 🙂), try creating a pseudo-shell, but only using system calls. I got some C source code if you want to take a gander. I've emulated about 10 shell commands (ls, du, ls -la, cp, mv, pwd, cd). It would be cool to expand on it so that it actually executes code and forks new processes etc... Since you want to get into the programming of your favorite OS's, learning system calls is very important 🙂

System calls are important, but they aren't a hard thing to understand. I can make a C program in 10 seconds (including compile time) that will turn the ls command on Linux into the dir command in Windows. You can do it even faster by using a batch script, but thats not what he's after.

I think you guys might be meaning different things - I'm thinking of system calls as in chdir(), stat(), unlink(), etc. KraziKid, are you talking about system() and execlmnop() and whatnot?

 

[Mucman]

Just throwing suggestions up, that's all 🙂

Time to go to the beach now!

 

[Mucman]

Originally posted by: BingBongWongFooey

Originally posted by: KraziKid

Originally posted by: Mucman
The more reason you should play with threads in C! Since you already know many of the fundamentals, it might be an interesting exercise so see how they are implemented in C. Oh, and another project (my OS course was awesome 🙂), try creating a pseudo-shell, but only using system calls. I got some C source code if you want to take a gander. I've emulated about 10 shell commands (ls, du, ls -la, cp, mv, pwd, cd). It would be cool to expand on it so that it actually executes code and forks new processes etc... Since you want to get into the programming of your favorite OS's, learning system calls is very important 🙂

System calls are important, but they aren't a hard thing to understand. I can make a C program in 10 seconds (including compile time) that will turn the ls command on Linux into the dir command in Windows. You can do it even faster by using a batch script, but thats not what he's after.

I think you guys might be meaning different things - I'm thinking of system calls as in chdir(), stat(), unlink(), etc. KraziKid, are you talking about system() and execlmnop() and whatnot?

I'm talking low level system calls... using stat() to get the fname, or number of disk blocks the file is taking, etc... my du command is pretty
spiffy since it works with recursion 🙂

 

[Descartes]

Originally posted by: BingBongWongFooey
Got a question about types. Ok, so I have this "list" type, a list of ints. I have functions for manipulating it and stuff. Now, if I wanted to use the same thing for some char arrays, or some longs, or whatever, do I have to basically copy and paste all of this and make small changes to accommodate the difference in type? Or can I make some sort of generic container that will hold things of any type?

Yes, a void pointer can reference any type in C, but you'll have to cast it in order to dereference it. What this means if that you cannot polymorphically refer to any of the types passed into your functions (something that OO languages handle natively) because there's no concept of derivation/generalization; further, there are no templates as others have said.

What's typically done is a form of logical cohesion (see Code Complete); you pass in a parameter indicating what type is to be used. e.g.:

#define TYPE_INT 1
#define TYPE_CHARP 2
void Foo(void * p, int t)
{
switch (t)
{
case TYPE_INT: // dereference 'p' for as int
break;
case TYPE_CHARP: // dereference 'p' as pointer to char
break;
}
}

A lot of the older "flat" systems libraries were implemented in this manner (e.g. the win32 api). These libraries generally have monolithic functions like DoStuff(SOME_CONSTANT); hardly functionally cohesive.

 

[Barnaby W. Füi]

Originally posted by: Descartes

What's typically done is a form of logical cohesion (see Code Complete); you pass in a parameter indicating what type is to be used. e.g.:

#define TYPE_INT 1
#define TYPE_CHARP 2
void Foo(void * p, int t)
{
switch (t)
{
case TYPE_INT: // dereference 'p' for as int
break;
case TYPE_CHARP: // dereference 'p' as pointer to char
break;
}
}

A lot of the older "flat" systems libraries were implemented in this manner (e.g. the win32 api). These libraries generally have monolithic functions like DoStuff(SOME_CONSTANT); hardly functionally cohesive.

Yep, that's what I'm trying to do now. http://incise.org:82/~death/mlist2.c

Still have errors, but I think I'm getting close. 🙂

edit: woohoo I'm so happy, I'm actually getting somewhere 🙂

http://incise.org:82/~death/mlist3.c

.. Feels like I'm basically trying to Pythonize C for myself; having a generic type "object" (struct) and then letting it be any real C type underneath, and making different data structures (well, only the list for now) that can hold these generic objects.

 

[CTho9305]

"void *" = generic object

 

[Descartes]

Originally posted by: CTho9305
"void *" = generic object

In C we have to be pedantic, and calling it a "generic object" is incorrect. A void pointer is simply a pointer to an unspecified data type. C has neither generics nor objects, so calling it a "generic object" would be incorrect on both counts.

Not trying to be combative, just clear 🙂

 

[TerryMathews]

Just wanted to throw in here that binary trees are used in place of ternerary trees, or any other for that matter, because they only require one comparison to decide which path to follow, vs. two or more. A ternerary tree creates shorter trees, but the advantage doesn't offset the doubling of comparisions necessary to traverse the tree.

A ternerary tree is also relatively expensive memory-wise as each node would have an additional pointer per node.

 

[PowerMacG5]

Originally posted by: BingBongWongFooey

Originally posted by: KraziKid If you sit down and learn Binary Tree's, they are a pretty amazing structure. In the simplest terms, it is a doubly linked list. Each node of a Binary Tree has two pointers, which can point to two memory locations, one, or NULL. Binary tree's are very easy to navigate using recursion. You have the base case, and the condition's, and once you figure out how what these should be, it's easy as cake. One major use for Binary Trees are something called Binary Search Trees. In a Binary Search Tree, each node to the left or right of the parent node meets a certain condition, so this makes navigation a very easy task. The time it takes in the worst case is O(Length of tree). The Length of the tree is the length of the root node to the longest leg. Binary Tree's can come in handy when you want a quick way to search. In a Binary Search tree of numbers, all numbers to the left of its parent node are less than it, and all to the right are greater. This mean the recursive navigation is very simple. I hope this helps in some way.

Cool. That's why I linked to that ternary article; a ternary tree should be even more efficient than a binary one. If you draw out a binary and a ternary tree, with the same number of items, it'll always take fewer hops to find your item in the ternary tree. Hm, I guess a base-four would be even more efficient, wouldn't it? And so on. I guess it gets to a point where the number of comparisons needed to take each step outweighs the shallowness of the items. Hm, maybe that's the whole point of a binary tree.. it DOES relate to the binary nature of computers! A comparison is either matching or not, and that's how it decides which branch to follow. On a base-3 computer, comparisons would be like cmp() and return less than, equal, or greater than, so only on a ternary computer would a ternary tree be more efficient. ... I guess.

I've never heard of a ternary tree, but I would assume it would not be very efficient. With a binary tree, there is only one question with two possible answers that are needed for a tree traversal. In a hypothetical ternary tree, there could be multiple questions with multiple answers. The code would be quite strange.

EDIT: bah, I didn't see this:

Originally posted by: TerryMathews
Just wanted to throw in here that binary trees are used in place of ternerary trees, or any other for that matter, because they only require one comparison to decide which path to follow, vs. two or more. A ternerary tree creates shorter trees, but the advantage doesn't offset the doubling of comparisions necessary to traverse the tree. A ternerary tree is also relatively expensive memory-wise as each node would have an additional pointer per node.

until after I posted. But i guess we think alike 🙂. Yes, a ternary tree would have a shorter length, but the variables for a traversal would be too many to need to keep track of, and the recursive algorithm would probably be quite ugly, while binary tree recursive algorithms are quite elegant.

 

[CTho9305]

Originally posted by: Descartes

Originally posted by: CTho9305
"void *" = generic object

In C we have to be pedantic, and calling it a "generic object" is incorrect. A void pointer is simply a pointer to an unspecified data type. C has neither generics nor objects, so calling it a "generic object" would be incorrect on both counts.

Not trying to be combative, just clear 🙂

BBWF isn't a C person (at least, not yet), so I was translating into the crazytalk used by non-C langauges 😉.

 

[Descartes]

Originally posted by: CTho9305

Originally posted by: Descartes

Originally posted by: CTho9305
"void *" = generic object

In C we have to be pedantic, and calling it a "generic object" is incorrect. A void pointer is simply a pointer to an unspecified data type. C has neither generics nor objects, so calling it a "generic object" would be incorrect on both counts.

Not trying to be combative, just clear 🙂

BBWF isn't a C person (at least, not yet), so I was translating into the crazytalk used by non-C langauges 😉.

I believe you were being facetious, but if not, the master should not mislead the journeyman 🙂

 

[Barnaby W. Füi]

Having problems, if you want to look, it's about 2/3 of the way down in mlist_del() here (problem described in comments): http://incise.org:82/~death/mlist4.c

I'm sort of having a hard time understanding what exactly to malloc() and free(). I malloc() a struct, but do I malloc() any of its members? Is there some rule of thumb for what you do and don't need to malloc()?

 

[JSClark]

btw, are you going pure C, or are you mixing in C++ as well?

Nah, for the forseeable future, just plain C.[/quote]

IMO, I think it would be worth it to check out C++, as its a more powerful language over C. I'm learning C right now, plan on going to C++ once I get good with this...

 

[Barnaby W. Füi]

Originally posted by: JSClark

btw, are you going pure C, or are you mixing in C++ as well?

Nah, for the forseeable future, just plain C.

IMO, I think it would be worth it to check out C++, as its a more powerful language over C. I'm learning C right now, plan on going to C++ once I get good with this...[/quote]

I have no doubt that I'll eventually learn C++, but right now I want to focus on C, for lots of reasons. I do have a vague familiarity with C++, so I do understand the basic differences.

 

[ProviaFan]

Originally posted by: JSClark

btw, are you going pure C, or are you mixing in C++ as well?

Nah, for the forseeable future, just plain C.

IMO, I think it would be worth it to check out C++, as its a more powerful language over C. I'm learning C right now, plan on going to C++ once I get good with this...

Hmm, I'm learning C++ right now (with Deitel & Deitel); is that a mistake (i.e. should I learn C first, then C++)? I'm hoping to "go back" and pick up C after I get done with this, if it's possible. 🙂

 

[Descartes]

Originally posted by: BingBongWongFooey
Having problems, if you want to look, it's about 2/3 of the way down in mlist_del() here (problem described in comments): http://incise.org:82/~death/mlist4.c

I'm sort of having a hard time understanding what exactly to malloc() and free(). I malloc() a struct, but do I malloc() any of its members? Is there some rule of thumb for what you do and don't need to malloc()?

Not to sound snide, but you free() what you malloc(). You need to malloc() storage that is not determined at compile-time. The perfect example is your list; you can't possibly determine how many items will be added in order to allocate the appropriate space, so you mallocate each one at run-time when they add an item to the list. You can of course mallocate anything to which a pointer can reference, and you can have a pointer of any type, so... the rule "that which is not determined at compile-time' seems the best to me.

 

[Barnaby W. Füi]

Originally posted by: jliechty

Originally posted by: JSClark

btw, are you going pure C, or are you mixing in C++ as well?

Nah, for the forseeable future, just plain C.

IMO, I think it would be worth it to check out C++, as its a more powerful language over C. I'm learning C right now, plan on going to C++ once I get good with this...

Hmm, I'm learning C++ right now (with Deitel & Deitel); is that a mistake (i.e. should I learn C first, then C++)? I'm hoping to "go back" and pick up C after I get done with this, if it's possible. 🙂

I think the issue is not specific to C and C++, but programming in general; "should I learn low-level stuff first, or high-level stuff first?" I honestly don't think it makes a *huge* difference, it probably is much more dependant on the individual. I started off with VB and then learned a *tiny* bit of C++, then a tiny bit of shell scripting, and then PHP was the first language that I really learned well. After that, I learned Python. And now I'm learning C (although it's been trickling in a tiny bit through osmosis for a couple years too). None of those steps were particularly difficult, even though I pretty much went from high-level ("very high-level" actually) to C which nowadays is pretty low-level (is it still technically considered to be high-level?). But a lot of people would never be able to do that. And others would rather start with assembly and then learn C and so on. Actually, what is probably most important, IMO, is whether you are genuinely interested in a language and want to do real things with it. I would never know PHP or Python as well as I do if I wouldn't have written non-trivial things with them.

 

[Barnaby W. Füi]

Originally posted by: Descartes

Originally posted by: BingBongWongFooey
Having problems, if you want to look, it's about 2/3 of the way down in mlist_del() here (problem described in comments): http://incise.org:82/~death/mlist4.c

I'm sort of having a hard time understanding what exactly to malloc() and free(). I malloc() a struct, but do I malloc() any of its members? Is there some rule of thumb for what you do and don't need to malloc()?

Not to sound snide, but you free() what you malloc().

I *do* know that much.

You need to malloc() storage that is not determined at compile-time. The perfect example is your list; you can't possibly determine how many items will be added in order to allocate the appropriate space, so you mallocate each one at run-time when they add an item to the list. You can of course mallocate anything to which a pointer can reference, and you can have a pointer of any type, so... the rule "that which is not determined at compile-time' seems the best to me.

Ok. So an int never needs to be malloce'd, A pointer itself never needs to be malloc'ed. The thing about these list items is that currently, the ones that use char*s just point to the original string, instead of copying it and holding it inside of the struct. So I don't need to malloc these? Or should I make a copy the string instead?

edit: IT'S ALIVE! Got the big bugs worked out... for now. 😀 http://incise.org:82/~death/mlist5.c

 

[lordex]

Originally posted by: Mucman
Yes O(1) is similar to O(c). By saying O(1) though you are saying that you gaurantee every hash table lookup will involve 1 comparison and you are
done. This is usually not practical because of memory limitations, and doesn't address possible collisions.

Just double checked my analysis book, 🙂 Seems you can prove by definition that O(1) equals O(c), where c is a constant. I think there isn't a theoretical term to differentiate a strict no-miss hash from a may-have-a-couple-retries one. There probably isn't any practical reason for us to differentiate them, either, since the performance difference is trivial.