How do you make diagrams of memory and data structures?

Question

I have to create a short program in C that manipulates strings, but I always run into some weird pointer errors. While K&R is a great reference on the language, and I often look at it when I am puzzled it already assumes you are an adequate programmer.

The lecturer that teaches us programming said that good programmers make nice diagrams on these stuff but I have no idea how to do it. Can you recommend a good book or lectures on this?

Thanks, I will appreciate every answer I get.

Answer 1

I echo the suggestion of drawing them on paper first and then, if you feel the need, you can include an ascii version of them into the code.

I normally use these three formats:

---

to reason about memory:

      +--------+
   0  |        |  <- start
      +--------+
   1  |        |  <- q  scans from start to end
      +--------+
      ~  ..... ~
      +--------+
      |        |  <- end
      +--------+  \
      |        |  |
      +--------+  |__ rest of the
      ~  ..... ~  |   allocated memory
  n   |        |  |
      +--------+ /

---

to reason about strings:

    0               n
   +--+-- --+--+--+--+
   |  | ... |  |  |\0|
   +--+-  --+--+--+--+
     ^        ^__ q moves from the
     |            end to the start
     p moves from
       start to the end

---

to reason about bits in a word:

   xxxx yyzz 00tt 11ss
   \    \ \  \ \  \ \__ storage registry
    \    \ \  \ \  \___ always set to 1
     \    \ \  \ \_____ temp value
      \    \ \  \______ always zeroed 
       \    \ \________ zero flag value
        \    \_________ y register
         \_____________ x address            

---

I used to do something similar for finite state machines too but they tended to be too complex (and time consuming to do) so I now directly embed the graphviz code into a comment. Even not knowing about GraphViz it should be easy to guess how to draw the FSM diagram.

digraph G {
  mode = hier

  LIMBO [style= filled];
    node [shape = ellipse];

    LIMBO   -> HEADER  ;
    HEADER  -> LIMBO;
    HEADER  -> TUNE ;
    TUNE    -> LYRICS ;
    TUNE    -> CHORD [style=dashed ];
    TUNE    -> LIMBO ;
    GRACE   -> TUNE ;
    GRACE   -> CHORD  [style=dashed ] ;
    SYMBOLS -> TUNE ;
    SYMBOLS -> LIMBO ;

    overlap=false
  sep = 1.5
}

---

These cover the vast majority of diagrams I need. For more complex ones I use GraphViz or OpenOffice Draw.

Answer 2

One of the most useful things I once have done was my application draw the graphs ...

In an application that had a complicated data structure specialized to the job (standard hashtable didn't do in that case ;-) I had my application output a ".dot" script that dot tool of graphviz could parse.

It did this by having a dump routine (okay, method, it was C++) that output the .dot header

 digraph g {

then walked my data structure and then wrote the footer

 }

In the structure walk it wrote every pointer with

 SOURCE -> DESTINATION

where Source was the memory address of the referencing object preprened with O (O213435354) and Destination was the object pointed to in the same format.

At the start of every object it also wrote

SOURCE [ .... ]  

with ... being the object data.

Whenever the application was at an "intersting" state I dumped the graph and then used the dot-tool from graphviz to visualize it. I have found a lot of pointer error quite easily that way, the eye is built to see regular structures in lines ...

By the way I still regularily use graphviz as it is quite nice to write & edit graphs with the text editor and let the tool vizualize them afterward. If I need to dress up .dot graphs for a powerpoint-spoiled audience, I load them into OmniGraffle on my mac. (And my PC-using coworkers think I have some diagramming superhero powers because with that combination I produce graphs 10 times faster than them when they use Visio)