Re: Okay to move an "object" will-nilly?

On Wed, 28 Jun 2006 09:59:06 GMT, Frederick Gotham
<fgothamNO@xxxxxxxx> wrote in comp.lang.c:

(My dialect of English seems to puzzle people at times, so I'll first
clarify a few terms which I use in the following post:)

(1) By "domestic", I mean "ordinary, run-of-the-mill, not
extraordinary or strange".

(2) By "willy-nilly", I mean something along the lines of
"haphazardly", but without any sense of recklessness (i.e. gleefully
doing something without expecting any sort of negative effect, even
though there may in fact be a negative effect), e.g. "A child would drink
a glass of liquid left on the kitchen table willy-nilly, blissfully
ignorant as to whether it contained bleach".

======================================================

Okay I'll try to keep the C++ part brief (and yes, my eventual question
is about C):

In C++, there are things called objects. They behave just like
variables, but special things happen when they're created, destroyed,
copied, assigned to, etc.. (specifically, the programmer can specify code
which is to be executed).

If you want to copy an object in C++, is it ill-advised to simply do:

ArbitraryClass original_object;

ArbitraryClass *p = malloc( sizeof *p );

memcpy( p, &original_object, sizeof original_object );


The reason why it's il-advised is that when an object is created, code
can be executed via a "constructor" which may result in the acquisition
of resources such as dynamically allocated memory. If we perform a
"shallow copy" by using "memcpy", then the resulting copy is using the
same resources as the original (when in reality, we want it to get its
own). The matter is remedied by using a copy-constructor... but I won't
get into that here.

Anyway, notwithstanding any of that, I thought it would still be OK in
C++ to move an object in memory, i.e. simply re-locate it. This would
involve memcpy'ing its bytes to a different location and simply not
making any further use of the original. I was told however that this also
is il-advised in C++, because the object's address may be of some
significance to its internal workings (i.e. the special code that gets
executed when you assign to it, destroy it, etc.). A prime example would
be an object which contains a buffer, and which also contains a pointer
to the current position in the buffer, something like:

struct StringStream {

char buffer[1024];

char *p_pos; /* Points to an element of buffer */

};

If we were to move an object of the type "StringStream", then "p_pos"
would effectively become corrupt.

So what's the significance of this?

Recently, I wrote a funky kind of algorithm for sorting an array (whether
it be an array of char's, int's, double's or perhaps a C++ class type),
and the algorithm moved objects around willy-nilly by using memcpy and
discarding the original. However, my algorithm was "broken" in the sense
that it would corrupt objects whose address was of some significance to
their internal workings.

Hence, there is an accepted etiquette in C++ that, when writing re-usable
code such as a sorting algorithm, you DON'T just re-locate objects willy-
nilly, but rather you've to resort to more elustrious means.

My question is:
Does any such etiquette exist in C? If I were writing a domestic
sorting algorithm in C, would it be acceptable for me to re-locate the
objects willy-nilly?

The C qsort() function does exactly this. If you are sorting an array
of objects, the objects in the array must be move safe. If they are
not move safe, then you will have problems using them after you have
sorted them with qsort(), unless you have the degenerate case where
the array was already sorted so no swaps were performed by the sort.

In the case of your example StringStream structure, it would not be
safe to sort them by qsort(), nor would it be safe to sort them by any
other means that involved swapping.

As others have mentioned, you can define an array of pointers to the
structures, then sort this index array with another level of
indirection.

So C, just like C++, allows you to do some things that might not be
safe. You can use memcpy() or memmove() on C objects, just as you can
on POD objects in C++. It is up to the programmer to determine if the
internal structure of those objects makes the operation useful.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://c-faq.com/
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html
.

Relevant Pages

  • Re: Fastcode poll - Should Sort include worst case situations
    ... median algorithm, not O), there exists sequences that will beat ... quicksort and make it O. ... by many compiler vendors is "Engineering a Sort ... If it detects that a portion of an array is responding badly, ...
    (borland.public.delphi.language.basm)
  • Re: Hash table in C++? STL?
    ... The Oalgorithm is when you scan all ... > Assume array a and b both have N elements, ... > Will a binary search beat a hash lookup? ... Running time O) for the sort if using ...
    (comp.lang.cpp)
  • Re: Sorting
    ... The easiest, probably, is to go through the array. ... This algorithm is called bubblesort. ... less efficient than selection sort or insertion sort, ... What memory management is below? ...
    (comp.lang.c)
  • Re: Sorting
    ... Then go back to the start of the array and do it again, until you make a clean sweep without swapping. ... This algorithm is called bubblesort. ... less efficient than selection sort or insertion sort, ...
    (comp.lang.c)
  • Re: regex question - trying to find ".mp3" in a SELECT box
    ... But `Array' is a Function object reference. ... Establish a new execution context using F's FormalParameterList, ... Since is not a primitive value, the exception should be thrown. ... | 5.2 Algorithm Conventions ...
    (comp.lang.javascript)
Loading