Breaking a node of link list

[Nehil]

i've following union

union header
{
struct
{
unsigned int size;
union header *next;
}s;

long x;
}

typedef union header Header;

i use Header as follows :
Header *ptr_free = (Header *)sbrk(4096);
Header *ptr_alloc = NULL;

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

Now, ptr_free has size = 4096 bytes,

i want to break this node ( ptr_free ) into two nodes :
one is pointed by ptr_alloc and the remaining part by ptr_free. and in
each pointer the size must be maintained.

How can i do it??
plz give me a hint.

[Walter Roberson]

In article <11*********************@r34g2000hsd.googlegroups. com>,
Nehil <ne***********@gmail.comwrote:

>i've following union

>union header
{
struct
{
unsigned int size;
union header *next;
}s;
long x;
}

>typedef union header Header;

>i use Header as follows :
Header *ptr_free = (Header *)sbrk(4096);
Header *ptr_alloc = NULL;

>Now, ptr_free has size = 4096 bytes,

It does??

Quoting from the Linux 2.4 sbrk() man page:

brk and sbrk are not defined in the C Standard and are deliberately
excluded from the POSIX.1 standard (see paragraphs B.1.1.1.3 and
B.8.3.3)

So here in comp.lang.c we don't know what the heck sbrk(4096) does.
And what it does might vary between different systems (that bother
to implement it at all) and between different versions of the same system.
So if your question depends upon some particular result being
returned by sbrk() then you need to take the question to a newsgroup
that deals with the OS or OSes that you need this to be portable to.

>i want to break this node ( ptr_free ) into two nodes :
one is pointed by ptr_alloc and the remaining part by ptr_free. and in
each pointer the size must be maintained.

>How can i do it??
plz give me a hint.

No can do unless you are the implementor of the processor architecture.
There are very few systems in which a pointer contains a size
*within the pointer itself* -- it would require a pointer representation
wider than the number of bits required to describe the largest object
size pointed to, and you would get wacky pointer semantics if you
did pointer arithmetic (and remember that pointer arithmetic must
be reversable...).

It would be possible to maintain the size of the nodes at the
location pointed *to*, but not practical in the pointer -itself-
("and in each pointer the size must be maintained").

Your union header has a size field, but you seem to be lacking
a field for the remaining storage in the node. Of course you have
a semantic problem in defining the type for that storage if you
are working in C89; in C99 you could type it as a VLA (Variable
Length Array).
--
I was very young in those days, but I was also rather dim.
-- Christopher Priest

[Nehil]

On Jul 12, 9:39 pm, [e-mail] (Walter Roberson)
wrote:

In article <[e-mail]. com>,

Nehil <[e-mail]:

i've following union
union header
{
struct
{
unsigned int size;
union header *next;
}s;
long x;
}
typedef union header Header;
i use Header as follows :
Header *ptr_free = (Header *)sbrk(4096);
Header *ptr_alloc = NULL;
Now, ptr_free has size = 4096 bytes,

It does??

Quoting from the Linux 2.4 sbrk() man page:

brk and sbrk are not defined in the C Standard and are deliberately
excluded from the POSIX.1 standard (see paragraphs B.1.1.1.3 and
B.8.3.3)

So here in comp.lang.c we don't know what the heck sbrk(4096) does.
And what it does might vary between different systems (that bother
to implement it at all) and between different versions of the same system.
So if your question depends upon some particular result being
returned by sbrk() then you need to take the question to a newsgroup
that deals with the OS or OSes that you need this to be portable to.

i want to break this node ( ptr_free ) into two nodes :
one is pointed by ptr_alloc and the remaining part by ptr_free. and in
each pointer the size must be maintained.
How can i do it??
plz give me a hint.

No can do unless you are the implementor of the processor architecture.
There are very few systems in which a pointer contains a size
*within the pointer itself* -- it would require a pointer representation
wider than the number of bits required to describe the largest object
size pointed to, and you would get wacky pointer semantics if you
did pointer arithmetic (and remember that pointer arithmetic must
be reversable...).

It would be possible to maintain the size of the nodes at the
location pointed *to*, but not practical in the pointer -itself-
("and in each pointer the size must be maintained").

Your union header has a size field, but you seem to be lacking
a field for the remaining storage in the node. Of course you have
a semantic problem in defining the type for that storage if you
are working in C89; in C99 you could type it as a VLA (Variable
Length Array).
--
I was very young in those days, but I was also rather dim.
-- Christopher Priest

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

well, i agree that sbrk(int) is implementation defined, but don't u
think malloc must be using *something* like sbrk or brk to request the
memory chunk from OS.

or

do u know some poratble way of taking memory from OS? please tell me.

Now, let say i have a link list as follows :

header-->NODE1 =NODE2 =NODE3 =NODE4 =NULL

is there any way to merge the two nodes or to break a node in two
parts?

Please clarify.
Thanks.

[santosh]

Nehil wrote:

On Jul 12, 9:39 pm, [e-mail] (Walter Roberson) wrote:

In article <[e-mail]. com>,
Nehil <[e-mail]:

>
>i've following union
>union header
>{
struct
{
unsigned int size;
union header *next;
}s;
long x;
>}
>typedef union header Header;
>i use Header as follows :
Header *ptr_free = (Header *)sbrk(4096);
Header *ptr_alloc = NULL;
>Now, ptr_free has size = 4096 bytes,

It does??

Quoting from the Linux 2.4 sbrk() man page:

brk and sbrk are not defined in the C Standard and are deliberately
excluded from the POSIX.1 standard (see paragraphs B.1.1.1.3 and
B.8.3.3)

So here in comp.lang.c we don't know what the heck sbrk(4096) does.
And what it does might vary between different systems (that bother
to implement it at all) and between different versions of the same system.
So if your question depends upon some particular result being
returned by sbrk() then you need to take the question to a newsgroup
that deals with the OS or OSes that you need this to be portable to.

<snip>

well, i agree that sbrk(int) is implementation defined, but don't u
think malloc must be using *something* like sbrk or brk to request the
memory chunk from OS.

Not necessarily. There are situations where a host operating system
might not exist at all. In such cases malloc and friends would
presumably use system memory directly.

But the point is, whatever method malloc uses is system specific. C
runs on a huge variety of systems and hence it would not be feasible
for this group to discuss the details of all these systems. Hence only
Standard C is discussed here. Most major target platforms for C have
their own dedicated group, as do most major C compilers.

or

do u know some poratble way of taking memory from OS? please tell me.

Use malloc or calloc or realloc. Use free to deallocate.

Now, let say i have a link list as follows :

header-->NODE1 =NODE2 =NODE3 =NODE4 =NULL

is there any way to merge the two nodes or to break a node in two
parts?

Why do you need to do this? Nodes may exist at different memory
locations. What is it that you're doing that calls for "breaking" a
node or merging them?

[santosh]

Nehil wrote:

i've following union

union header
{
struct
{
unsigned int size;
union header *next;
}s;

long x;
}

typedef union header Header;

i use Header as follows :
Header *ptr_free = (Header *)sbrk(4096);
Header *ptr_alloc = NULL;

Now, ptr_free has size = 4096 bytes,

i want to break this node ( ptr_free ) into two nodes :
one is pointed by ptr_alloc and the remaining part by ptr_free. and in
each pointer the size must be maintained.

You cannot store sizes within pointers in Standard C. What you can do
is set ptr_free and ptr_alloc to point to the appropriate offsets
within the node and store the sizes is seperate variables. You could
encapsulate the pointer and it's associated size variable into a
structure. You can use the offsetof operator to get the offset of the
member where you want to "break" the node.

Why do you want to do this. This is probably going to be non-portable,
particularly if you try to access the separate parts of the union.

[Nehil]

On Jul 12, 11:45 pm, santosh <[e-mail]:

Nehil wrote:

i've following union

union header
{
struct
{
unsigned int size;
union header *next;
}s;

long x;
}

typedef union header Header;

i use Header as follows :
Header *ptr_free = (Header *)sbrk(4096);
Header *ptr_alloc = NULL;

Now, ptr_free has size = 4096 bytes,

i want to break this node ( ptr_free ) into two nodes :
one is pointed by ptr_alloc and the remaining part by ptr_free. and in
each pointer the size must be maintained.

You cannot store sizes within pointers in Standard C. What you can do
is set ptr_free and ptr_alloc to point to the appropriate offsets
within the node and store the sizes is seperate variables. You could
encapsulate the pointer and it's associated size variable into a
structure. You can use the offsetof operator to get the offset of the
member where you want to "break" the node.

Why do you want to do this. This is probably going to be non-portable,
particularly if you try to access the separate parts of the union.

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

I've the following requirement :

i'm developing a Garbage Collector for C. so i'd do develop a complete
memory manager ie i'd to allocate and de-allocate. for allocation i'm
using sbrk(int mem).
acc. to man page it returns a void pointer to the memory chunk of mem
bytes. but actually it is returning a void pointer to a memory chunk
of 4kb (4096 bytes).
if the argument of sbrk is in between 1 and 4096 (including both ends)
the size of the chunk returned will be 4096 bytes.

Now, at the start of program this whole chunk can be treated as a free
block of memery. so i do as follows :

Header *ptr_free = (Header *)sbrk(4096);
Header *ptr_alloc = NULL;

when, user requests for memory of certain bytes, let say 20 byets. so
i do as follows : (i'm considering only the very 1st request)

ptr_alloc = ptr_free;
ptr_free = ptr_free + 20 + sizeof(Header);
void *memory = ptr_alloc + sizeof(Header);
return memory;

i.e. ptr_free is now pointing to the start of un-allocated part of
that big chunk. and memory points to the allocated part, but leaves
the starting header.

Now, ptr_free should have size of "rest of the block". but it is a
single node so it's not possible. plz correct me if i'm wrong.
To keep the record of free blocks i need to break the big chunk into
parts : Allocated and Free.
How can i break the node into two parts so that it can have size
information for allocated and free parts.

Hope u understand my question and problem. :-)
Thanks.

[Walter Roberson]

In article <11**********************@22g2000hsm.googlegroups. com>,
Nehil <ne***********@gmail.comwrote:

>I've the following requirement :

>i'm developing a Garbage Collector for C. so i'd do develop a complete
memory manager ie i'd to allocate and de-allocate. for allocation i'm
using sbrk(int mem).

I am not clear what your portability requirements are? A number
of pointer operations which are formally unspecified or undefined
behaviour in C are well defined and simple if you are allowed to
assume particular operating environments -- but can be a large
large nuisance if you are trying to work portably.

>acc. to man page it returns a void pointer to the memory chunk of mem
bytes. but actually it is returning a void pointer to a memory chunk
of 4kb (4096 bytes).

I'd like to emphasize that sbrk() is not considered portable,
being not a part of C nor of POSIX.1. It is part of the
Single Unix Specification Version 2, but there are still quite
a number of useful Unix operating systems which are not certified
to Version 2 of the SUS. Even the SUS lists them as LEGACY and says,
"The use of malloc() is now preferred because it can be used
portably with all other memory allocation functions and with any
function that uses other allocation functions."

http://www.opengroup.org/onlinepubs/...9/xsh/brk.html

"It is unspecified whether the pointer returned by sbrk() is
aligned suitably for any purpose."

Which is equivilent to a flaming red arrow saying THIS IS NOT PORTABLE.

>Now, at the start of program this whole chunk can be treated as a free
block of memery. so i do as follows :

Header *ptr_free = (Header *)sbrk(4096);
Header *ptr_alloc = NULL;

>when, user requests for memory of certain bytes, let say 20 byets. so
i do as follows : (i'm considering only the very 1st request)

And if the user requests 4096 - sizeof(struct header) or more,
you have problems. The memory your allocation routines hands over
to the users must be consequative, so you cannot hand over multiple
chunks each with an embedded header.

>ptr_alloc = ptr_free;
ptr_free = ptr_free + 20 + sizeof(Header);
void *memory = ptr_alloc + sizeof(Header);
return memory;

>i.e. ptr_free is now pointing to the start of un-allocated part of
that big chunk. and memory points to the allocated part, but leaves
the starting header.

>Now, ptr_free should have size of "rest of the block". but it is a
single node so it's not possible. plz correct me if i'm wrong.
To keep the record of free blocks i need to break the big chunk into
parts : Allocated and Free.
How can i break the node into two parts so that it can have size
information for allocated and free parts.

If you do not have enough C experience to figure this out on your
own (and it is not difficult) then you do not have enough C experience
to implement a garbage collector. This bit is trivial compared to
figuring out whether a particular block of memory is still in
use or not!
--
Programming is what happens while you're busy making other plans.