radixsort.c
/**************************************************************************************/
/* Radix Sort of integers numbers using polymorphic linked lists. */
/**************************************************************************************/
#include <stdio.h>
#include "list.h"
#include <stdlib.h>
#include "numberinterface.h"
#include <math.h>
void static refill( int A[] , list Bins[] ) ;
int static getdigit( int number, int position ) ;
int main( int argc, char *argv[] ) {
int *A ;
list Bins[10] ;
int i, j, k, n, digit ;
n = atoi( argv[1] ) ;
A = (int *)malloc( sizeof( int) * n ) ;
for ( i = 0 ; i < n ; i++ ) { A[i] = rand() % 10000; }
printf("\n ");
for ( i = 0 ; i < 20 ; i++ ) printf(" %d ", A[i] );
printf("\n");
for ( i = 0 ; i < 10 ; i++ ) init_list( &Bins[i] ) ;
for ( i = 1 ; i <= 4 ; i++ ) {
printf("Pass %d: ", i ) ;
for ( j = 0 ; j < n ; j++ ) {
digit = getdigit( A[j] , i-1 ) ;
appendanumber( &Bins[digit], A[j] ) ;
}
refill( A, Bins ) ;
for ( k = 0 ; k < 20 ; k++ ) printf(" %d ", A[k] ); printf("\n");
}
return 0 ;
}
static int getdigit( int num, int position ) {
int digit = num / (int)pow(10,position-1) % 10 ;
return digit ;
}
static void refill( int A[], list Bins[] ) {
int i ;
int j = 0 ;
int n ;
for( i = 0 ; i < 10 ; i++ ){
while( !empty_list( Bins[i] ) ) {
getnextnumber(&Bins[i] , &n) ;
A[j] = n ;
j++ ;
}
}
}numberinterface.h
#ifndef _numberinterface
#define _numberinterface
#include "list.h"
extern status appendanumber( list *p_L , int n ) ;
extern status getnextnumber( list *p_L , int *p_n ) ;
#endifnumberinterface.c
#include <stdlib.h>
#include "numberinterface.h"
#include "globals.h"
#include "list.h"
#include <stdio.h>
status appendanumber( list *p_L , int n ){
int *t_ptr = (int *)malloc(sizeof(int) ) ;
if( t_ptr == NULL ) return ERROR ;
*t_ptr = n ;
if( append(p_L,(generic_ptr)t_ptr) == ERROR ) {free(t_ptr ) ; return ERROR ; }
return OK ;
}
status getnextnumber( list *p_L , int *p_n ){
int *p_temp ;
if(delete(p_L, (generic_ptr *)&p_temp ) == ERROR ) return ERROR ;
*p_n = *p_temp ;
free(p_temp) ;
return OK ;
}list.h
#ifndef _list
#define _list
#include "globals.h"
typedef struct node node, *list;
struct node { generic_ptr datapointer; list next; };
extern status allocate_node( list *p_L, generic_ptr data ) ;
extern void free_node( list *p_L ) ;
extern status init_list( list *p_L ) ;
extern bool empty_list( list L ) ;
extern status insert( list *p_L, generic_ptr data ) ;
extern status append( list *p_L, generic_ptr data ) ;
extern status delete( list *p_L, generic_ptr *p_data ) ;
extern status delete_node( list *p_L, list node ) ;
extern status traverse( list L, status (*p_func_f) () );
extern status find_key( list L, generic_ptr key, int(*p_cmp_f) (), list *p_keynode );
extern list list_iterator( list L, list lastreturn );
extern void destroy(list *p_L, void (*p_func_f)() );
extern bool set_equal( list L1 , list L2 , int (*p_cmp_f)() ) ;
#endiflist.c
/*****************************************************************************/
/* list.c */
/* */
/*****************************************************************************/
#include <stdlib.h>
#include "globals.h"
#include "list.h"
status allocate_node( list *p_L , generic_ptr data) {
list L = (list) malloc(sizeof(node));
if (L == NULL) return ERROR;
*p_L = L;
DATA(L) = data;
NEXT(L) = NULL;
return OK;
}
void free_node(list *p_L) {
free(*p_L);
*p_L = NULL;
}
status init_list( list *p_L) {
*p_L = NULL;
return OK;
}
bool empty_list(list L) {
return (L == NULL ) ? TRUE : FALSE;
}
status insert( list *p_L,generic_ptr data ) {
list L;
if(allocate_node(&L, data) == ERROR) return ERROR;
NEXT(L) = *p_L;
*p_L = L;
return OK;
}
status append(list *p_L, generic_ptr data) {
list L, tmplist;
if(allocate_node(&L, data) == ERROR) return ERROR;
if(empty_list(*p_L) == TRUE) *p_L = L;
else {
for(tmplist = *p_L; NEXT(tmplist) != NULL; tmplist=NEXT(tmplist) );
NEXT(tmplist) = L;
}
return OK;
}
status delete(list *p_L, generic_ptr *p_data) {
if(empty_list(*p_L)) return ERROR;
*p_data = DATA(*p_L);
return delete_node(p_L, * p_L);
}
status delete_node( list *p_L, list node) {
if(empty_list(*p_L) == TRUE) return ERROR;
if(*p_L == node) *p_L = NEXT(*p_L);
else {
list L;
for(L = *p_L; L != NULL && NEXT(L) != node; L = NEXT(L));
if (L == NULL) return ERROR;
else NEXT(L) = NEXT(node);
}
free_node(&node);
return OK;
}
status traverse( list L, status(*p_func_f) () ) {
if(empty_list(L)) return OK;
if( (*p_func_f)(DATA(L)) == ERROR ) return ERROR;
else
return traverse(NEXT(L), p_func_f);
}
status find_key( list L, generic_ptr key, int(*p_cmp_f)(), list *p_keynode ) {
list curr = NULL;
while( ( curr = list_iterator(L, curr)) != NULL) {
if ( (*p_cmp_f) (key, DATA(curr) ) == 0 ) {
*p_keynode = curr;
return OK;
}
}
return ERROR;
}
list list_iterator(list L, list lastreturn ) {
return (lastreturn == NULL) ? L : NEXT(lastreturn);
}
void destroy( list *p_L, void (*p_func_f)() ) {
if (empty_list(*p_L) == FALSE) {
destroy( &NEXT(*p_L), p_func_f );
if (p_func_f != NULL)
(*p_func_f)(DATA(*p_L));
free_node(p_L);
}
}
bool equal(list L1 , list L2 , int (*p_cmp_f)() ){
while(L1 != NULL && L2 != NULL ){
if( (*p_cmp_f)(L1->datapointer,L2->datapointer ) == -1)
return FALSE;
else
equal(L1->next,L2->next,p_cmp_f) ;
}
return TRUE;
}
bool set_equal( list L1 , list L2 , int (*p_cmp_f)() ){
while(L1 != NULL && L2 != NULL ){
if( (*p_cmp_f)(L1->datapointer,L2->datapointer ) == -1)
return FALSE;
else
equal(L1->next,L2->next,p_cmp_f) ;
}
return TRUE;
}globals.h
#ifndef _globals
#define _globals
#define NEXT(L) ( (L) -> next )
#define DATA(T) ( (T) -> datapointer )
#define LEFT(T) ( (T) -> left )
#define RIGHT(T) ( (T) -> right )
typedef enum { OK, ERROR } status ;
typedef enum { FALSE=0 , TRUE=1 } bool ;
typedef void *generic_ptr ;
#endifI compiled it like this : gcc -o radix radixsort.c list.c numberinterface.c -lm
and after I ran it it printed this out:
./radix 5
9383 886 2777 6915 7793 135145 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Floating point exception
so i decided to compile it with the -g option and run it on gdb
and this is what i got:
(gdb) run
Starting program: ........................../radixsort/radix
Program received signal SIGSEGV, Segmentation fault.
0x0054becc in ____strtol_l_internal () from /lib/tls/libc.so.6
(gdb)
