1

I want to implement queue on server side functions:

  1. store the packets in queue (copy them from recvfrom buffer)
  2. search the packets by id's and retrieve them for retransmission
  3. take the 2 packets with different id's and process them together
  4. delete packets with the same id
  5. delete all the packets from the queue when timer expires

I have reading a lot, but I'm not sure what is the best data structure to use for this problem, linked lists, hash tables? I don't have experience in this field to I need the advice for the most efficient algorithm

Thank you

Dipto
  • 2,720
  • 2
  • 22
  • 42
user3119422
  • 87
  • 3
  • 11

2 Answers2

1

For efficient data structure linked list is best choice .for example udp data structure in link list

/* The UDP data packet structure */

struct udp_data
{
   struct udp_data* u_next;
   short id;    /* id for this packet */
   void *   u_data;     /* packet data */

   //Add more field if you want
   ......................................
   .........................................

};

typedef struct udp_data *UDP_DATA;

And most important thing you must know linked list management.

Jayesh Bhoi
  • 24,694
  • 15
  • 58
  • 73
  • Jayeshbhoi don't you think that find operation is expensive in linked list's? If I want to find for example packet with id 50, you must go sequential through the whole list to find and grab the packet ...Is there any better solution? – user3119422 Jan 30 '14 at 12:39
  • Yes, traversal is the only method for searching the list but if you think memory point of view then linked list batter because it allocate memory dynamically.if max element known at design time.then go for same structure(exclude `struct udp_data* u_next`) using array(but memory allocated statically in array.) – Jayesh Bhoi Jan 30 '14 at 13:13
  • ok, now choice is yours whether go for `linked list` (consume less memory find operation is little slow) OR `structure array` (consume lots of memory but find operation fast). – Jayesh Bhoi Jan 30 '14 at 13:29
  • I will have a lot of find operations in my queue so I think that linked list are not the best solution...I'm not sure about arrays, I never have array of structures and I'm not sure how I will handle static memory allocation ...what about hash tables? do you had experience with them? – user3119422 Jan 30 '14 at 13:29
  • Retriving element in array and hash-table is generally similar but it hash-table take constant time.for more info which one is best please go to and other SO topic – Jayesh Bhoi Jan 30 '14 at 13:54
0

The best way to go with this kind of issue as far i know is to use a standard header far all packets with same header lenght then take header size data, from header know the packet length and take the packet length data from the pool, and repeat the same.

hope to find your answer.

for example

struct Common_header{
        float ver;
        int flag;
        int msg_type;
        int msg_len;    
};

struct Req_Cim_Nim_Snr{
        struct Common_header header;
        char master[30];
        char cpe[30];   
};

struct Req_Cim_Nim_Fwr{
        struct Common_header header;
        char fwr_link[200]; 
};

in both the request messages i have a struct header which contains the length of the message, so i take header first and take msg_len length number of bites to get the whole message.

about the datastructure, since its first in first out, linked list is good enough.

Trilok M
  • 681
  • 7
  • 21
  • Trilok M , I don't understand your exlpanaiton, for what you are using structures Req_Cim_Nim_Snr and Req_Cim_Nim_Fwr, how do you add packets in the queue, search them or delete them? I don't understand your data structure, in wich fashion should be implemented..? – user3119422 Jan 30 '14 at 12:41