Appendix: Data Structures in C

Vectors

• Typically implemented with an array
• Processed using a for loop:
    char pbuf0[ED_PAGE_SIZE];
  
    for (i = 0; i < ED_PAGE_SIZE; i++)
      pbuf0[i] = 0;
  
• Copied using memcpy
• Integer-typed elements initialized with memset
• Saved and restored with fread/fwrite (non-portable data representation)

Asymmetric Bounds

When using asymmetric bounds:

• Number of elements is equal to the difference between upper and lower bound.
• When upper bound equals lower bound the range is empty.
• The lower bound is the first occupied element.
• The upper bound is the first free element.

Matrices

• Multi-dimensional structures of elements of the same type
• Fixed-sized implemented as multi-dimensional arrays
  typedef double Transform3D[4][4];
  
  IdentMat(Transform3D m)
  {
      register int i;
      register int j;
  
      for (i = 3; i >= 0; --i)
      {
          for (j = 3; j >= 0; --j)
              m[i][j] = 0.0;
          m[i][i] = 1.0;
      }
  }
  
• Variable-sized matrices are handled through pointers to elements, but accessed using the array syntax:
          double **mat = (double **)xmalloc(rows * sizeof(double *));
          for (i = 0; i < rows; i++)
                  mat[i] = (double *)xmalloc(cols * sizeof(double));
  
• N dimensions can also be mapped into a flat structure using multiplication.

Tables

• Rows of different-typed fields
• Often implemented as arrays of structures
  static struct tok icmp2str[] = {
      { ICMP_ECHOREPLY,       "echo reply" },
      { ICMP_SOURCEQUENCH,    "source quench" },
      { ICMP_ECHO,            "echo request" },
      [...]
      { 0,                NULL }
  };
  
• Can be accessed using a pointer (type-safe)
  static struct user {
          uid_t uid;
          char *name;
          daddr_t space;
          long count;
          daddr_t spc30;
          daddr_t spc60;
          daddr_t spc90;
  } *users;
  
  /* [...] */
  
          struct user *usr, *usrs;
  
          for (usr = usrs, n = nusers; --n >= 0 && usr->count; usr++) {
                  printf("%5ld", (long)SIZE(usr->space));
                  if (count)
                          printf("\t%5ld", (long)usr->count);
                  printf("\t%-8s", usr->name);
                  if (unused)
                          printf("\t%5ld\t%5ld\t%5ld",
                              SIZE(usr->spc30), SIZE(usr->spc60),
                              SIZE(usr->spc90));
                  printf("\n");
          }
          free(usrs);
  }
  
• Accessing with an integer index is not type safe (why?)

Stacks

• Often implemented as an ADT
  #define STACKMAX 32
  static int opstack[STACKMAX];
  static int opsp;
  
  
  PushOp(op)
     int op;
  {
    if (opsp==STACKMAX) {strcpy(dispstr,"stack error");  entered=3;}
    else opstack[opsp++]=op;
  }
  
  int PopOp()
  {
    if (opsp==0) {
        strcpy(dispstr,"stack error");
        entered=3;
        return(kNOP);
    } else
      return(opstack[--opsp]);
  }
  
  int isopempty()
  {
    return( opsp ? 0 : 1 );
  }
  
• Also implemented in-line:
      de_stack[--stack_top] = '0' + c % 8;
      de_stack[--stack_top] = '0' + (c / 8) % 8;
      de_stack[--stack_top] = '0' + c / 64;
  
  Problem with overflow-underflow checking.

Queues

• Found when different systems are connected together (real world connection?)
  • Window system - user applications
  • OS network packets
  • Mail messages
  • Network interface cards
  • Disk drives
  • Serial communication
  • Printers
• Efficiently implemented with a ring buffer and two indices
  volatile int        rnd_head;
  volatile int        rnd_tail;
  [...]
  volatile rnd_event_t    rnd_events[RND_EVENTQSIZE];
  
• Avoids shifting overhead
• Code must ensure pointers wrap around. Two approaches
  • Conditional:
    static int    history_head, history_tail;
    #define hist_bump(h)    ((++(h) == NUM_HISTORY) ? ((h) = 0) : 0)
    
        for (i = history_tail; i != history_head; hist_bump(i))
            DrawPoints (old_pixmaps[i], bit_0_gc, xp, n);
    
  • Modulo arithmetic:
    adb_evq[(adb_evq_len + adb_evq_tail) % ADB_MAX_EVENTS] = *event;
    

Maps

• Trivial map, integer-indexed:
  static const int        mon_lengths[2][MONSPERYEAR] = {
    { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 },
    { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }
  };
  
• More sophisticated: key/value pairs
• The following map is used to dispatch functions based on the name of the command:
  #define F_NEEDARG       0x01                    /* needs an argument */
  #define F_OFFOK         0x02                    /* can turn off */
  static struct key {
          char *name;                             /* name */
          void (*f) __P((struct info *));         /* function */
          int flags;
  } keys[] = {
          { "all",        f_all,          0 },
          { "cbreak",     f_cbreak,       F_OFFOK },
          { "cols",       f_columns,      F_NEEDARG },
          { "columns",    f_columns,      F_NEEDARG },
          { "cooked",     f_sane,         0 },
          { "dec",        f_dec,          0 },
          { "everything", f_everything,   0 },
          { "extproc",    f_extproc,      F_OFFOK },
  /* [...] */
          { "size",       f_size,         0 },
          { "speed",      f_speed,        0 },
          { "tty",        f_tty,          0 },
  };
  
  static int c_key __P((const void *, const void *));
  
  static int
  c_key(a, b)
          const void *a, *b;
  {
  
          return (strcmp(((struct key *)a)->name, ((struct key *)b)->name));
  }
  
  int
  ksearch(argvp, ip)
          char ***argvp;
          struct info *ip;
  {
          char *name;
          struct key *kp, tmp;
  
          name = **argvp;
          if (*name == '-') {
                  ip->off = 1;
                  ++name;
          } else
                  ip->off = 0;
  
          tmp.name = name;
          if (!(kp = (struct key *)bsearch(&tmp, keys,
              sizeof(keys)/sizeof(struct key), sizeof(struct key), c_key)))
                  return (0);
          if (!(kp->flags & F_OFFOK) && ip->off) {
                  warnx("illegal option -- %s", name);
                  usage();
          }
          if (kp->flags & F_NEEDARG && !(ip->arg = *++*argvp)) {
                  warnx("option requires an argument -- %s", name);
                  usage();
          }
          kp->f(ip);
          return (1);
  }
  
  void
  f_all(ip)
          struct info *ip;
  {
          print(&ip->t, &ip->win, ip->ldisc, BSD);
  }
  
  

Hash Tables

• Construct integer array index out of the (non-integer) key
  static
  Hash(char *string, int len)
  {
      int h;
  
      h = 0;
      while (len--)
          h = (h << 3) ^ *string++;
      if (h < 0)
          return -h;
      return h;
  }
  
• Hash function, converts key into an integer
• A modulo function limits the integer into the size of a table
• A scheme for handling collisions must be provided (unless this is a perfect hash function)
  Atom
  MakeAtom(string, len, makeit)
      char *string;
      unsigned len;
      int makeit;
  {
      AtomListPtr a;
      int         hash;
      int         h;
      int         r;
  
      hash = Hash (string, len);
      if (hashTable)
      {
          h = hash & hashMask;
          if (hashTable[h])
          {
              if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
                  NameEqual (hashTable[h]->name, string, len))
              {
                  return hashTable[h]->atom;
              }
              r = (hash % rehash) | 1;
              for (;;)
              {
                  h += r;
                  if (h >= hashSize)
                      h -= hashSize;
                  if (!hashTable[h])
                      break;
                  if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
                      NameEqual (hashTable[h]->name, string, len))
                  {
                      return hashTable[h]->atom;
                  }
              }
          }
      }
  

Sets

• Small sets are sometimes represented as collection of bits
• Elements are added using binary-or
  pbitvec[j/BITS_PER_LONG] |= ((unsigned long)1 << (j % BITS_PER_LONG));
  
• Element presence is implemented using binary-and
  #define FD_ISSET(n, p) \
   ((p)->fds_bits[(n)/NFDBITS] & (1 << ((n) % NFDBITS)))
  
• Element removal is implemented using binary-and of the complement
  #define FD_CLR(n, p) \
   ((p)->fds_bits[(n)/NFDBITS] &= ~(1 << ((n) % NFDBITS)))
  
• Set intersection is implemented using binary and
  #define XFD_ANDSET(dst,b1,b2) \
   (dst)->fds_bits[0] = ((b1)->fds_bits[0] & (b2)->fds_bits[0]); \
  
• Set union is implemented using binary or
• Larger sets are sometimes represented as an array of values
      resourceQuarks[q >> 3] |= 1 << (q & 0x7);
  

Singly Linked Lists

• Properties:
  • Efficient addition and removal from any position
  • Linear traversal to access arbitrary elements
  • Efficient dynamic expansion
• List representation:
  struct host_list {
          struct host_list *next;
          struct in_addr addr;
  } *hosts;
  
• Traversal:
  int
  search_host(addr)
          struct in_addr addr;
  {
          struct host_list *hp;
  
          if (!hosts)
                  return(0);
  
          for (hp = hosts; hp != NULL; hp = hp->next) {
                  if (hp->addr.s_addr == addr.s_addr)
                          return(1);
          }
          return(0);
  }
  
• Element addition:
  void
  remember_host(addr)
          struct in_addr addr;
  {
          struct host_list *hp;
  
          if (!(hp = (struct host_list *)malloc(sizeof(struct host_list)))) {
                  err(1, "malloc");
                  /* NOTREACHED */
          }
          hp->addr.s_addr = addr.s_addr;
          hp->next = hosts;
          hosts = hp;
  }
  

Doubly Linked Lists

• Uses two pointers:
  struct queue {
      struct queue *q_next, *q_prev;
  };
  
• Adding and removing elements can be done given only a single element pointer
• Example: add elem after head:
      struct queue *next;
  
      next = head->q_next;
      elem->q_next = next;
      head->q_next = elem;
      elem->q_prev = head;
      next->q_prev = elem;
  

Circular Linked Lists

• Last element points to the head
• Can not be traversed using a simple for loop
• Typically the code looks for an element to occur again
  void
  prlex(FILE *fp, struct wordent *sp0)
  {
      struct wordent *sp = sp0->next;
  
      for (;;) {
          (void) fprintf(fp, "%s", vis_str(sp->word));
          sp = sp->next;
          if (sp == sp0)
              break;
          if (sp->word[0] != '\n')
              (void) fputc(' ', fp);
      }
  }
  

Trees

• Single path from each node to the trees root
• Applications
  • Data organization
  • Searching
  • Sorting
  • Language processing
  • Graphics
  • Compression
• Typically implemented using pointers to nodes:
  typedef struct tree_s {
          tree_t      data;
          struct tree_s   *left, *right;
          short       bal;
      }
      tree;
  
• Processing algorithms are also recursive:
  tree_t
  tree_srch(tree **ppr_tree, int (*pfi_compare)(), tree_t p_user)
  {
      register int    i_comp;
  
      if (*ppr_tree) {
          i_comp = (*pfi_compare)(p_user, (**ppr_tree).data);
          if (i_comp > 0)
              return (tree_srch(&(**ppr_tree).right, pfi_compare, p_user))
          if (i_comp < 0)
              return (tree_srch(&(**ppr_tree).left, pfi_compare, p_user))
          /* not higher, not lower... this must be the one.
           */
          return ((**ppr_tree).data)
      }
      /* grounded. NOT found.
       */
      return (NULL)
  }
  

Further Reading

• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974.

• Arash Baratloo, Timothy Tsai, and Navjot Singh. Transparent run-time defense against stack smashing attacks. In Christopher Small, editor, USENIX 2000 Technical Conference Proceedings, Berkeley, CA, June 2000. Usenix Association.

• Mark W. Eichlin and Jon A. Rochlis. With microscope and tweezers: An analysis of the internet virus of November 1988. In IEEE Symposium on Research in Security and Privacy, pages 326–345, May 1989.

• Donald E. Knuth. The Art of Computer Programming, volume 1: Fundamental Algorithms. Addison-Wesley, Reading, MA, third edition, 1997.

• Donald E. Knuth. The Art of Computer Programming, volume 3: Sorting and Searching. Addison-Wesley, Reading, MA, second edition, 1998.

• Douglas C. Schmidt. Gperf: A perfect hash function generator. In Jim Waldo, editor, USENIX C++ Conference, pages 87–100, Berkeley, CA, April 1990. Usenix Association.

• Robert Sedgewick. Algorithms in C Parts 1–4: Fundamentals, Data Structures, Sorting, Searching. Addison-Wesley, Reading, MA, third edition, 1997.

• Robert Sedgewick. Algorithms in C Part 5: Graph Algorithms. Addison-Wesley, Boston, MA, third edition, 2001.

• Eugene H. Spafford. The Internet worm: Crisis and aftermath. Communications of the ACM, 32(6):678–687, June 1989.

• Diomidis Spinellis. Code Reading: The Open Source Perspective, pages 95–140. Effective Software Development Series. Addison-Wesley, Boston, MA, 2003.

• H. E. Williams, J. Zobel, and S. Heinz. Self-adjusting trees in practice for large text collections. Software: Practice & Experience, 31(10):925–940, August 2001.

Exercises and Discussion Topics

1. Select a large software system, locate where arrays are used, and categorize their uses.
2. Fixed-length arrays notoriously impose arbitrary limits to program elements. Locate 20 instances of such limits in existing code and check whether these are documented in the respective system's documentation.
3. For the RDBMS of your choice locate documentation regarding cursors. Compare the functionality offered by cursors to the functionality offered by pointers to structures.
4. A number of linear algebra and matrix libraries are available on the Web in open-source form. Download two such packages and identify how matrices are stored.
5. Examine the stack operations performed on implementations based on explicit code. Identify those operations that do not fit into the model we described. Propose function names and code for implementing them.
6. Locate code where explicit control structures can be substituted by an array lookup mechanism. Explain how the code would be implemented.
7. Do you envisage any difficulties in implementing a hash-based map as an abstract data type? Suggest a way to overcome them.
8. Locate instances in the course's reference source code where sets are being used. Suggest other implementation strategies for each particular problem. Comment on whether a set data-type is used partly, because it is easy to create an efficient implementation for it.
9. Locate five instances of singly and doubly-linked lists in the course's reference source code and explain the function they perform.
10. Draw a binary tree containing the host names in your email address book. Add the names in a random order; not alphabetically. Systematically walk through the tree to derive a sorted listing of the host names. Construct a new tree adding the host names in the order they appear in the listing you constructed. Comment on the efficiency of searching data in the two trees.

• Contents

 Last change: Thursday, July 3, 2008 6:09 pm
 Unless otherwise expressly stated, all original material on this page created by Diomidis Spinellis is licensed under a Creative Commons Attribution-Share Alike 3.0 Greece License.