Back to index

glibc  2.9
Classes | Functions | Variables
strtab.c File Reference
#include <assert.h>
#include <inttypes.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/cdefs.h>
#include <sys/param.h>

Go to the source code of this file.

Classes

struct  Strent
struct  memoryblock
struct  Strtab

Functions

void * xmalloc (size_t n) __attribute_malloc__
struct Strtabstrtabinit (void)
void strtabfree (struct Strtab *st)
struct Strentstrtabadd (struct Strtab *st, const char *str, size_t len)
void * strtabfinalize (struct Strtab *st, size_t *size)
size_t strtaboffset (struct Strent *se)
static void morememory (struct Strtab *st, size_t len)
static struct Strentnewstring (struct Strtab *st, const char *str, size_t len)
static struct Strent ** searchstring (struct Strent **sep, struct Strent *newstr)
static void copystrings (struct Strent *nodep, char **freep, size_t *offsetp)

Variables

static size_t ps

Class Documentation

struct Strent

Definition at line 33 of file strtab.c.

Collaboration diagram for Strent:
Class Members
struct Strent * left
size_t len
struct Strent * next
size_t offset
char reverse
struct Strent * right
const char * string
struct memoryblock

Definition at line 45 of file strtab.c.

Collaboration diagram for memoryblock:
Class Members
char memory
struct memoryblock * next
struct Strtab

Definition at line 52 of file strtab.c.

Collaboration diagram for Strtab:
Class Members
char * backp
size_t left
struct memoryblock * memory
struct Strent * root
size_t total

Function Documentation

static void copystrings ( struct Strent nodep,
char **  freep,
size_t offsetp 
) [static]

Definition at line 287 of file strtab.c.

{
  struct Strent *subs;

  if (nodep->left != NULL)
    copystrings (nodep->left, freep, offsetp);

  /* Process the current node.  */
  nodep->offset = *offsetp;
  *freep = (char *) mempcpy (*freep, nodep->string, nodep->len);
  *offsetp += nodep->len;

  for (subs = nodep->next; subs != NULL; subs = subs->next)
    {
      assert (subs->len < nodep->len);
      subs->offset = nodep->offset + nodep->len - subs->len;
    }

  if (nodep->right != NULL)
    copystrings (nodep->right, freep, offsetp);
}

Here is the caller graph for this function:

static void morememory ( struct Strtab st,
size_t  len 
) [static]

Definition at line 112 of file strtab.c.

{
  struct memoryblock *newmem;

  if (len < ps)
    len = ps;
  newmem = (struct memoryblock *) malloc (len);
  if (newmem == NULL)
    abort ();

  newmem->next = st->memory;
  st->memory = newmem;
  st->backp = newmem->memory;
  st->left = len - offsetof (struct memoryblock, memory);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct Strent* newstring ( struct Strtab st,
const char *  str,
size_t  len 
) [static, read]

Definition at line 146 of file strtab.c.

{
  struct Strent *newstr;
  size_t align;
  int i;

  /* Compute the amount of padding needed to make the structure aligned.  */
  align = ((__alignof__ (struct Strent)
           - (((uintptr_t) st->backp)
              & (__alignof__ (struct Strent) - 1)))
          & (__alignof__ (struct Strent) - 1));

  /* Make sure there is enough room in the memory block.  */
  if (st->left < align + sizeof (struct Strent) + len)
    {
      morememory (st, sizeof (struct Strent) + len);
      align = 0;
    }

  /* Create the reserved string.  */
  newstr = (struct Strent *) (st->backp + align);
  newstr->string = str;
  newstr->len = len;
  newstr->next = NULL;
  newstr->left = NULL;
  newstr->right = NULL;
  newstr->offset = 0;
  for (i = len - 2; i >= 0; --i)
    newstr->reverse[i] = str[len - 2 - i];
  newstr->reverse[len - 1] = '\0';
  st->backp += align + sizeof (struct Strent) + len;
  st->left -= align + sizeof (struct Strent) + len;

  return newstr;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct Strent** searchstring ( struct Strent **  sep,
struct Strent newstr 
) [static, read]

Definition at line 187 of file strtab.c.

{
  int cmpres;

  /* More strings?  */
  if (*sep == NULL)
    {
      *sep = newstr;
      return sep;
    }

  /* Compare the strings.  */
  cmpres = memcmp ((*sep)->reverse, newstr->reverse,
                 MIN ((*sep)->len, newstr->len) - 1);
  if (cmpres == 0)
    /* We found a matching string.  */
    return sep;
  else if (cmpres > 0)
    return searchstring (&(*sep)->left, newstr);
  else
    return searchstring (&(*sep)->right, newstr);
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct Strent* strtabadd ( struct Strtab st,
const char *  str,
size_t  len 
) [read]

Definition at line 213 of file strtab.c.

{
  struct Strent *newstr;
  struct Strent **sep;

  /* Compute the string length if the caller doesn't know it.  */
  if (len == 0)
    len = strlen (str) + 1;

  /* Make sure all "" strings get offset 0.  */
  if (len == 1)
    return &st->null;

  /* Allocate memory for the new string and its associated information.  */
  newstr = newstring (st, str, len);

  /* Search in the array for the place to insert the string.  If there
     is no string with matching prefix and no string with matching
     leading substring, create a new entry.  */
  sep = searchstring (&st->root, newstr);
  if (*sep != newstr)
    {
      /* This is not the same entry.  This means we have a prefix match.  */
      if ((*sep)->len > newstr->len)
       {
         struct Strent *subs;

         for (subs = (*sep)->next; subs; subs = subs->next)
           if (subs->len == newstr->len)
             {
              /* We have an exact match with a substring.  Free the memory
                 we allocated.  */
              st->left += st->backp - (char *) newstr;
              st->backp = (char *) newstr;

              return subs;
             }

         /* We have a new substring.  This means we don't need the reverse
            string of this entry anymore.  */
         st->backp -= newstr->len;
         st->left += newstr->len;

         newstr->next = (*sep)->next;
         (*sep)->next = newstr;
       }
      else if ((*sep)->len != newstr->len)
       {
         /* When we get here it means that the string we are about to
            add has a common prefix with a string we already have but
            it is longer.  In this case we have to put it first.  */
         st->total += newstr->len - (*sep)->len;
         newstr->next = *sep;
         newstr->left = (*sep)->left;
         newstr->right = (*sep)->right;
         *sep = newstr;
       }
      else
       {
         /* We have an exact match.  Free the memory we allocated.  */
         st->left += st->backp - (char *) newstr;
         st->backp = (char *) newstr;

         newstr = *sep;
       }
    }
  else
    st->total += newstr->len;

  return newstr;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* strtabfinalize ( struct Strtab st,
size_t size 
)

Definition at line 311 of file strtab.c.

{
  size_t copylen;
  char *endp;
  char *retval;

  /* Fill in the information.  */
  endp = retval = (char *) xmalloc (st->total + 1);

  /* Always put an empty string at the beginning so that a zero offset
     can mean error.  */
  *endp++ = '\0';

  /* Now run through the tree and add all the string while also updating
     the offset members of the elfstrent records.  */
  copylen = 1;
  copystrings (st->root, &endp, &copylen);
  assert (copylen == st->total + 1);
  assert (endp == retval + st->total + 1);
  *size = copylen;

  return retval;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void strtabfree ( struct Strtab st)

Definition at line 130 of file strtab.c.

{
  struct memoryblock *mb = st->memory;

  while (mb != NULL)
    {
      void *old = mb;
      mb = mb->next;
      free (old);
    }

  free (st);
}
struct Strtab* strtabinit ( void  ) [read]

Definition at line 91 of file strtab.c.

{
  struct Strtab *ret;

  if (ps == 0)
    {
      ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void *);
      assert (sizeof (struct memoryblock) < ps);
    }

  ret = (struct Strtab *) calloc (1, sizeof (struct Strtab));
  if (ret != NULL)
    {
      ret->null.len = 1;
      ret->null.string = "";
    }
  return ret;
}

Here is the call graph for this function:

Here is the caller graph for this function:

size_t strtaboffset ( struct Strent se)

Definition at line 337 of file strtab.c.

{
  return se->offset;
}

Here is the caller graph for this function:

void* xmalloc ( size_t  n)

Definition at line 77 of file xmalloc.c.

{
  VOID *p;

  p = malloc (n);
  if (p == 0)
    p = fixup_null_alloc (n);
  return p;
}

Variable Documentation

size_t ps [static]

Definition at line 66 of file strtab.c.