Link | bodom_lx at task3 dot cc

La portabilità del codice esiste o no?

June 24th, 2008 bodom_lx No comments

Immaginate questo pensiero contornato da mille bestemmie..
Perchè uno straccio di programma in C che usa si e no 10 syscalls e un signal handler (tutto standard), compilato con gcc 4.0.1 sotto Mac Os X Leopard, quindi certificato Unix 03, e perfettamente funzionante…NON FUNZIONI su Gnu/Linux 2.6.18 + gcc 4.1.2 e Gnu/Linux 2.6.24 + gcc 4.3.1?
Segmentation Fault a manetta..e si che mi sembrava un po’ permissivo gcc 4.0.1 su Mac os X quando lavoravo con puntatori a stringhe e liste linkate..
Caro Gnu/Linux, sto tornando.

Hash Maps with linear probing and separate chaining

April 28th, 2008 bodom_lx No comments

Time for two new C programs! At the DSA course I learned something about Hash Tables and collision resolutions.
I just implemented insert/search/print operations.

The first source code is an implementation of a Hash Map with open addressing (linear probing) as collision resolution method.
The following are the interesting functions of the program. As always, take a look at the source code for comments:

// hashMapLinear[] is the hash map
void linearProbingInsert(int value){
int probe = hash(value);
while (hashMapLinear[probe]!=0){
probe = fmod((probe+1),SIZE_HASH_MAP);
}
hashMapLinear[probe] = value;
}

int linearProbingSearch(int value){
int probe = hash(value);
int i;
for(i=0;i<size_hash_map ;i++){
if(hashMapLinear[probe]==value)
return TRUE;
probe = fmod((probe+1),SIZE_HASH_MAP);
}
return FALSE;
}

Download: hash-map-linear-probing.c

The second program is an implementation of a Hash Map with chaining as collision resolution method.
Interesting functions:

// t_hashTableNode is a struct that is created as single linked list
void chainedHashInsert(int value){
int probe = hash(value);
if(hashMapChained[probe] == NULL){
hashMapChained[probe] = malloc(sizeof(t_hashTableNode));
hashMapChained[probe]->value = value;
hashMapChained[probe]->next = NULL;
}else{
t_hashTableNode *hashTableNode = hashMapChained[probe];
while(hashTableNode->next!=NULL){
hashTableNode = hashTableNode->next;
}
hashTableNode->next = malloc(sizeof(t_hashTableNode));
hashTableNode->next->value = value;
hashTableNode->next->next = NULL;
}
}

int chainedHashSearch(int value){
t_hashTableNode *hashTableNode = hashMapChained[hash(value)];
while(hashTableNode!=NULL){
if(hashTableNode->value==value){
return TRUE;
}
hashTableNode = hashTableNode->next;
}
return FALSE;
}

Download: hash-map-chaining.c

BD-shell

April 21st, 2008 bodom_lx No comments

BD-shell (a.k.a. bdsh) is a tiny Unix shell written in C. It’s a project required for the Operating System Course at my University.
It is written using a clean coding style, following xP coding standard philosophy.
Version 1.0 is the release that satisfies all the course requirements!

Quick Jump:
Features
Download
License

Features

Cool Features

Lightweight
Implements real Job Control
Clear and understandable code, ideal for Academic (and personal) studies
Makes use of various system calls, signals, signal handlers, user input handling, data structures implementation
Free Software!

Cool Features NOT present (but may be in future)

No command history present
No command/filename auto completion
No wildcars
No command piping, just a single command can be launched at a time
Put everything else here.

These are the requirements asked by the teaching professor. The complete project description page is located at http://www.inf.unibz.it/~david/os/project.html
The shell must be able to do the following:

to read commands from standard input and execute them in a loop until a
built-in command exit is issued (we call these processes the foreground processes; there is always at most one of these at any particular time);
be able to redirect the standard input and output of commands by prefixing them with built-in commands in file and out file;
be able to terminate (involuntarily) the foreground process when user presses ^C and return back to the mini-shell;
be able to interrupt the foreground process temporarily, when user presses ^Z, returning to the mini-shell;
be able to execute any number of processes in background (i.e., in parallel with the foreground process), including in particular, the ability to start another process while a process has been temporarily suspended;
inform the user when the background process finishes or is
waiting for an input from the terminal;
be able to inform the user what commands are executing in the background by issuing the built-in command jobs, this should include information about the state of the process (i.e., suspended, background, waiting for input, etc.) and about what file(s) is the background process using for standard input and output);
be able to terminate involuntarily a background processes by issuing the built-in command kill job-number.
to be able to resume a process or to make a background process into the foreground process (i.e., the one that currently interacts with the terminal) by issuing the fg job-number command.

Download:

2008-09-14 – version 1.0.0.
- fixed synchronization bug in putJobBackground() that made not notify background processes requesting input (in some situations)
Known Bugs:
- Lots of! I consider bdsh-1.0.0 stable because it covers ALL requirements of the course and does them whell on various Unix systems. So it works, but commands like “in non_existent_file cat” won’t work and will crash it!
What will be next?
- I don’t know. I may consider a 1.0.1 release to fix future bugs. I may also think to add cool features to make the shell complete. I hope I will have the time for it. You can also do it by yourself and send me the code

2008-09-13 – version 1.0.0 Release Candidate 2.
Changes from beta 1 / release candidate 1
- removed gcc O3 flag from makefile
- lots of bugs fixed in functions operating on the list of jobs
- improvements in launchJob() when dealing with background commands
- bug in putJobBackground() that made the shell crash has been fixed
- killJob() now sends a SIGKILL
- bugs fixed in signalHandler_child()
- Code formatted using astyle (linux style)
- A couple of variables renamed
- Various usleep() removed
Known Bugs:
- So many =) This is a shell made for Academic purposes, not for production use!

2008-07-30 – version 1.0.0 beta1.
Characteristics:
- First beta release of the final version
- Every requirement has been covered
- Real Job-Control implemented
- About every function of bdsh.c has been rewritten
- New source directory layout, very clean
- Some documentation and makefile
- IMPORTANT! this has to be considered a bug hunting release! Please report me any bugs

2008-06-05 – version 0.7.1, corrects the linked list bug of version 0.7.0

2008-05-09 – version 0.7.0.
UPDATE 2008-06-05: there is a bug in the list handling, the shell crashes when using the standard input redirection. Please download version 0.7.1, which corrects the problem.
Characteristics:
- Cleaner code!
- Lots of bugs fixed!
- reads commands from standard input and executes them in a loop until a built-in command exit is issued
- redirects STDIN and STDOUT of commands by prefixing them with built-in commands in file and out file
- terminates (involuntarily) the foreground process when user presses ^C and return back to the shell
- executes any number of processes in background (i.e., in parallel with the foreground process)
- informs the user when the background process finishes
- informs the user what commands are executing in the background by issuing the built-in command jobs
- terminates involuntarily a background processes by issuing the built-in command kill job-number.

Due to a lots of compatibility issues with Gnu/Linux (the shell has been developed under Mac Os X), the final released has been delayed to mid-September. Sorry for this, I encountered so many problems the day before project presentation, that I decided to present it during the next exam session. I switched back to Gnu/Linux, too
~~Final release is scheduled on 2008-06-26, as the project deadline is 2008-06-25.~~ The release will
satisfy all the requirements, and as addition:
- Execution system totally rewritten (e.g. one single short function that handles everything)
- A Job Control will be implemented
- Processes in foreground will really be in foreground, there are a lot of things that we did not learn during the course, like tcsetpgrp()
- Some functions in utils.h will be deleted and optimized
- Cleaner and clearer code!

2008-04-21 – version 0.0.1
Characteristics:
- Modular code, divided in 3 files: bdsh.c, utils.h, headers.h
- Clean user input from a char buffer to an array of strings
- Built-in commands: exit (exits from the shell), cd (changes directory), in <filename> command (redirects STDIN of command from <filename>), out <filename> command (redirects STDOUT of command to <filename>)
- Makes use of fork() to read commands from standard input and execute them

License:

BD-shell is released under The Gnu GPL version 3! This is different from the license of the contents of the blog

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program. If not, see <http ://www.gnu.org/licenses/>>.

Insertion Sort on Linked Lists

April 9th, 2008 bodom_lx 1 comment

I’m pleased to publish this insertion sort implementation on single linked lists developed with my collegue Rigel.
It’s a nice experiment in asymptotic complexity of O(n^3). The high complexity is due to the necessity of retrieving the neighbours of the node handled, a difficult operation when using single linked lists.

Download: Insertion Sort on Single Linked Lists

OO Memory Management Model summary updated

April 6th, 2008 bodom_lx No comments

Today I wrote a new version of my summary posted here. The new version covers more topics, here is the updated list:

Memory portions assigned to a program (code area, heap / dynamic memory area), execution stack
How code is loaded in Java
The Activation Record (AR) and function calls
Abbrevations (AR, RV, RA, SP, N/E, @, ??, arb)
Examples on method calls and activation records usage
Declaraion vs. Definition of a variable, the scope of a variable, blocks
Scope Activation Record (SAR), Static Link (SL), the role of SL
The extent/lifetime of a variable
Dynamic memory allocation and handling
Dynamic vs. Static memory allocation
Dynamic memory scope and extent
Accessing dynamic memory
Classes and Objects in detail, object instantiation
Memory Management issues
Objects vs. Variables (definitions)
Methods of Objects
Class Attributes
The null value
Parameters (formal, actual), parameters passing (by reference, by value)
Constructors and Inline Initialization
Constructor’s call

Object Oriented Memory Management

March 19th, 2008 bodom_lx No comments

Major Update on 10th April 2009, inclusion of C++ programming language!
Updated on 18th April 2008, a complete example on stack and heap
Updated on 15th April 2008, new contents and new layout!
Updated on 6th April 2008, new contents!

The paper you can download from here is about a model for memory management during the execution of programs written in Java and C++.

It started on March, 2008 as a summary of the lecture notes of both the “Programming Project” and
“Software Engineering Project” courses held by professors of the CASE (Center for Applied Software Engineering) of the Free University of Bolzano – Bozen.

The first versions of this publication were only about Java memory management.
Subsequent revisions added information found on other sources. Unfortunately, the author forgot to
reference the sources on the document.

On March, 2009 the author began to add the information about C++ programming language. More
information from other sources were added, including their attribution.

The biggest source of this document is still the set of presentations of CASE.
The code snippets and their corresponding stack/heap diagrams are copied in full from those of the
slides.

The next major revision will contain original images (not belonging to CASE slides), as well as other code
snippets that I could find more clear than those of CASE.

If you find that this document contains information taken from one of your publications, please
contact the author, that is willing to either delete them from this document or to add an attribution to
your work.

Download the PDF of the summary

Table of Contents:

The model
Code load and execution
Activation Record (AR)
Contents of the Activation Record
Abbreviations for
Declaration vs. Definition
The scope of a variable
Extent of a Variable
Blocks
Scope Activation Record (SAR)
Example on SAR
Role of SLs
Dynamic Memory Allocation And Handling
Dynamic Vs. Static memory allocation
Dynamic Memory Scope and Extent
Accessing dynamic memory
Classes
Objects
Object instantiation
Objects in Memory (Java)
Objects in Memory (C++)
Memory Management issues (Java)
Memory Management issues (C++)
Methods
Methods (Java)
Methods (C++)
Attributes
The null value (Java)
The NULL value (C++)
Parameter
Parameter Passing (Java)
Example of parameters passing (Java)
Example of parameters passing (Java), continued
Parameter Passing (C++)
Example of parameters passing by value (C++)
Example of parameters passing by reference (C++)
Pointers vs. Parameters (C++)
Previous example using pointers (C++)
Constructor
Inline initialization
A constructor’s call (Java)
Class attributes
Example of class attributes (Jav)
Example of class attributes (C++)
Class Method
Example of Stack/Heap Diagrams in Java
Code
Stack Diagram
Heap Diagram

Memory portions assigned to a program (code area, heap / dynamic memory area), execution stack
How code is loaded in Java
The Activation Record (AR) and function calls
Abbrevations (AR, RV, RA, SP, N/E, @, ??, arb)
Examples on method calls and activation records usage
Declaraion vs. Definition of a variable, the scope of a variable, blocks
Scope Activation Record (SAR), Static Link (SL), the role of SL
The extent/lifetime of a variable
Dynamic memory allocation and handling
Dynamic vs. Static memory allocation
Dynamic memory scope and extent
Accessing dynamic memory
Classes and Objects in detail, object instantiation
Memory Management issues
Objects vs. Variables (definitions)
Methods of Objects
Class Attributes
The null value
Parameters (formal, actual), parameters passing (by reference, by value)
Constructors and Inline Initialization
Constructor’s call
Class attributes (static variables)
Class methods (static methods)
Complete Example of Stack/Heap Diagrams

Everything is integrated with simple examples.

Download the PDF of the summary

bodom_lx at task3 dot cc

Archive

La portabilità del codice esiste o no?

Related posts

Hash Maps with linear probing and separate chaining

Related posts

BD-shell

Features

Cool Features

Cool Features NOT present (but may be in future)

Download:

License:

Related posts

Insertion Sort on Linked Lists

Related posts

OO Memory Management Model summary updated

Related posts

Object Oriented Memory Management

Related posts

About

Recent Posts

Recent Comments

Meta

Categories

Tags

Twitter