Thread: data storage - struct or hash table

  1. #1
    Hamster without a wheel iain's Avatar
    Join Date
    Aug 2001
    Posts
    1,385

    data storage - struct or hash table

    I am writing a proxy server, an internal table will need to keep track of requests so incoming traffic can be dropped if it has not been requested and maintain connection state.

    I will need to store

    Originating Internal IP (unsigned long)
    Destination IP (unsigned long)
    Source port (uint)
    Destination ports (uint)

    I will need to store a lot of these in data records and will need to access them qucickly. Would it be more efficient to store them in a hash table or a struct?
    Or is tere a more suitable data type?

    thanks
    Last edited by iain; 02-03-2005 at 09:50 AM. Reason: Additional info
    Monday - what a way to spend a seventh of your life

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    A hash table of structs might be a good idea.
    If you understand what you're doing, you're not learning anything.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    How many data items do you need to hold ?
    What value(s) are used to lookup ?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Hamster without a wheel iain's Avatar
    Join Date
    Aug 2001
    Posts
    1,385

    Post

    How many data items do you need to hold ?
    - I can't say, it depends on the network load, theoretically it should be able to keep track of all current connections, the data being removed from the container when the session is completed.
    My intention is to dynamically allocate space to store each new record.


    What value(s) are used to lookup ?
    Lookups will be performed on potentially all of the values. Depending on the operation any of the values could potentially used as the lookup key, but i think that source port would be used most frequently.

    A hash table of structs
    is that even possible?
    Monday - what a way to spend a seventh of your life

  5. #5
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Sure it's possible. You can implement it as an array of linked lists. Or an array of an array of structs if you want to do it that way, but I recommend the array of linked lists.
    Last edited by itsme86; 02-03-2005 at 02:09 PM.
    If you understand what you're doing, you're not learning anything.

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >theoretically it should be able to keep track of all current connections
    If you're thinking of a hash table then you need at least a vague idea of the average number of connections. This is because dynamically sizing a hash table is a pain in the butt. You'll most likely end up using separate chaining, which is only effective if the array of linked lists is appropriately sized to begin with so that the lists are all short.

    >Lookups will be performed on potentially all of the values.
    To avoid lots of reorganizing, you're probably looking at four separate hash tables (of pointers to the original data). Each table will be hashed to a different field for lookup. The original data could be in one of the tables or in a separate data structure optimized for insertion and deletion of connections. Either way, you still have to touch all of the tables when adding or removing records.

    Alternatively, a balanced tree schema might be sufficient for your performance needs. That way you won't be constrained by the size of an array for hash tables.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. memory issue
    By t014y in forum C Programming
    Replies: 2
    Last Post: 02-21-2009, 12:37 AM
  2. Hash Table outputting incorrect number
    By Paul Skinner in forum C Programming
    Replies: 4
    Last Post: 11-20-2008, 06:19 AM
  3. Replies: 10
    Last Post: 05-18-2006, 11:23 PM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. Passing pointers between functions
    By heygirls_uk in forum C Programming
    Replies: 5
    Last Post: 01-09-2004, 06:58 PM