?
Solved

structures containing thousands of entries

Posted on 2003-03-11
5
Medium Priority
?
159 Views
Last Modified: 2010-04-15
hi,

i am creating a web program which will need to hold user information in a struct. I've thought about creating an array of structs, but this has some limitations that I don't want.  I am looking for a way to do something similar to this:
typedef struct {
 int var1;
 int var2;
 char *arg;
} _users;
_users *users;

int main() {
   users = calloc(1024, sizeof(_users));
}

again, im looking for alternatives. linked lists wont work because then i'd have to search through the linked list everytime i look for a user, and the userlist will be HUGE, and there will be too much time going through the whole list. i'm aware of hte several ways i could improve linked lists, but not really feeling up to it. looking for something more like users[id] where id = 1-1024, etc.

feel free to post your suggestions.
thanks.
0
Comment
Question by:rulerr
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
5 Comments
 
LVL 6

Expert Comment

by:gj62
ID: 8115682
Not sure I understand - you are going to have to search through structs too (you can have a linked list of structs).

The nice think about linked lists is as you build them, you can keep it sorted on the fly, then bsearch it pretty easily.

I would recommend you consider a linked list of structs in sorted order...  If that's what you want, we can certainly provide the code to do it, it really isn't that much...
0
 
LVL 6

Expert Comment

by:gj62
ID: 8115690
By the way, thousands really isn't that many, especially for a struct of that size - now, if we were talking about millions, then we'd have to give it some thought...
0
 
LVL 5

Accepted Solution

by:
Kocil earned 225 total points
ID: 8115837
Use array of pointer to struct.

Looks like this in the memory

Array of *_user  
[0] -> [user 0]
[1] -> [user 1]
[2] -> [user 2]
[...]

You may have a big array of *user without wasting too much memory. You only malloc memory for _user data if needed.
You can sort and bsearch on the the array efficiently as usual;
 
typedef struct {
  int var1;
  int var2;
  char *arg;
} _user;

typedef struct {
  int number;
  int max;
  _user **users;   /* array of pointers to _user */
} _userlist;

int UserInit(_userlist* ul, int max)
{
  ul->number = 0;
  ul->users = malloc(sizeof(_user*));
  ul->max = max;
}

int UserAdd(_userlist* ul, _user* u)
{
  ul->number++;
  if (ul->number >= ul->max) realloc(ul->users, ul->max+10);
  ul->users[ul->number] = malloc(sizeof(_user));

  /* you may add feature to sort insert user here */
  *ul->users[ul->number] = *u;
}

/* compare user var1 */
int compvar1(_user* u1, _user* u2)
{
   int v1 = u1->var1;
   int v2 = u1->var2;
   return v1 == v2 ? 0 : (v1 < v2 ? -1 : 1);
}

_user* UserSearch(_userlist* ul, _user* key)
{
  return bsearch(key, ul->users, ul->number,
    sizeof(_user*), comparevar1);  
}
 
int main() {
  _userlist ulist;
  _user user = {....};

  UserInit(&ulist, 1024);
  UserAdd(&ulist, &user);
   ...

  found = UserSearch(&ulist, &user) != NULL;
}
0
 

Author Comment

by:rulerr
ID: 8115878
Thanks.  I haven't thought of something like this, and it's exactly what I will implement. Sorry for not accepting previous answers, but this one suits me best.

again, thanks a lot.
0
 

Expert Comment

by:Twinkt73
ID: 9696506
Just out of curiousity:
Can you run your code with a C++ compiler? In that case, you can use the STL (Standard Template Library). The STL is pure heaven for these kind of issues. Totally flexible. You can either store the struct or a pointer to the struct in a number of different datastructures. For instance, when you need random access, traversing the complete linked list every time to find your item is slooow. In STL you would simply use a Map, or a Hash_map if you have many items and performing string-based look-ups. There is a whole bunch more.

I know the question is closed but I wouldn't want anybody to have to live without the STL :) STLPort.org has complete libs that work with about any compiler.
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.
Suggested Courses

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question