[MUD-Dev] Re: Variable-sized structures in C (was: Naming and Directories)

[T. Alexander Popiel]

>Date: Fri, 19 Mar 1999 14:17:41 +0100
>From: Ola Fosheim =?iso-8859-1?Q?Gr=F8stad?= <olag at ifi.uio.no>
>To: mud-dev at kanga.nu
>Subject: Re: [MUD-Dev] Naming and Directories?
>Reply-To: mud-dev at kanga.nu

>Or more memory efficient:
>
>struct node {
>  object *obj; 
>  node *l,*r;
>  const char key[1];
>};
>
>node *new_node(char *s){
>  node *n = 0;
>  const char *k=n->key;
>
>  // Ugly and not fully portable? An option would be to declare
>  // key[4] and use sizeof(node)-3+strlen(s)
>
>  size_t keyoffset=*(size_t*)(void*)&k;
>  size_t keysize = strlen(s);
>
>  void *n = calloc(1, keyoffset + keysize + 1);  
>  assert(n);
>  memcpy(((char*)n)+keyoffset,s,keysize + 1);
>  return (node*)n;
>}

As suspected, this is not fully portable.  (It also won't compile
due to redeclaration of n, but that's minor.)  The "proper" way
to do it is:

struct node {
  object *obj; 
  node *l,*r;
  const char key[MAX_KEY_BUFFER_SIZE];
};

node *new_node(char *s){
  node *n;
  size_t keysize = strlen(s);

  /* May not allocate larger than structure definition */
  assert(keysize < MAX_KEY_BUFFER_SIZE);

  n = (node *)malloc(sizeof(*n) - sizeof(n->key) + keysize + 1);  
  assert(n);
  memcpy((char *)n->key, s, keysize + 1);
  return n;
}

This approach eliminates nasty pointer math, prevents problems
caused by allocating larger than the struct definition (which
can blow up on segmented architectures), and has only the two
requisite casts (one for the malloc result, one to prevent a
const/non-const mismatch on the memcpy).  As far as I know,
it is strictly ISO 9899:1990 compliant.

ObMUD: I have used a very similar approach for a string table
implementation in PennMUSH (not released yet, but I can give the
code to any who want it).  The string table is used for attribute
names on the objects, to eliminate duplication of the same name
on multiple objects through shared storage of the name.  This
has yielded 50% storage reduction over naive duplication and
30% storage reduction over duplicating all but a known set of
common names (the current policy in the server) in tests using
the pre-closing DuneMUSH database.  (Of course, the overall
memory usage only went down a few percent, because the names
are generally smaller than the contents, but even 5% on 40 meg
is nice.)

- Alex



_______________________________________________
MUD-Dev maillist  -  MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev