[ale] Copy a Structure - A C Question

[Byron A Jeff]

> 
> Wow! What a great answer. Thank you for taking the time to expound on 
> this issue.

No problem. It helps when you've taught C programming at the college level for
5 years.

> I tried bcopy after making the post and it worked just as 
> you stated. I just tried the assignement operator as you suggested but 
> it puked. 

What happened?

>I believe that it behaved this way because the structure 
> element in this discussion is really an element in a dynamically 
> allocated linked list, so the structure name is really a pointer.

OK. Well you can copy either the pointer or the actual structure. Both are
legal. Another example....

//--------------------------------------
struct stuff s1,s2,p1,p2;

// ...

p1 = &s1; // These are pointer copies
p2 = &s2;

*p2 = *p1; // A structure copy using the pointers. Equivalent to s2=s1
//--------------------------------------

> I'm 
> not copying the entire linked list, but only those elements that meet 
> certain criteria.

A suggestion then: Don't bother copying the structs from the list since they
are already allocated. Simply copy the pointers to the structs that meet the
criteria. My semester projects always used this technique for searching and
sorting. Since the C library qsort function only sorts arrays, we would do
selections from out of the list into an array of pointers (not structs), then
sort the pointers. So the list remains intact but the array of pointers into
the list gives a sorted view of the list.

> In essence, I'm splitting off a group of elements from 
> the main list. The pointer to the next element is reassigned so there is 
> no problem with a global copy of the original.

I see where you're going. The real question is whether or not the copy is a
view of the original list, meaning that it's a subset of elements that are
somehow rearranged, or if it's a true copy. The determinant is if other than
the next element pointer, does any other part of the struct have to differ
between the original and the copy. You stated that these are large structs,
so copying them are wasteful of both time and memory. If the copy remains an
exact duplicate of the original it would be better to create an array or a list
of pointers and point them back to the original elements. So instead of this:

// ------ Full struct copy ----------

struct stuff *mylist, *myview, *t1,*t2;

// ...
myview = malloc(sizeof(stuff) * listlength); // Allocate Full structures
for(t1=mylist,t2=myview;t1;t1=t1->next) {
   if(meets_criteria(t1)) {
      *t2++ = *t1; // Copy if it meets the criteria.
   }
}
// ------ End of Full struct copy

The above code will take up a lot of memory allocated to the structs and a
lot of time copying them. Instead create a view of the list by copying only
the pointers to the interesting structs...


// ------ Pointer only copy ----------

struct stuff *mylist, **myview, *t1,**t2;

// ...
myview = malloc(sizeof(stuff *) * listlength); // Allocate only pointers
for(t1=mylist,t2=myview;t1;t1=t1->next) {
   if(meets_criteria(t1)) {
      *t2++ = t1; // Copy the pointer only, if the struct it points to 
                  // meets the criteria.
   }
}
// ------ End of Pointer only copy

Note the code looks almost exactly the same, but the space and time required
to copy the pointers is significantly less than the first example.

Dynamically allocated arrays such as the one above is cheap and easy to do. 
For true flexibility the view can also be allocated as a list consisting of
the data pointer to the original list nodes and the next pointer to the next
element of the view.

> 
> Thanks for your excellent response!

You are welcome. Always glad to help.

BAJ
> 
> Byron A Jeff wrote:
> 
> >>Good Morning ALE'rs:
> >>
> >>This is a question for the C programmers out there. I have a situation 
> >>where I need to copy a rather large data structure to another memory 
> >>location.
> >>
> >
> >OK.
> >
> >>Is there a C function that I can use to do this rather than 
> >>going through the arduous task of allocating memory and coping each 
> >>element manually?
> >>
> >
> >Each element manually? In one of very strange quirks of C, while arrays
> >generally cannot be copied wholesale by the assignment operator (due to
> >the definition of the name of an array), structures can. So this is perfectly
> >legal:
> >
> >// Structure copy example-------------------------------------------------
> >struct mystruct one,two;
> >
> >// ...
> >
> >two = one; // Copy an entire struct including all the elements.
> >
> >// End of example---------------------------------------------------------
> >
> >>In addition, since this project is still in 
> >>development, the makeup of the structure may change and I don't want to 
> >>worry about having to keep my manual routine updated.
> >>
> >
> >Agreed. But no matter. The assignment will copy all of the elements.
> >
> >>The structure 
> >>contains a combination of 
> >>character arrays,
> >>
> >
> >No problem.
> >
> >>integer values
> >>
> >
> >No problem.
> >
> >>and pointers to other structures.
> >>
> >
> >It depends here. If it's OK for both structures, the original and the copy, to
> >point to same 'other struct' (this is called a shallow copy in C++ speak), then
> >no problem. You'd have to do more if you wanted to clone a copy of the 'other
> >struct'. Simple assignment won't do that.
> >
> >
> >>Since this is a structure, is all the allocated 
> >>memory for the structure in one contiguous chunk?
> >>
> >
> >Yes. But there's no guarantee that the individual elements are contiguous.
> >Often compilers will insert padding between the elements to maintain alignment.
> >
> >>If so, could I then 
> >>use something like memcpy to do the job?
> >>
> >
> >Sure. But why when a simple assignment does the job so well.
> >
> >Here are the major differences between arrays and structs:
> >
> >* The name of an array is defined as a pointer to the first element. A struct's
> >  name defines the struct itself.
> >
> >* Assignment on arrays is illegal because array names cannot be assigned with
> >  new values. Struct assignment copies a struct as you would expect.
> >
> >* Array parameters are pass by reference, since it implicitly passes a pointer
> >  to the array. Struct parameters are copied. One needs to watch that when
> >  passing a very large struct. It generally better to pass a pointer to the
> >  struct, even when you have no intention of changing it (use a const...)
> >
> >* Arrays cannot be returned as the result of a function. Structs can.
> >
> >In the end structs are much more like simple scalars and behave in very much
> >the same manner.
> >
> >So just assign the structs and don't worry about it. It'll do the same thing
> >as the memcpy, but will be much more intuitive.
> >
> >It's kind of funny how C's quirkiness with arrays throws folks off when 
> >structs come behind it...
> >
> >BAJ
> >
> 
> -- 
> Sparta, NC 28675 USA
> 336.372.6812
> http://www.esc1.com
> The Gates of hell shall NOT prevail...
> 
> 
> 


---
This message has been sent through the ALE general discussion list.
See http://www.ale.org/mailing-lists.shtml for more info. Problems should be 
sent to listmaster at ale dot org.