Storing data structure

Discussion in 'C Programming' started by TDB, Jan 27, 2008.

  1. TDB

    TDB Guest

    Hello,

    I'm creating an application using C which requires the data structures
    like trees and graphs to be stored in files and retrieved later
    ( simply serialization of a data structure ) .

    Is there any libraries available in C for this purpose ?
    TDB, Jan 27, 2008
    #1
    1. Advertising

  2. TDB

    santosh Guest

    TDB wrote:

    > Hello,
    >
    > I'm creating an application using C which requires the data structures
    > like trees and graphs to be stored in files and retrieved later
    > ( simply serialization of a data structure ) .
    >
    > Is there any libraries available in C for this purpose ?


    The Standard library functions fread/fwrite should be sufficient
    primitives for this purpose.
    santosh, Jan 27, 2008
    #2
    1. Advertising

  3. TDB

    jacob navia Guest

    TDB wrote:
    > Hello,
    >
    > I'm creating an application using C which requires the data structures
    > like trees and graphs to be stored in files and retrieved later
    > ( simply serialization of a data structure ) .
    >
    > Is there any libraries available in C for this purpose ?


    You will have to do that yourself, i.e. you will have to transform
    the embedded pointers into pointers to other file structures.

    In a very general form, you should be able to translate pointers into
    indexes into a node array. When you read back the node array you
    transform again those indexes into real pointers.



    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
    jacob navia, Jan 27, 2008
    #3
  4. santosh said:

    > TDB wrote:
    >
    >> Hello,
    >>
    >> I'm creating an application using C which requires the data structures
    >> like trees and graphs to be stored in files and retrieved later
    >> ( simply serialization of a data structure ) .
    >>
    >> Is there any libraries available in C for this purpose ?

    >
    > The Standard library functions fread/fwrite should be sufficient
    > primitives for this purpose.


    You're right, but I don't think he was asking for primitives. He was asking
    for a library which "understands" the serialisation of trees and graphs in
    a way that primitives don't. You can't just fwrite(root, sizeof *root, 1,
    fp) and expect the whole tree to be saved.

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
    Richard Heathfield, Jan 27, 2008
    #4
  5. santosh <> writes:
    > TDB wrote:
    >> I'm creating an application using C which requires the data structures
    >> like trees and graphs to be stored in files and retrieved later
    >> ( simply serialization of a data structure ) .
    >>
    >> Is there any libraries available in C for this purpose ?

    >
    > The Standard library functions fread/fwrite should be sufficient
    > primitives for this purpose.


    Certainly, but I think that misses the OP's point. You have to
    flatten the data structure somehow, replacing any pointers with
    something more "static" (not in the C keyword sense), before you can
    fwrite anything.

    I don't know of any libraries to do this, but they probably exist.

    --
    Keith Thompson (The_Other_Keith) <>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Jan 27, 2008
    #5
  6. TDB

    Willem Guest

    TDB wrote:
    ) Hello,
    )
    ) I'm creating an application using C which requires the data structures
    ) like trees and graphs to be stored in files and retrieved later
    ) ( simply serialization of a data structure ) .
    )
    ) Is there any libraries available in C for this purpose ?

    A library can only be expected to save a data structure in a file
    if it knows all the details of that data structure, and this is usually
    only the case if that library also provides those structures.
    So, IMO your best bet would be to look for tree- and graph-libraries.


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
    Willem, Jan 27, 2008
    #6
  7. "TDB" <> wrote in message news
    > I'm creating an application using C which requires the data structures
    > like trees and graphs to be stored in files and retrieved later
    > ( simply serialization of a data structure ) .
    >
    > Is there any libraries available in C for this purpose ?
    >

    Yes and no.
    One cannot store pointers in a file. Whilst there are general-purpose
    libraries that purport to be able to serialise structures, using a
    programmer-specified format string, these are so difficult to use that I
    think it is red herring to recommend them.
    However storing a tree is not too difficult. Simply write a bracket,
    recursively write the subtree, and then write a closing bracket.

    Loading is more tricky.
    If you look for the Newick tree loader on my website you might find what you
    are looking for. However it will only load trees, not graphs.

    --
    Free games and programming goodies.
    http://www.personal.leeds.ac.uk/~bgy1mm
    Malcolm McLean, Jan 27, 2008
    #7
  8. TDB

    santosh Guest

    TDB wrote:

    > Hello,
    >
    > I'm creating an application using C which requires the data structures
    > like trees and graphs to be stored in files and retrieved later
    > ( simply serialization of a data structure ) .
    >
    > Is there any libraries available in C for this purpose ?


    One link I found through Google is:

    <http://tpl.sourceforge.net/>

    HTH
    santosh, Jan 27, 2008
    #8
  9. TDB <> writes:

    > Hello,
    >
    > I'm creating an application using C which requires the data structures
    > like trees and graphs to be stored in files and retrieved later
    > ( simply serialization of a data structure ) .
    >
    > Is there any libraries available in C for this purpose ?

    As others have pointed out without some work on your side this won't
    work. Howerver you may check the berkeley DB stuff which offers quite
    a bunch for "persitence in C"

    http://www.oracle.com/database/berkeley-db/db/index.html

    Regards
    Friedrich


    --
    Please remove just-for-news- to reply via e-mail.
    Friedrich Dominicus, Jan 27, 2008
    #9
  10. TDB

    cr88192 Guest

    "TDB" <> wrote in message
    news:...
    > Hello,
    >
    > I'm creating an application using C which requires the data structures
    > like trees and graphs to be stored in files and retrieved later
    > ( simply serialization of a data structure ) .
    >
    > Is there any libraries available in C for this purpose ?



    well, there are a lot of libs for a lot of things, so a lot depends on what
    you want to do.


    if XML is acceptable, than maybe either SAX or DOM may be what you are
    looking for.
    libxml is a common choice here.

    many projects may implement other representations as well, for example,
    Lisp-style S-Expressions may well be a good starting point for a customized
    (yet still "general") data processing/serialization system (this depends a
    lot on what is being done, but anymore, I will generally lean more in favor
    of XML than S-Expressions).


    also common is implementing a format based on line-oriented text files.

    in this way, we can use fprintf, fgets, and sscanf (actually, I more usually
    implement a 'split' function here), in order to serialize and reload the
    data.

    this approach is often both simple and allows fast loading/saving, but is
    less general than SAX or DOM (essentially, the structure of the data and the
    structure of the file are tied together).

    as such, this is good for dumping and reloading a bunch of context-specific
    data (such as tables, 3D geometry, ...) but is not so good for more
    free-form data (such as compiler AST trees, hypertext documents, ...).

    for XML, this is fairly close to the SAX approach.


    another common approach, is to regard the file as a serialized bytestream or
    similar.

    in these cases, we often have loaders that, for example, use fgetc to read
    individual bytes (or sometimes, FOURCC's and similar), and dispatch to the
    appropriate handlers as needed (read the magic value for a node, so call the
    function to handle reading nodes, ...).

    this approach tends to lead to formats that are both fairly dense, and have
    a good tradeoff between speed and flexibility (textual formats tend to be
    much bigger and slower, and data-dumping formats tend to be brittle).

    however, as a cost, these formats are not human-readable (unlike most
    textual formats), and are typically much slower than raw dumping.

    I suspect, however, for widely used binary formats, variations of this
    approach are the most common.


    another common approach is data dumping:

    freading/fwriting data is possible, but as noted, may require a lot of
    processing to serialize and reload the data. for this approach, it is common
    practice to avoid any use of pointers within these structures (instead,
    indices and offsets are used almost exclusively, and the app will operate on
    the data more or less as it appears in the files).

    for example, I have seen loaders that will fread a whole file structured
    like this, and then create a context with:
    a pointer to the file's data;
    a set of specific pointers to specific parts of the files' data (such as the
    strings tables, nodes table, ...).

    other times, specific tables are read, and placed within different buffers.


    when handling accesses, we will use indices or offsets, to access the
    specific members.
    j=ctx->node.left;
    k=ctx->node.right;
    s=ctx->strtab+ctx->node.name;


    other times, these files may be split up into some number of chunks or
    blocks, which are loaded, processed, and/or stored, as needed. this
    variation is common within things like database engines (for example, for
    implementing structures like B-Trees).

    the advantage of this approach is that file loading and saving can be made
    to operate very quickly (for a save, we simply dump the whole file's
    contents back to disk, or, in some cases, unmap the file from memory).

    the disadvantage, is that these kind of file formats can become excessively
    brittle (these are the kinds of files where you often find version numbers,
    endianess and alignment check values, ..., embedded in the headers).

    as a result, these formats are usually used within a specific version of a
    specific app, and very rarely become common-use. very often, these formats
    are also not formally specified either (when the code or data changes, so
    does the file format...).


    dunno if this helps any...
    cr88192, Jan 27, 2008
    #10
  11. TDB

    CBFalconer Guest

    Keith Thompson wrote:
    > santosh <> writes:
    >> TDB wrote:
    >>
    >>> I'm creating an application using C which requires the data
    >>> structures like trees and graphs to be stored in files and
    >>> retrieved later (simply serialization of a data structure).
    >>>
    >>> Is there any libraries available in C for this purpose ?

    >>
    >> The Standard library functions fread/fwrite should be
    >> sufficient primitives for this purpose.

    >
    > Certainly, but I think that misses the OP's point. You have to
    > flatten the data structure somehow, replacing any pointers with
    > something more "static" (not in the C keyword sense), before you
    > can fwrite anything.
    >
    > I don't know of any libraries to do this, but they probably
    > exist.


    Highly doubtful. Any such library would have to understand the
    entire organization of the trees and graphs.

    --
    [mail]: Chuck F (cbfalconer at maineline dot net)
    [page]: <http://cbfalconer.home.att.net>
    Try the download section.



    --
    Posted via a free Usenet account from http://www.teranews.com
    CBFalconer, Jan 28, 2008
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jonny
    Replies:
    2
    Views:
    783
  2. toton
    Replies:
    11
    Views:
    695
    toton
    Oct 13, 2006
  3. Jonathan Wood
    Replies:
    1
    Views:
    498
    Jonathan Wood
    Jun 2, 2008
  4. Gundala Viswanath
    Replies:
    1
    Views:
    607
    Gert-Jan de Vos
    Jan 17, 2009
  5. A
    Replies:
    27
    Views:
    1,577
    Jorgen Grahn
    Apr 17, 2011
Loading...

Share This Page