Efficency and the standard library

[spinoza1111]

[...]

It was hard to get my doubly linked list working, but I did. It would
have been nice to have a separate tool for linked lists. Richard
Heathfield appears to have published such a tool in 2000, in C
Unleashed, but as far as I can determine (see elsethread), the
Dickiemaster copies the actual values into the list. This would have
blown me to Kingdom Come. I THINK the Heathman wanted to avoid using
pointer to void (he is welcome to comment here).

I don't know why Richard implemented a simple linked-list that way. I take
it he is not that fond of intrusive linked lists.

But his solution IS intrusive, unless by "intrusive" you mean
something else.

A linked list of pointers (the right way) is only "intrusive" in that
it consists of a set of eyes looking at data.

Whereas to copy *anything* into your linked list is asking for
trouble, since you're both looking at data and grabbing it. Eyes and
paws.

What about intrusive data-structures that do not require any copying and/or
void pointers? I use them all the time.

That was my idea...use a macro for strong typing.

 

[spinoza1111]

The main concern is, is this library easy to use? Only when the
program hits the treacle do ypu stary worrying about how efficient the
code is behind those nice interfaces.

Yeah.  My string library (like most C programmers, I wrote one at one point)
actually does have, under some circumstances, linked lists in it.  It never
seems to have become an issue.

They're used to provide familiar semantics.  Consider:
        char s[256] = "hello, world!";
        char *t;

        t = strstr(s, "world");
        strcpy(t, "sailor!");

You would expect this to leave s = "hello, sailor!" (note that it's a [], not
a *, and sized to provide enough room).

At this point, it doesn't seem that "your" string library is what we
need, since you have to do its mallocs or fixed allocations. A true
solution would instead encapsulate all memory management.

Your library allows its users to make crappy and irresponsible secret
decisions as to "how big" things can get, which programmers are
rarely, if ever, qualified to make.

If you are doing structures, rather than raw pointers to characters, you
need some way to indicate that the same change must be made in both t and s.
My solution was to have s contain a linked list of strings derived from it,
and t contain a pointer to the string it is derived from.  When you modify
t, it observes that it is a substring of another string, so in fact, the
modification is passed back up to s.  Since t and s share storage, this
works.

OK, your string library is something like a library of pointers
outside the library; a collection of maps. I did something like this
in a preliminary fashion in 1987, but found that it was too much
trouble. A string library needs ownership of the strings.

However, a full library MIGHT want to sponsor both "virtual" strings
(pointers to space the library has neither mallocated nor predefined)
and "actual" strings (where the library has done the memory
management).

 

[spinoza1111]

Indeed. Too bad linked data structures have a tendency toward poor
cache performance. And depending on how the list is implemented, many
programmers (even in C#) would likely balk at the extra overhead of
storing and following links for a "mere" string.

They wouldn't have to follow the links. And the "overhead" is
psychological. Frankly, Julienne, I'm tired of the facility in which
ordinary garden-variety transform "the need to think" into "wasting
overhead" as if their brains == their computer.

But I can see where linked data structures have a tendency toward poor
cache performance, the blocks not being adjacent. If this is a
consideration, malloc() a big block and then do memory allocation
yourself inside the big block.

Can you elaborate on this? I'm not sure I fully understand what you
mean.

It appeared to me that Richard's "general purpose linked list" of 2000
copies the values of anything passed to it into nodes of the linked
list. But if I were (in a blue moon) to use his code to re-present
strings as linked list, then he'd copy unbounded amounts of data
inside his code.

For the same reason RISC designers refused to implement the "fancy"
instructions of the old DEC Vax, a library function needs IF POSSIBLE
to have a fixed upper bound on the time it will consume. If I am
correct about Richard's code, if I pass him a huge data structure, his
timings will blow up because he's copying my data. Whereas if he'd
done the job right, for each node I pass him, he would have taken
constant time to set four-byte values (essentially the node's data
pointer and the pointer to the next element).

It is not always possible for a library function to have such a fixed
upper bound. If it is a replace() or a strstr(), OF COURSE its time
will depend on a fact about the data.

But this dependency falls right out of the problem, it is a necessary
fact about the problem. Whereas Richard's copy-o-rama comes out of
left field and seems to me completely unnecessary. If your compiler
supports pointer to void, use it, I say, and be damned.

Every "textbook" linked list I can recall uses a pointer in the data
node when the data is non-trivial. I was shocked, *shocked* to find
Richard did not.

But it is true that C handles this poorly because "void pointer is not
a 'real' pointer". This fact, about the inadequacy of C, has been
transformed into barbaric knowledge by the C clerisy, where what is a
criticism is re-intoned in tones of holy dread.

The problem wasn't solved until C++ and the notion of generics.
Preprocessor macros can simulate the effect of generics but only
painfully.

As far as I'm concerned: as far as I can see
Richard Heathfield does not work tastefully:
If something is coyote ugly and unpleasant
He seems to me to regard it, as a Heaven-sent
Opportunity
To increase the great weight of the world's misery.

Thus in linking up a linky list
We see, with dread, we say, oh hist,
He's copying ANYTHING into each node
Oh what a weary thing that is, and what a weary road.

He seems to be the Puritan
Who makes us sad whenever he can.

 

[spinoza1111]

Which myth is that then? I'm dealing with reality - that of being left
with an undocumented mess to look after, because the clown in question
preferred to do something "cool" and "neat", rather than what he was
paid to do.

What was he paid to do? Something hot and sloppy?

By the way, I don't object to his doing something "cool" and "neat", but
on his own time, OK?

But on the job we must produce crap at speed?

[irrelevant drivel deleted]

Sure, the guy may have gone overboard. But the effect of the myth is
to bias programmers to a "simplicity" which permits them to make silly
mistakes.

Way overboard in this instance. And which mistakes might those be, then?

Or whatever. Yes, I had to refresh my memory (you might also consider
doing your homework on what's what before posting: there's really no
excuse not to since so much information is online).

Which homework's that then, Spinny? There was nothing I needed to look up..

As I said, this is because intelligent people prefer learning and
remembering elegant things,

Very likely.

and feof() is coyote ugly, and, as I said, a bug waiting to happen

 > when a C program has to do an extra read merely to check EOF from

a device.

Well, gee, life's a bitch sometimes, ain't it though! I'll let the good
people of Haiti know that while they might think *they* have problems,
poor Spinny has to deal with feof().

Haiti? OK, an old argument: don't complain about anything, you have no
right given "the weight of the world". The problem being that Haiti's
problems were CAUSED by US corporations in the same system in which
they don't give programmers, *as a matter of principle* enough time to
do a quality job.

 

[Nick Keighley]

Until very recently, I thought that bit length was an unacceptable
restriction on string length, but if one ponders the scale of long
long, it is more than enough.

if you mean (I don't find "bit length" very clear) a character count
and a collection of characters and using long long as the count then
small strings have a heft overhead.

"hello" has more space devoted to the count than the character data

 

[Chris M. Thomasson]

[...]

It was hard to get my doubly linked list working, but I did. It would
have been nice to have a separate tool for linked lists. Richard
Heathfield appears to have published such a tool in 2000, in C
Unleashed, but as far as I can determine (see elsethread), the
Dickiemaster copies the actual values into the list. This would have
blown me to Kingdom Come. I THINK the Heathman wanted to avoid using
pointer to void (he is welcome to comment here).

I don't know why Richard implemented a simple linked-list that way. I
take
it he is not that fond of intrusive linked lists.

But his solution IS intrusive, unless by "intrusive" you mean
something else.

I mean why not embed the list node directly into a data-structure? The list
nodes intrudes into the object.

That was my idea...use a macro for strong typing.

I was thinking of the following technique. Here, let me quickly code up a
simple example:
_______________________________________________________________
#include <stdio.h>
#include <stddef.h>


#define CONTAINS(mp_self, mp_type, mp_member) \
((mp_type*)(((unsigned char*)(mp_self)) - \
offsetof(mp_type, mp_member)))


struct slist
{
struct slist* next;
};


#define SLIST_SINIT { NULL }


#define slhead(mp_self) ((mp_self)->next)


void
slpush(struct slist* const self,
struct slist* node)
{
node->next = self->next;
self->next = node;
}


struct slist*
slpop(struct slist* const self)
{
struct slist* node = self->next;
if (node) self->next = node->next;
return node;
}


void
slreverse(struct slist* const self)
{
struct slist* head = NULL;
struct slist* node = self->next;

while (node)
{
struct slist* next = node->next;
node->next = head;
head = node;
node = next;
}

self->next = head;
}




struct foo
{
char const* string;
struct slist node1;
struct slist node2;
};


#define FOO_SINIT(mp_string) \
{ (mp_string), SLIST_SINIT, SLIST_SINIT }


int main()
{
struct slist* node;
struct slist list1 = SLIST_SINIT;
struct slist list2 = SLIST_SINIT;

struct foo foo[] =
{
FOO_SINIT("One"),
FOO_SINIT("Two"),
FOO_SINIT("Three"),
FOO_SINIT("Four"),
FOO_SINIT("Five")
};

size_t i;
size_t depth = sizeof(foo) / sizeof(foo[0]);

for (i = 0; i < depth; ++i)
{
slpush(&list1, &foo.node1);
slpush(&list2, &foo.node2);
}

slreverse(&list2);


node = slhead(&list1);

while (node)
{
struct foo* f = CONTAINS(node, struct foo, node1);

printf("(%p)->foo(%s)\n",
(void*)f,
f->string);

node = node->next;
}


puts("--------------------------------------------------");


node = slhead(&list2);

while (node)
{
struct foo* f = CONTAINS(node, struct foo, node2);

printf("(%p)->foo(%s)\n",
(void*)f,
f->string);

node = node->next;
}

return 0;
}
_______________________________________________________________


The `struct slist' objects intrude upon the `struct foo' objects. Now, you
can create a generic set of functions that operate on `struct slist' objects
regardless of what they are embedded within (e.g., see the `slreverse()'
function).

 

[spinoza1111]

if you mean (I don't find "bit length" very clear) a character count
and a collection of characters and using long long as the count then
small strings have a heft overhead.

"hello" has more space devoted to the count than the character data

Hmm, good point. The vast majority of strings fit in int or even short
or even byte, and the counts of strings probably increase
exponentially from long long to long to int to short to byte.

OK, use a byte for string length in a linked list. When you need the
total length sum the byte lengths in a long long. Shouldn't be a
problem for 90% of all strings.

Then, "hello" would take

1 byte length
4 (?) byte pointer to value
6 bytes for the value

You do agree that you're gonna need more bytes than are in the string.
We could get rid of the NUL bytes by storing the segment length and
not the length of the string in the linked list node, and whenever we
need the "real" length, walking the list.

But note that I fall here into the trap that Heathfield apparently
fell into in C Unleashed with his less than amazing linked list: some
calls to my string thingie blow up.

Better, then, to put the total length in the first node.

 

[spinoza1111]

[...]
It was hard to get my doubly linked list working, but I did. It would
have been nice to have a separate tool for linked lists. Richard
Heathfield appears to have published such a tool in 2000, in C
Unleashed, but as far as I can determine (see elsethread), the
Dickiemaster copies the actual values into the list. This would have
blown me to Kingdom Come. I THINK the Heathman wanted to avoid using
pointer to void (he is welcome to comment here).
I don't know why Richard implemented a simple linked-list that way. I
take
it he is not that fond of intrusive linked lists.

But his solution IS intrusive, unless by "intrusive" you mean
something else.

I mean why not embed the list node directly into a data-structure? The list
nodes intrudes into the object.

That was my idea...use a macro for strong typing.

I was thinking of the following technique. Here, let me quickly code up a
simple example:
_______________________________________________________________
#include <stdio.h>
#include <stddef.h>

#define CONTAINS(mp_self, mp_type, mp_member) \
  ((mp_type*)(((unsigned char*)(mp_self)) - \
    offsetof(mp_type, mp_member)))

struct slist
{
    struct slist* next;

};

#define SLIST_SINIT { NULL }

#define slhead(mp_self) ((mp_self)->next)

void
slpush(struct slist* const self,
       struct slist* node)
{
    node->next = self->next;
    self->next = node;

}

struct slist*
slpop(struct slist* const self)
{
    struct slist* node = self->next;
    if (node) self->next = node->next;
    return node;

}

void
slreverse(struct slist* const self)
{
    struct slist* head = NULL;
    struct slist* node = self->next;

    while (node)
    {
        struct slist* next = node->next;
        node->next = head;
        head = node;
        node = next;
    }

    self->next = head;

}

struct foo
{
    char const* string;
    struct slist node1;
    struct slist node2;

};

#define FOO_SINIT(mp_string) \
    { (mp_string), SLIST_SINIT, SLIST_SINIT }

int main()
{
    struct slist* node;
    struct slist list1 = SLIST_SINIT;
    struct slist list2 = SLIST_SINIT;

    struct foo foo[] =
    {
        FOO_SINIT("One"),
        FOO_SINIT("Two"),
        FOO_SINIT("Three"),
        FOO_SINIT("Four"),
        FOO_SINIT("Five")
    };

    size_t i;
    size_t depth = sizeof(foo) / sizeof(foo[0]);

    for (i = 0; i < depth; ++i)
    {
        slpush(&list1, &foo.node1);
        slpush(&list2, &foo.node2);
    }

    slreverse(&list2);

    node = slhead(&list1);

    while (node)
    {
        struct foo* f = CONTAINS(node, struct foo, node1);

        printf("(%p)->foo(%s)\n",
               (void*)f,
               f->string);

        node = node->next;
    }

    puts("--------------------------------------------------");

    node = slhead(&list2);

    while (node)
    {
        struct foo* f = CONTAINS(node, struct foo, node2);

        printf("(%p)->foo(%s)\n",
               (void*)f,
               f->string);

        node = node->next;
    }

    return 0;}

_______________________________________________________________

The `struct slist' objects intrude upon the `struct foo' objects. Now, you
can create a generic set of functions that operate on `struct slist' objects
regardless of what they are embedded within (e.g., see the `slreverse()'
function).

Very clever. I like this idea. Lists remain pure lists. Very elegant.
But: I do not understand how, if I have ONLY a foo, to find the next
foo.

 

[Julienne Walker]

They wouldn't have to follow the links. And the "overhead" is
psychological.

They *would* have to follow the links unless there are fingers into
the list. One of the basic limitations of a linked list is a lack of
random access. Assuming you're performing a search and modify on a
string, that limitation isn't a big deal, but you'll still need to
traverse the list in one form or another.

The overhead may be psychological in this day and age, but I think
you'll agree that one node per character is wasteful in terms of
space. Even if you use Unicode and a suitable type to represent
Unicode characters, we're still looking at approximately twice the
space for a link (either an integer index or a pointer) to an
"unbounded" linked list.

One can alleviate that waste by storing arrays of characters in each
node rather than a single character, but that increases the complexity
of the data structure, which means you're probably going to see a
performance hit. Whether that hit is significant would require
profiling, but even if it weren't, I'd say the benefit of a linked
list is no longer clear.

There are many ways of implementing a linked list, with suggests that
you're thinking of a different implementation than I. Perhaps you
could describe the implementation you're thinking of, where following
links is unnecessary and overhead is psychological?

Frankly, Julienne, I'm tired of the facility in which
ordinary garden-variety transform "the need to think" into "wasting
overhead" as if their brains == their computer.

I can't decide if you're insulting me or using my post to enable
attacks on your usual clc nemeses. Either way I think I'll simply
ignore it and focus on the topic at hand.

It appeared to me that Richard's "general purpose linked list" of 2000
copies the values of anything passed to it into nodes of the linked
list. But if I were (in a blue moon) to use his code to re-present
strings as linked list, then he'd copy unbounded amounts of data
inside his code.

Thank you. That's what I was thinking, but felt the need to ask for
clarification. Unfortunately I'm unable to comment further at this
time because C Unleashed isn't on my bookshelf at work.

 

[Chris M. Thomasson]

[...]

IMVHO, a linked-list amortized string implementation can get along fairly
well with a "large" amount of text. For instance, I would personally not
want to store the text that makes up a fairly verbose well-read novel in a
single NUL terminated string. Humm... You should probably break the massive
data apart into an amortized linked data-structure. Amortized in the sense
that multiple characters/whatever can exist on a per-node basis.

 

[Seebs]

IMVHO, a linked-list amortized string implementation can get along fairly
well with a "large" amount of text. For instance, I would personally not
want to store the text that makes up a fairly verbose well-read novel in a
single NUL terminated string. Humm... You should probably break the massive
data apart into an amortized linked data-structure. Amortized in the sense
that multiple characters/whatever can exist on a per-node basis.

Anyone planning to invent this would be well-served by studying the "mbufs"
in the BSD networking stack.

Not necessarily imitating, or using. But studying. They are a fairly
carefully-considered approach to the question of storing widely variable
amounts of data in a listish form, with some variance in the amount of data
in each node.

-s

 

[spinoza1111]

I observe that, like all fascists, you see the world in terms of black
and white. No - he was paid to do an adequate and workmanlike job,
taking data output from one program and changing it to be suitable to be
input by another. A few pages of code at most, and not worth
generalising since the whole suite was likely to be ditched within a
year or so.

We don't need "War and Peace" when the sixpenny paperback does the job
just as well.

The problem is that it's always like that. Management never wants to
invest enough.

The guy may have been a fool. But I regard these stories as primarily
myths, since in all probability you weren't any more qualified than he
to tell what was needed.

See above.



Gosh, US Corps can trigger earthquakes, eh? Marvellous, what will they
think of next?

Read history. Haiti was in permanent debt as a result of being forced
by the US, Britain and France to pay "reparations for slavery" AS THE
SLAVE SOCIETY in 1825: French pigs wanted to be compensated when in
1804, Haitiennes fought for and won their freedom...in a war which
forced Napoleon to sell what's now more than half the United States to
the USA in the Louisiana Purchase, which was greatly, that is, to the
United States' advantage. When in 1910 these debts overwhelmed Haiti,
the City Bank of New York (today Citicorp) forced Haiti to sell its
central bank at fire-sale prices.

The United States Marines were sent in 1915 by President Wilson to
handle the chaos that resulted from the poverty that resulted from
Citicorp's theft, and a US-friendly dictator (Duvalier) and his son
terrorized Haiti until the 1980s.

A popular leader (Aristide) who threatened to act in the interest of
Haiti's poor was overthrown by a Bush-sponsored coup in 2004 while the
USA was distracted by Iraq, and kidnapped by US Marines "for his own
protection" and taken to Africa.

The country collapsed in January as a result of two hundred years of
debt slavery and persecution by the "civilized" world for having the
balls to take the US Declaration of Independence and the French
"Declaration de Droites de l'Homme et Citoyen" seriously. A 7.0
earthquake in San Francisco in 1989 at the start of the World Series
killed only a few dozen people and destroyed no major structures,
because Californians HAD THE MONEY to build earthquake safe: that
magnitude in Haiti has killed uncounted numbers of people because of
the two hundred year bullying of Haiti for being a country of men who
freed themselves. Just as people who post here with grownup dignity
are targeted, in fact, the Haitiennes have been targeted. I hope they
swim to Florida and take over.

 

[spinoza1111]

They *would* have to follow the links unless there are fingers into
the list. One of the basic limitations of a linked list is a lack of
random access. Assuming you're performing a search and modify on a
string, that limitation isn't a big deal, but you'll still need to
traverse the list in one form or another.

That is correct, but the string manager can cache an index randomly in
the string.

The overhead may be psychological in this day and age, but I think
you'll agree that one node per character is wasteful in terms of
space. Even if you use Unicode and a suitable type to represent
Unicode characters, we're still looking at approximately twice the
space for a link (either an integer index or a pointer) to an
"unbounded" linked list.

Oops, perhaps I need to clarify. You would store the addresses of
blocks of characters in each node, that is, pointers to segments in
mallocated storage with a length code expressing the segment length
rather than a Nul in the segment. Putting characters in nodes would
make what I think was Richard Heathfield's mistake: a linked list as a
collection of actual squashed butterflies (a Lady Godey's Fairy Book)
and not photographs of (links to) data.

One can alleviate that waste by storing arrays of characters in each
node rather than a single character, but that increases the complexity

No no no no no. LINKS, please. A pointer to the segment in mallocated
space and its length.

of the data structure, which means you're probably going to see a
performance hit. Whether that hit is significant would require
profiling, but even if it weren't, I'd say the benefit of a linked
list is no longer clear.

My entire point was that Richard's approach is wrong. In fact, a
programmer with uni compsci would never have done what he did.

There are many ways of implementing a linked list, with suggests that
you're thinking of a different implementation than I. Perhaps you
could describe the implementation you're thinking of, where following
links is unnecessary and overhead is psychological?

struct linkedListNode
{
char * ptrToSegment; // Photograph of the Fairy, not the Fairy's
corpse
int segmentLength; // Who needs Nul? We don't need no steenking
Nul
struct linkedListNode * next; // Aargh a linked list ye be
};

I can't decide if you're insulting me or using my post to enable
attacks on your usual clc nemeses. Either way I think I'll simply
ignore it and focus on the topic at hand.

Neither. What concerns me is that in nearly all offices, a language
game is played that produces crumby software. Here, it's resistance to
good solutions which are hard for some to think about based on false
appeals to a misapprehension of "structured programming" and the false
inference from "it is difficult for me to think about this" to "this
must be an inefficient kludge".

And I reserve the right to answer the excessive bullying that occurs
in this newsgroup.

 

[Chris M. Thomasson]

Anyone planning to invent this would be well-served by studying the
"mbufs"
in the BSD networking stack.

Indeed. I also enjoy the well known intrusive list technique:
_______________________________________________________
struct node
{
struct node* next;
};


struct foo
{
struct node node;
/* [whatever] */
};


#define foo_from_node(n) ((struct foo*)(n))
_______________________________________________________




The Linux User/Kernel and Windows User/Kernel-space code is quite fond of
intrusive data-structures as well.

Not necessarily imitating, or using. But studying. They are a fairly
carefully-considered approach to the question of storing widely variable
amounts of data in a listish form, with some variance in the amount of
data
in each node.

Agreed.

 

[Malcolm McLean]

A 7.0
earthquake in San Francisco in 1989 at the start of the World Series
killed only a few dozen people and destroyed no major structures,
because Californians HAD THE MONEY to build earthquake safe:

You are absolutely right. Few if any Haitians died by act of God, but
because humans chose to build unstable structures, knowing that
earthquakes occasionally happen.

To put this back on topic, what's a professional Haitian architect to
do? Insisting on California-style structural standards would mean that
very few Haitians could afford to live in brick buildings.

 

[spinoza1111]

You are absolutely right. Few if any Haitians died by act of God, but
because humans chose to build unstable structures, knowing that
earthquakes occasionally happen.

To put this back on topic, what's a professional Haitian architect to
do? Insisting on California-style structural standards would mean that
very few Haitians could afford to live in brick buildings.

What is needed is to analyze Citicorp's current holdings in order to
trace what part are due to the fire sale price the City Bank of New
York (its former name) paid for Haiti's central bank in 1910, and then
force Citicorp, and all other banks unjustly enriched by the
reparations forced by France in 1825, to pay reparations for these
reparations, with a surcharge paid by French banks, and landowner
descendants for importing black Africans to Haiti in conditions of
slavery in the first place.

This would allow Haiti to rebuild itself adequately.

To stay on topic, this is something that could be done in part with
programming. But probably not in C, so it's not I admit on-topic. I
was replying to something I thought ignorant.

 

[Nick Keighley]

um, that's what links are for...

That is correct, but the string manager can cache an index randomly in
the string.

I've no idea what that means

Oops, perhaps I need to clarify. You would store the addresses of
blocks of characters in each node, that is, pointers to segments in
mallocated storage with a length code expressing the segment length
rather than a Nul in the segment. Putting characters in nodes would
make what I think was Richard Heathfield's mistake: a linked list as a
collection of actual squashed butterflies (a Lady Godey's Fairy Book)
and not photographs of (links to) data.

bizzare analogy.

So you're proposing a linked list of nodes each node containing a char
count and a pointer to a block of memory containing the actual chars.
Probably ok for some applications. Text editor? Bit heavy for small
strings.

No no no no no. LINKS, please. A pointer to the segment in mallocated
space and its length.

why so insistent? Whats wrong with variable sized nodes?


struct Node
{
struct Node *next;
int count;
char data [1];
};

then use "the struct hack" to allocate the memory

struct Node* make_node (char *c_str)
{
int size = strlen (c_str);
Node *new_node = malloc (sizeof(struct Node) + size - 1);
new_node->next = NULL;
new_node->count = size;
memcpy (new_node->data, c_str, size);
return new_node;
}

error checking ommitted. Untested code.

[note: there is a modified version of this function later on]

My entire point was that Richard's approach is wrong. In fact, a
programmer with uni compsci would never have done what he did.

I'll have to read C Unleashed but I doubt you're right.

struct linkedListNode
{
    char * ptrToSegment; // Photograph of the Fairy, not the Fairy's
corpse
    int segmentLength;   // Who needs Nul? We don't need no steenking
Nul
    struct linkedListNode * next; // Aargh a linked list ye be

};

and why wouldn't that link be followed. I've got a linked list and I
need to skip to the 196th character. I need to follow the chain of
links.



I'm still not clear how your version avoids the copying. Ah my above
code would look more like

struct Node* make_node (char *c_str)
{
int size = strlen (c_str);
Node *new_node = malloc (sizeof(struct Node) + size - 1);
new_node->next = NULL;
new_node->count = size;
new_node->data = c_str;
return new_node;
}

I suppose it depends where your strings come from. Again this would be
ok-ish for a text editor. The data comes from a file (the original
text) or user input (the edits)

 

[Malcolm McLean]

I've no idea what that means

With a canonical linked list, one must always start traversing the
list at the head, and continue following links until one has got the
data one wants.

However it's possible to store additional pointers to points along the
list. So, for instance, if we have a linked list of 1000 entries, we
could have extra pointers at 100, 200, 300 and so on. To get to link
202, one simply checks the extra pointers (two comparisons), jumps
into the list at node 200, and carries along to 202 (3 comparisons),
thous retrieving the information in 5 comparisons instead of 203.

 

[spinoza1111]

What management may or may not want to do in general is neither here nor
there, like most of your observations. In this particular instance,
management wanted to invest just the right amount, but got something
they hadn't asked for and that was pretty useless once the guy had left.

But it worked, you say below. My suspicion is that it became "useless"
because you and your mates were unwilling and unable to maintain it,
and this may be because it was crap (in which case the original
programmer is to blame), over your heads (in which case the original
programmer is partly to blame) or an excellent piece of code (in which
case, you're to blame).

Oh, "in all probability", eh? You have evidence to support this, do you?
(other then your usual b/s, I mean).

The guy was not a fool and his product worked. But the fact that it
needed him to make any modifications and turned into a black box once he
left, is proof enough that I was perfectly qualified to tell better that
he what was needed.

That may be the case. But given what appears to me to be a VERY low
level of skill on the part of the somewhat random selection of
programmers who post here, the program the guy wrote may have been
"too difficult to maintain" not as an inherent property, but because
you were unable/unwilling to maintain it.

His intention seems to have been to make it more easy to maintain by
writing a sort of "conversion compiler". Sometimes such tools are more
trouble than they are worth, because to use them you have to learn
what some clown's ideas of what a "language for file conversion" is.

Other times, however, corporate programmers merely have a learning
disorder or mental block when it comes to being able to connect with
program texts in a different style, and simply refuse to learn a
program written in a different style or with a different approach from
their favorite styles and approaches, for the same reason I've stated
elsethread: they self-selected into programming because they had
reading difficulties, especially in reading literature.

For the same reason they resented having to read Shakespeare in high
school to pass a class, they resent some pretentious ponce writing
code in an unfamiliar way. The pretentious ponce may be another
Shakespeare, or in actuality a pretentious ponce, but more usually
from a statistical perspective alone he's probably somewhere in
between.

Did you in fact envy his creativity and skill? And does not the
corporate way discourage dependence on creativity and skill?

If there was only one good way to convert the file, then the guy was
either a pretentious ponce or overqualified. If however he saw
something you did not, then he was a "genius". The truth is probably
somewhere in between.

Yes, I know about this thanks very much. But any society having an
earthquake like they had would be buggered, US Corps or not.

No again. Again, the San Francisco Bay area had a Richter 7.0 scale
earthquake at the start of the World Series in 1989, and casualties
and damage were minimal.

 

[spinoza1111]

Are we reinventing the weal?
Yes.

http://www.sgi.com/tech/stl/Rope.html

Greets