Hash Table with Simple record in files

This is a discussion on Hash Table with Simple record in files within the C Programming forums, part of the General Programming Boards category; Code: # i n c l u d e < s t d i o . h > # i ...

  1. #61
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    
    #define ACCOUNTS 300000UL
    #define BUCKETS 1000
    
    struct holding
    {
        struct holding *next;
        char holdingName[ BUFSIZ ]; /* this should be some ID# instead of a name */
        unsigned long shares;
    };
    struct account
    {
        unsigned long accountNumber;
        long balance;
        struct holding *holdings;
    };
    struct accountTable
    {
        struct accountTable *next;
        struct account *this;
    };
    
    struct account *find( struct accountTable **at, unsigned long accountNumber )
    {
        struct accountTable *bucket = NULL;
        struct account *found = NULL;
        for( bucket = at[ accountNumber % BUCKETS ];
             bucket && bucket->this && bucket->this->accountNumber != accountNumber;
             bucket = bucket->next )
             ;
        if( bucket )
            found = bucket->this;
    
        return found;
    }
    
    void freeholdings( struct account *a )
    {
        if( a )
        {
            struct holding *h = a->holdings;
            while( h )
            {
                struct holding *n = h->next;
                free( h );
                h = n;
            }
        }
    }
    
    void freeaccounts( struct accountTable *t )
    {
        if( t )
        {
            freeaccounts( t->next );
            freeholdings( t->this );
            free( t );
        }
    }
    
    void freebuckets( struct accountTable **all )
    {
        unsigned long x;
        for( x = 0; x < BUCKETS; x++ )
            freeaccounts( all[ x ] );
    }
    
    int main( void )
    {
        unsigned long totalAccounts = ACCOUNTS, anAccount = 0;
        struct accountTable *allAccounts[ BUCKETS ] = { NULL };
        
        for( anAccount = 0; anAccount < totalAccounts; anAccount++ )
        {
            struct accountTable *nte = malloc( sizeof *nte );
            if( nte )
            {
                nte->this = malloc( sizeof *(nte->this) );
                if( nte->this )
                {
                    nte->this->accountNumber = anAccount;
                    nte->this->balance = 0;
                    nte->this->holdings = NULL;
                }
                else
                {
                    printf( "Buy a better server.\n" );
                    exit( EXIT_FAILURE );
                }
                nte->next = allAccounts[ anAccount % BUCKETS ];
                allAccounts[ anAccount % BUCKETS ] = nte;
            }
            else
            {
                printf( "Buy a better server.\n" );
                exit( EXIT_FAILURE );
            }
        }
    
        for( anAccount = 0; anAccount < totalAccounts; anAccount++ )
        {
            unsigned long randomAccount = (rand() % ACCOUNTS);
            struct account *an = NULL;
            
            an = find( allAccounts, randomAccount );
            if( an )
            {
                struct holding *nh = malloc( sizeof *nh );
                if( nh )
                {
                    /* make a random account name */
                    nh->holdingName[ 0 ] = 'A' + (rand() % 26);
                    nh->holdingName[ 1 ] = 'A' + (rand() % 26);
                    nh->holdingName[ 2 ] = 'A' + (rand() % 26);
                    nh->holdingName[ 3 ] = 'A' + (rand() % 26);
                    nh->holdingName[ 4 ] = '\0';
                    
                    nh->shares = 1 + (random() % 100);
                    an->balance += nh->shares;
                    
                    nh->next = an->holdings;
                    an->holdings = nh;
                }
                else
                {
                    printf( "Buy a better server.\n" );
                    exit( EXIT_FAILURE );
                } }
            else
            {
                printf( "Account #%lu not found.\n", randomAccount );
            }
        }
    
        printf( "Congratulations, you have %lu accouns active.\n", totalAccounts );
        
        anAccount = 0;
        while( anAccount < ACCOUNTS )
        {
            printf( "Enter an account number, or a number >= %lu to exit: ", ACCOUNTS );
            if( scanf( " %lu", &anAccount ) == 1 && anAccount < ACCOUNTS )
            {
                struct account *an = NULL;
                an = find( allAccounts, anAccount );
                if( an )
                {
                    struct holding *nh = an->holdings;
                    printf( "\nAccount %lu has ", an->accountNumber );
                    if( nh )
                    {
                        printf( "%lu shares in the following:\n", an->balance );
                        while( nh )
                        {
                            printf( "\t%s, %lu shares\n", nh->holdingName, nh->shares );
                            nh = nh->next;
                        }
                    }
                    else
                    {
                        printf( "no holdings.\n" );
                    }
                }
            }
            else
            if( anAccount < ACCOUNTS )
            {
                printf( "Stop typing stupid stuff.\n" );
                exit( EXIT_FAILURE );
            }
        }
        
        freebuckets( allAccounts );
        
        return 0;
    }
    There, 300000 accounts. That should keep you busy for a while.


    Quzah.
    Hope is the first step on the road to disappointment.

  2. #62
    Registered User
    Join Date
    Oct 2011
    Location
    India
    Posts
    53
    Quote Originally Posted by CommonTater View Post
    That's very nice of you but we don't do that... Online is online... private is private... the two never meet.
    OK. If you would like to get to know us, you are welcome! We have met folks who helped us in the past.

    Quote Originally Posted by CommonTater View Post
    ROFL... not even bloody close... a million transactions a day?
    You're probably talking about 15 or more Xeon or Itanium blade servers running 64 bit OS, with gobs of memory, redundent raid arrays, continuous backup, routing software, load balancing and all the horrific complexity that comes with it.
    You're talking about --> THIS
    My god man... you need to stop asking for advice on public forums and hire a proper consultant... Really... I don't think you have the first clue how big a job this is. The principles I've outlined will be at the core of it... but with that much traffic, you aren't going to cobble together some quicky C proggys and cross your fingers.
    The million transactions a day would be the ultimate goal, sir. We expect to be able to handle that much traffic in about, say, 5 years. Not necessarily immediately.
    Yes, we intend to write all the stuff necessary to reach a million trans processing power. We have a long road ahead of us. Definitely not expecting any quickies here at all, no.
    Yes, crunching a million transactions is not going to be easy. No, of course not, we are not expecting to accomplish anything at all over night.


    I sleep well enough... I've never had a data loss --ever-- because I make sure the software is running on a proper server, with mirrored drives and daily backup... The worst case data loss in any of my systems will be one business day... which these systems can easily tolerate. If these were handling even a small fraction of a million transactions a day, I'd be running double backups and a whole lot better hardware...
    It time to drop this... you need to hire a consultant and get hooked up with a software house capable of such a job.




    Well, I am personally not in favor of keeping one big file with 18GB size!
    Yes, the hardware and other requirements if I am keeping all the transactions in a single file would be heavy. But, individual files with many processors divvying up work load ought to work out OK. Again, I am not trivializing anything here. As I said earlier, we have a long road ahead of us.
    My professors at the very beginning of our course warned us: “If you ever write in your papers that you would hire a consultant to analyze/handle any issue, I would fail you and ask you to leave my class”. Sir, we ARE the software house! We will learn and progress every single day. Asking for help in a Public forum is filling up a hole here and there and never to get the whole stuff! If someone has the whole stuff, they would be doing this business already.
    Your feedback and help is very much appreciated by me and my colleagues.


    Last edited by infantheartlyje; 10-12-2011 at 07:50 AM.

  3. #63
    Registered User
    Join Date
    Oct 2011
    Location
    India
    Posts
    53
    Quote Originally Posted by quzah View Post
    I don't know how you can possibly think manipulating it on disk is going to be faster than in memory.


    Quzah.
    Memory based “processing/sorting” is “always” going to be fast. I agree. But, I am not asking for “processing” in disk at all. Finding a clever way of arranging FAT in such a way that I do not find myself processing/sorting the file every time is what I am after. (Again, I am saying FAT just to point out some kind of manipulation in the file allocation tables, whatever they might be in the current environment).

    I do agree that the answer is not readily apparent. It could very well be that it can not be done. But, haven't things been done by new inventions which were impossible to do in the past?
    There was a time when all agreed Einstein's proposition that speed of light was the fastest. In recent times there were some “preliminary” reports that other faster things were observed in CERN. So, nothing wrong in trying, I suppose!

  4. #64
    Registered User
    Join Date
    Oct 2011
    Location
    India
    Posts
    53
    Quote Originally Posted by quzah View Post
    There, 300000 accounts. That should keep you busy for a while.
    Quzah.
    Thank you. You shared lots of code with us. We appreciate your help. Thanks again!

  5. #65
    Registered User
    Join Date
    Oct 2011
    Location
    India
    Posts
    53
    Quote Originally Posted by quzah View Post

    Hope is the first step on the road to disappointment.

    Quzah.
    We may fail 99 times, Quzah! But, the one triumph resulting from our hard work and tenacity might very well earn us a Nobel!
    You have been helpful to us so very much; kind of surprising why you keep this as your quote.

  6. #66
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by infantheartlyje View Post
    Memory based “processing/sorting” is “always” going to be fast. I agree. But, I am not asking for “processing” in disk at all. Finding a clever way of arranging FAT in such a way that I do not find myself processing/sorting the file every time is what I am after. (Again, I am saying FAT just to point out some kind of manipulation in the file allocation tables, whatever they might be in the current environment).
    Ok... lose this idea right now ... software should not be aware of the hard disk's filing system. This for the simple reason that updates and revisions are likely to change it... then your software is totally cooked. Don't even think about writing software that is even marginally aware of the underlying hardware.

    I do agree that the answer is not readily apparent. It could very well be that it can not be done.
    It's not a question of can or can't --because it can-- the active question here is exactly how stupid would it be to manipulate the hardware for the sake of one piece of software?

    And the answer is "massively stupid".

    One automatic update to the OS's filing systems and your software --all of it-- simply stops working...

    Old wisdom: "Just because you CAN do something does not mean you SHOULD".

    At the risk of stepping right in it... how long you guys been writing software?
    Last edited by CommonTater; 10-12-2011 at 10:06 AM.

  7. #67
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by infantheartlyje View Post
    But, the one triumph resulting from our hard work and tenacity might very well earn us a Nobel!
    I got one of those in my Happy Meal the other day. They give those things out to anyone now.


    Quzah.
    Hope is the first step on the road to disappointment.

  8. #68
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by infantheartlyje View Post
    [FONT=Univers, sans-serif]We may fail 99 times, Quzah! But, the one triumph resulting from our hard work and tenacity might very well earn us a Nobel
    Trust me... there are thousands of people with decades more experience. These days the very best a programmer can hope for is acceptance by his peers.

  9. #69
    Registered User
    Join Date
    Oct 2011
    Location
    India
    Posts
    53
    Quote Originally Posted by CommonTater View Post

    Ok... lose this idea right now ... software should not be aware of the hard disk's filing system. This for the simple reason that updates and revisions are likely to change it... then your software is totally cooked. Don't even think about writing software that is even marginally aware of the underlying hardware.
    I agree. App should do what it is supposed to and leave the OS to handle what it does and let the firmware handle the h/w.
    Looks like if my idea were to be implemented, there would have to be coordination between the application, OS and firmware/hardware folks to get this done. And, I do not think it would happen.

    Quote Originally Posted by CommonTater View Post

    It's not a question of can or can't --because it can-- the active question here is exactly how stupid would it be to manipulate the hardware for the sake of one piece of software?
    Let us consider sorting your 18GB file. If manipulating hardware might be worth the while to handle such large files, why not? Again, my point is that for specialized/targetted applications, this might be useful. As you said it does sound stupid in our case. I have heard that in the military where processing time is of the essence, there are instances of hardware manipulation. Well, we are not obviously as rich as Uncle Sam. Who knows? Just as creating a network protocol by DARPA came out to civilian use as the Internet, what I am suggesting might one day come to the public domain, if it exists.


    Quote Originally Posted by CommonTater View Post

    Old wisdom: "Just because you CAN do something does not mean you SHOULD".
    What we should and should not do changes over time, sir. There was a time when learning to drive entailed checking radiator water level, oil level, changing a flat, etc. before anyone let you take the wheel. Now, my wife wonders why she must bother dirtying her fingers when AAA is around. What I was suggesting might not be worth our time at this nascent state of our co. But, I might come around to it in the future. Just imagine a hardware based sorting solution!



    Quote Originally Posted by CommonTater View Post

    At the risk of stepping right in it... how long you guys been writing software?

    From the late 80's. That may not be much compared to what you might have. Does not mean we would give up easily.

  10. #70
    Registered User
    Join Date
    Oct 2011
    Location
    India
    Posts
    53
    Quote Originally Posted by CommonTater View Post
    Trust me... there are thousands of people with decades more experience. These days the very best a programmer can hope for is acceptance by his peers.
    I NEVER discount experience! But, if we accept experience is everything, if status quo would prevail, if something is not there, there is a reason why it is not there, then we wouldn't have many things in life, for e.g., the pc that you and I are using. Americans, I think, are a bit more independent and there is not much harm in believing there are separate lanes in the road for all of us to tread in life! Acceptance by others is nice but, ain't the end of it all.

  11. #71
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by infantheartlyje View Post
    Let us consider sorting your 18GB file.
    That's why we create index files... so that we don't have to sort the big one. Instead we sort the indexes... and With one index file at about 800megs, the system can do a copy-insertion sort of hundreds of new items in less than 3 minutes. How is that possible? It's possible because I never have to sort the whole file, I simply copy the file inserting out of order records as I go.

    If manipulating hardware might be worth the while to handle such large files, why not?
    See above... No it's not worth it...


    What we should and should not do changes over time, sir. There was a time when learning to drive entailed checking radiator water level, oil level, changing a flat, etc.
    And it still does for anyone who doesn't want to end up stranded in the middle of noplace.

  12. #72
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,866
    I do love these discussions, however why bother with someone who is still dealing with DOS ideals? Seriously, let's move this to GD and argue about the world being flat(mind you the perversion of the ideals is to the point that one thinks DOS idealogy allows for the discussion of a 18GB file). IMHO, sometimes it just isn't worth it..........
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  13. #73
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,866
    Quote Originally Posted by infantheartlyje View Post
    You have been helpful to us so very much; kind of surprising why you keep this as your quote.
    Your argument is why he has that quote.....
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  14. #74
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by AndrewHunter View Post
    I do love these discussions, however why bother with someone who is still dealing with DOS ideals? Seriously, let's move this to GD and argue about the world being flat(mind you the perversion of the ideals is to the point that one thinks DOS idealogy allows for the discussion of a 18GB file). IMHO, sometimes it just isn't worth it..........
    20gb files aren't that uncommon anymore... you can suck almost that much off a BluRay disk when making uncompressed AVIs...

    In a world with 8gb being minimal memory for even a lightweight server, 2.5terabyte drives with mirrors being considered bare minimum storage, 18gb is practically nothing... not even 1% of the disk!

    Fat32 would pee it's pants if it saw some of the stuff we now do as normal.

    Progress is a wonderful thing.

  15. #75
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,866
    You are correct, my point (I guess poorly made) was the futility in arguing modern software architecture to someone clearly stuck in a DOS mode concept that utilized modern ideals; a simple joke.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

Page 5 of 6 FirstFirst 123456 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. more serious hash table
    By Aisthesis in forum C++ Programming
    Replies: 9
    Last Post: 09-22-2010, 11:06 PM
  2. Hash Table
    By mrsirpoopsalot in forum C++ Programming
    Replies: 11
    Last Post: 11-14-2009, 08:10 PM
  3. hash table
    By mexx in forum C++ Programming
    Replies: 0
    Last Post: 06-30-2009, 12:23 PM
  4. Hash Table
    By Cpro in forum C++ Programming
    Replies: 3
    Last Post: 03-20-2008, 02:14 PM
  5. Errors in a simple hash table class.
    By TheSquid in forum C++ Programming
    Replies: 4
    Last Post: 02-23-2005, 03:49 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21