By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
459,725 Members | 1,094 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 459,725 IT Pros & Developers. It's quick & easy.

User implementable standard library functions

P: n/a
One interesting thing to come out of the recent "Alignment" thread is
that it is impossible to write a portable replacement for malloc in
"user space" (not sure what the right term is - I mean an ordinary
programmer, not an implementor) - even a naive method using a large
array isn't guaranteed to work if there's no way of having a variable
of strictest alignment. Oh, for the sake of the pedants, let's
discount
void *my_malloc(size_t size) { return 0; }
:)

Of course, for most standard library functions, say something like
strlen, it's perfectly possible to provide a completely equivalent
implementation yourself.

So as an academic exercise, which other standard library functions
share the same property as malloc, that the ordinary programmer is
powerless to write an equivalent function without dipping into non-
Standard implementation details?

Aug 21 '07 #1
Share this Question
Share on Google+
31 Replies


P: n/a
Fr************@googlemail.com wrote, On 21/08/07 23:50:
One interesting thing to come out of the recent "Alignment" thread is
that it is impossible to write a portable replacement for malloc in
"user space" (not sure what the right term is - I mean an ordinary
programmer, not an implementor) - even a naive method using a large
array isn't guaranteed to work if there's no way of having a variable
of strictest alignment. Oh, for the sake of the pedants, let's
discount
void *my_malloc(size_t size) { return 0; }
:)

Of course, for most standard library functions, say something like
strlen, it's perfectly possible to provide a completely equivalent
implementation yourself.

So as an academic exercise, which other standard library functions
share the same property as malloc, that the ordinary programmer is
powerless to write an equivalent function without dipping into non-
Standard implementation details?
free, fopen, fclose (you can implement getc using fgetc or the other war
around ;-)), signal, remove, rename, abort, offsetof (OK, so it's a
macro) to name just a few. I'm assuming ignoring implementations that
always fail just as you did.
--
Flash Gordon
Aug 21 '07 #2

P: n/a
Fr************@googlemail.com wrote:
>
One interesting thing to come out of the recent "Alignment" thread is
that it is impossible to write a portable replacement for malloc in
"user space" (not sure what the right term is - I mean an ordinary
programmer, not an implementor) - even a naive method using a large
array isn't guaranteed to work if there's no way of having a variable
of strictest alignment. Oh, for the sake of the pedants, let's
discount
void *my_malloc(size_t size) { return 0; }
:)

Of course, for most standard library functions, say something like
strlen, it's perfectly possible to provide a completely equivalent
implementation yourself.

So as an academic exercise, which other standard library functions
share the same property as malloc, that the ordinary programmer is
powerless to write an equivalent function without dipping into non-
Standard implementation details?
I don't know, but I have a toy C library here:

http://www.mindspring.com/~pfilandr/C/library/

--
pete
Aug 21 '07 #3

P: n/a
Fr************@googlemail.com wrote:
One interesting thing to come out of the recent "Alignment" thread is
that it is impossible to write a portable replacement for malloc in
"user space" (not sure what the right term is - I mean an ordinary
programmer, not an implementor) - even a naive method using a large
array isn't guaranteed to work if there's no way of having a variable
of strictest alignment. Oh, for the sake of the pedants, let's
discount
void *my_malloc(size_t size) { return 0; }
:)

Of course, for most standard library functions, say something like
strlen, it's perfectly possible to provide a completely equivalent
implementation yourself.

So as an academic exercise, which other standard library functions
share the same property as malloc, that the ordinary programmer is
powerless to write an equivalent function without dipping into non-
Standard implementation details?
From the top of my head:

free, fopen, fclose, freopen, fread, fwrite, fgetc, exit, signal, raise, the
is* character test functions, perror, sterror, locale functions,
setjmp/longjmp, fflush, remove, tmpfile, abort, system, the va_* macros,
time functions.

Aug 22 '07 #4

P: n/a
santosh wrote:
>
Fr************@googlemail.com wrote:
One interesting thing to come out of the recent
"Alignment" thread is
that it is impossible to write a portable replacement for malloc in
"user space" (not sure what the right term is - I mean an ordinary
programmer, not an implementor) - even a naive method using a large
array isn't guaranteed to work
if there's no way of having a variable
of strictest alignment. Oh, for the sake of the pedants, let's
discount
void *my_malloc(size_t size) { return 0; }
:)

Of course, for most standard library functions, say something like
strlen, it's perfectly possible to provide a completely equivalent
implementation yourself.

So as an academic exercise, which other standard library functions
share the same property as malloc, that the ordinary programmer is
powerless to write an equivalent function without dipping into non-
Standard implementation details?

From the top of my head:

free, fopen, fclose, freopen, fread, fwrite,
fgetc, exit, signal, raise, the
is* character test functions,
isdigit can be implemented.
It is not locale dependent.
perror, sterror, locale functions,
setjmp/longjmp, fflush, remove, tmpfile, abort, system,
the va_* macros, time functions.
--
pete
Aug 22 '07 #5

P: n/a
pete said:
santosh wrote:
>>
Fr************@googlemail.com wrote:
<snip>
So as an academic exercise, which other standard library functions
share the same property as malloc, that the ordinary programmer is
powerless to write an equivalent function without dipping into non-
Standard implementation details?

From the top of my head:

free, fopen, fclose, freopen, fread, fwrite,
fgetc, exit, signal, raise, the
is* character test functions,

isdigit can be implemented.
It is not locale dependent.
The same applies to isxdigit, and (without looking it up) probably
isspace - and perhaps one or two others in the same vein.
>perror, sterror, locale functions,
setjmp/longjmp, fflush, remove, tmpfile, abort, system,
the va_* macros, time functions.
I suspect that strftime can be implemented portably.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Aug 22 '07 #6

P: n/a

<Fr************@googlemail.comwrote in message
news:11**********************@x35g2000prf.googlegr oups.com...
One interesting thing to come out of the recent "Alignment" thread is
that it is impossible to write a portable replacement for malloc in
"user space" (not sure what the right term is - I mean an ordinary
programmer, not an implementor) - even a naive method using a large
array isn't guaranteed to work if there's no way of having a variable
of strictest alignment. Oh, for the sake of the pedants, let's
discount
void *my_malloc(size_t size) { return 0; }
:)
well, yes we can, if we grab the original memory from malloc that is...
of course, then for example, I detect linux, and go over to using mmap
instead (for some things, this is needed...).

this is often what I do in my allocators at least...

this often works well for specialized allocators and for garbage collectors.
likewise for wrapping other functionality (such as stdio and posix calls) in
the name of yet more features (a VFS system and being able to mount zipfiles
as part of the directory tree...).

maybe not the same, oh well...

Of course, for most standard library functions, say something like
strlen, it's perfectly possible to provide a completely equivalent
implementation yourself.

So as an academic exercise, which other standard library functions
share the same property as malloc, that the ordinary programmer is
powerless to write an equivalent function without dipping into non-
Standard implementation details?
there are lots.

of course, I am not exactly staying in standards land either for that
matter...

I have my own runtime C compiler hack-job linking against statically
compiled parts of the app, and then I go off and implement some blatently
non-standard compiler extensions (geometric vectors and quaternions as
built-in types, among other things...).

works, does what I want, if albeit one has to choose their targets carefully
(currently working on mingw and windows on x86, and, errm...). well, apart
from a few things (not completed yet), my compiler-core should be almost
workable on linux x86-64...

ok, x86 windows is my main target...

Aug 22 '07 #7

P: n/a
cr88192 wrote:
>
<Fr************@googlemail.comwrote in message
news:11**********************@x35g2000prf.googlegr oups.com...
One interesting thing to come out of the recent "Alignment" thread is
that it is impossible to write a portable replacement for malloc in
"user space" (not sure what the right term is - I mean an ordinary
programmer, not an implementor) - even a naive method using a large
array isn't guaranteed to work if there's no way of having a variable
of strictest alignment. Oh, for the sake of the pedants, let's
discount
void *my_malloc(size_t size) { return 0; }
:)

well, yes we can, if we grab the original memory from malloc that is...
of course, then for example, I detect linux, and go over to using mmap
instead (for some things, this is needed...).
How do you portably guarantee proper alignment?

[...]

--
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody | www.hvcomputer.com | #include |
| kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h|
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:Th*************@gmail.com>

Aug 22 '07 #8

P: n/a
On Aug 22, 10:16 am, santosh <santosh....@gmail.comwrote:
Francine.Ne...@googlemail.com wrote:
One interesting thing to come out of the recent "Alignment" thread is
that it is impossible to write a portable replacement for malloc in
"user space" (not sure what the right term is - I mean an ordinary
programmer, not an implementor) - even a naive method using a large
array isn't guaranteed to work if there's no way of having a variable
of strictest alignment. Oh, for the sake of the pedants, let's
discount
void *my_malloc(size_t size) { return 0; }
:)
Of course, for most standard library functions, say something like
strlen, it's perfectly possible to provide a completely equivalent
implementation yourself.
So as an academic exercise, which other standard library functions
share the same property as malloc, that the ordinary programmer is
powerless to write an equivalent function without dipping into non-
Standard implementation details?

From the top of my head:

free, fopen, fclose, freopen, fread, fwrite, fgetc, exit, signal, raise, the
is* character test functions, perror, sterror, locale functions,
You mean strerror.
setjmp/longjmp, fflush, remove, tmpfile, abort, system, the va_* macros,
time functions.

Aug 22 '07 #9

P: n/a
santosh wrote:
Fr************@googlemail.com wrote:
>One interesting thing to come out of the recent "Alignment" thread is
that it is impossible to write a portable replacement for malloc in
"user space" (not sure what the right term is - I mean an ordinary
programmer, not an implementor) - even a naive method using a large
array isn't guaranteed to work if there's no way of having a variable
of strictest alignment. Oh, for the sake of the pedants, let's
discount
void *my_malloc(size_t size) { return 0; }
:)

Of course, for most standard library functions, say something like
strlen, it's perfectly possible to provide a completely equivalent
implementation yourself.

So as an academic exercise, which other standard library functions
share the same property as malloc, that the ordinary programmer is
powerless to write an equivalent function without dipping into non-
Standard implementation details?

From the top of my head:

free, fopen, fclose, freopen, fread, fwrite, fgetc, exit, signal, raise,
the is* character test functions, perror, sterror, locale functions,
setjmp/longjmp, fflush, remove, tmpfile, abort, system, the va_* macros,
time functions.
fread/fwrite can be implemented portably by calling to fgetc/fputc, or
fgetc/fputc can be implemented portably by calling fread/fwrite; whichever
you choose, you can cross one pair off of your list. (You included fgetc
but not fputc; I'm assuming that was an oversight.)

In addition to the functions you listed, most of the floating point math
functions are notable in that they can be implemented portably, but cannot
be implemented portably in a way that's likely to actually be useful.
Aug 22 '07 #10

P: n/a
Kenneth Brody wrote:
cr88192 wrote:
.... snip ...
>>
well, yes we can, if we grab the original memory from malloc that
is... of course, then for example, I detect linux, and go over to
using mmap instead (for some things, this is needed...).

How do you portably guarantee proper alignment?
You don't. You can't. You use malloc or declare variables..

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

--
Posted via a free Usenet account from http://www.teranews.com

Aug 22 '07 #11

P: n/a
Harald van =?UTF-8?B?RMSzaw==?= wrote:
>
santosh wrote:
Fr************@googlemail.com wrote:
One interesting thing to come out of the recent "Alignment" thread is
that it is impossible to write a portable replacement for malloc in
"user space" (not sure what the right term is - I mean an ordinary
programmer, not an implementor) - even a naive method using a large
array isn't guaranteed to work if there's no way of having a variable
of strictest alignment. Oh, for the sake of the pedants, let's
discount
void *my_malloc(size_t size) { return 0; }
:)

Of course, for most standard library functions, say something like
strlen, it's perfectly possible to provide a completely equivalent
implementation yourself.

So as an academic exercise, which other standard library functions
share the same property as malloc, that the ordinary programmer is
powerless to write an equivalent function without dipping into non-
Standard implementation details?
From the top of my head:

free, fopen, fclose, freopen, fread, fwrite, fgetc,
exit, signal, raise,
the is* character test functions, perror, sterror, locale functions,
setjmp/longjmp, fflush, remove, tmpfile, abort, system,
the va_* macros,
time functions.

fread/fwrite can be implemented portably by calling to fgetc/fputc, or
fgetc/fputc can be implemented portably by calling fread/fwrite;
fgetc and fputc are much easier to implement than that:

#include <stdio.h>

int fputc(int c, FILE *stream)
{
return putc(c, stream);
}

int fgetc(FILE *stream)
{
return getc(stream);
}

--
pete
Aug 22 '07 #12

P: n/a

"Kenneth Brody" <ke******@spamcop.netwrote in message
news:46***************@spamcop.net...
cr88192 wrote:
>>
<Fr************@googlemail.comwrote in message
news:11**********************@x35g2000prf.googleg roups.com...
One interesting thing to come out of the recent "Alignment" thread is
that it is impossible to write a portable replacement for malloc in
"user space" (not sure what the right term is - I mean an ordinary
programmer, not an implementor) - even a naive method using a large
array isn't guaranteed to work if there's no way of having a variable
of strictest alignment. Oh, for the sake of the pedants, let's
discount
void *my_malloc(size_t size) { return 0; }
:)

well, yes we can, if we grab the original memory from malloc that is...
of course, then for example, I detect linux, and go over to using mmap
instead (for some things, this is needed...).

How do you portably guarantee proper alignment?
if grabbed from malloc, it is aligned to whatever malloc's alignment is (on
x86 and friends, usually at least 8 or 16 I think...).

and, if from mmap, it is aligned to a page boundary.
now, aligning memory, well this depends on the type sizes, ...

a general option is this (should work on windows-32 bit, linux, and linux
x86-64, and maybe a few others):
p=(void *)((((long)p)+15)&(~15)); //aligns to a 16 byte boundary

for other cases, it should be mostly tweaking...

Aug 22 '07 #13

P: n/a
"cr88192" <cr*****@hotmail.comwrites:
"Kenneth Brody" <ke******@spamcop.netwrote in message
news:46***************@spamcop.net...
[...]
>How do you portably guarantee proper alignment?

if grabbed from malloc, it is aligned to whatever malloc's alignment
is (on x86 and friends, usually at least 8 or 16 I think...).

and, if from mmap, it is aligned to a page boundary.
mmap is not portable.
>
now, aligning memory, well this depends on the type sizes, ...

a general option is this (should work on windows-32 bit, linux, and linux
x86-64, and maybe a few others):
p=(void *)((((long)p)+15)&(~15)); //aligns to a 16 byte boundary
No, this is not guaranteed to work. The result of converting of a
pointer to an integer or vice versa is implementation-defined. It's
also not guaranteed that 'long' is wide enough to hold a pointer
value. Even if it is, the result could easily be negative; using
'unsigned long' would avoid that problem, but not the others.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Aug 23 '07 #14

P: n/a

"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...
"cr88192" <cr*****@hotmail.comwrites:
>"Kenneth Brody" <ke******@spamcop.netwrote in message
news:46***************@spamcop.net...
[...]
>>How do you portably guarantee proper alignment?

if grabbed from malloc, it is aligned to whatever malloc's alignment
is (on x86 and friends, usually at least 8 or 16 I think...).

and, if from mmap, it is aligned to a page boundary.

mmap is not portable.
it exists on linux...
good enough for if running on linux, just have to detect and use.

ifdef powers, ifdef fixes everything...
hell, even chunks of inline assember and w32api calls can be made 'portable'
using ifdef (if by portable, one means, not included except on their
specific targets...).

likewise, going and opening the EXE and ripping out the symbol table is not
portable either, but can be done in portable projects via the powers of
ifdef...

>>
now, aligning memory, well this depends on the type sizes, ...

a general option is this (should work on windows-32 bit, linux, and linux
x86-64, and maybe a few others):
p=(void *)((((long)p)+15)&(~15)); //aligns to a 16 byte boundary

No, this is not guaranteed to work. The result of converting of a
pointer to an integer or vice versa is implementation-defined. It's
also not guaranteed that 'long' is wide enough to hold a pointer
value. Even if it is, the result could easily be negative; using
'unsigned long' would avoid that problem, but not the others.
I didn't say it was gueranteed to work, or even all that portable, only that
it works on x86 and friends in the compilers most people are likely to use
(gcc and msvc...).

also note that on x86-64, pointers are signed, so 'long' (or 'long long', if
win-x64 is a possibility) is a good option.

my case:
I usually detect, using 'int' on x86 and 'long long' on x86-64.

--
Keith Thompson (The_Other_Keith) ks***@mib.org
<http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*>
<http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Aug 23 '07 #15

P: n/a
cr88192 wrote:
"Keith Thompson" <ks***@mib.orgwrote in message
>"cr88192" <cr*****@hotmail.comwrites:
>>"Kenneth Brody" <ke******@spamcop.netwrote in message
[...]
>>>How do you portably guarantee proper alignment?

if grabbed from malloc, it is aligned to whatever malloc's
alignment is (on x86 and friends, usually at least 8 or 16 I
think...).

and, if from mmap, it is aligned to a page boundary.

mmap is not portable.

it exists on linux...
good enough for if running on linux, just have to detect and use.
But not good enough for c.l.c, which discusses the C language, as
defined by the C standard and historical standards. If you want to
discuss mmap, post its complete code, written in purely standard
C. Otherwise it is off-topic.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

--
Posted via a free Usenet account from http://www.teranews.com

Aug 23 '07 #16

P: n/a
"cr88192" <cr*****@hotmail.comwrites:
"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...
>"cr88192" <cr*****@hotmail.comwrites:
>>"Kenneth Brody" <ke******@spamcop.netwrote in message
news:46***************@spamcop.net...
[...]
>>>How do you portably guarantee proper alignment?

if grabbed from malloc, it is aligned to whatever malloc's alignment
is (on x86 and friends, usually at least 8 or 16 I think...).

and, if from mmap, it is aligned to a page boundary.

mmap is not portable.

it exists on linux...
good enough for if running on linux, just have to detect and use.
That's irrelevant here in comp.lang.c.
ifdef powers, ifdef fixes everything...
Hardly. If mmap isn't supported, you still have to find some
alternative.

[...]
>>now, aligning memory, well this depends on the type sizes, ...

a general option is this (should work on windows-32 bit, linux, and linux
x86-64, and maybe a few others):
p=(void *)((((long)p)+15)&(~15)); //aligns to a 16 byte boundary

No, this is not guaranteed to work. The result of converting of a
pointer to an integer or vice versa is implementation-defined. It's
also not guaranteed that 'long' is wide enough to hold a pointer
value. Even if it is, the result could easily be negative; using
'unsigned long' would avoid that problem, but not the others.

I didn't say it was gueranteed to work, or even all that portable, only that
it works on x86 and friends in the compilers most people are likely to use
(gcc and msvc...).
Again, that's not particularly relevant here.
also note that on x86-64, pointers are signed, so 'long' (or 'long long', if
win-x64 is a possibility) is a good option.
It depends on what you want to do with the converted result. I don't
use bitwise operators on signed integers, and I don't remember what
(blah+15)&(~15) does if blah is signed and has a negative value.
my case:
I usually detect, using 'int' on x86 and 'long long' on x86-64.
If you have <stdint.h>, you can use intptr_t or uintptr_t (if they
exists). If you don't, I'll mention that I've never used a system on
which different pointer types have different sizes, or on which
sizeof(void*) ! sizeof(long). Neither assumption is guaranteed, of
course, and I have no doubt that systems exist that violate them.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Aug 23 '07 #17

P: n/a

"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...
"cr88192" <cr*****@hotmail.comwrites:
>"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...
>>"cr88192" <cr*****@hotmail.comwrites:
"Kenneth Brody" <ke******@spamcop.netwrote in message
news:46***************@spamcop.net...
[...]
How do you portably guarantee proper alignment?

if grabbed from malloc, it is aligned to whatever malloc's alignment
is (on x86 and friends, usually at least 8 or 16 I think...).

and, if from mmap, it is aligned to a page boundary.

mmap is not portable.

it exists on linux...
good enough for if running on linux, just have to detect and use.

That's irrelevant here in comp.lang.c.
but is relevant for actual coding, where most non-trivial code ends up
having to deal with the underlying implementation in one non-standard way or
another...

unless you mean to say: c.l.c is only for theory, not for actual practice...

>ifdef powers, ifdef fixes everything...

Hardly. If mmap isn't supported, you still have to find some
alternative.
on windows, I use malloc.

on linux, mmap offers some powers over malloc:
page-aligned memory;
less overhead;
PROT_EXEC (because, on linux x86-64, stuff segfaults if one tries to run
code in buffers allocated with malloc);
forcing stuff into the low 2GB (my runtime text and data/bss sections);
....

so, which is used is controlled by a few ifdefs.

[...]
>>>now, aligning memory, well this depends on the type sizes, ...

a general option is this (should work on windows-32 bit, linux, and
linux
x86-64, and maybe a few others):
p=(void *)((((long)p)+15)&(~15)); //aligns to a 16 byte boundary

No, this is not guaranteed to work. The result of converting of a
pointer to an integer or vice versa is implementation-defined. It's
also not guaranteed that 'long' is wide enough to hold a pointer
value. Even if it is, the result could easily be negative; using
'unsigned long' would avoid that problem, but not the others.

I didn't say it was gueranteed to work, or even all that portable, only
that
it works on x86 and friends in the compilers most people are likely to
use
(gcc and msvc...).

Again, that's not particularly relevant here.
>also note that on x86-64, pointers are signed, so 'long' (or 'long long',
if
win-x64 is a possibility) is a good option.

It depends on what you want to do with the converted result. I don't
use bitwise operators on signed integers, and I don't remember what
(blah+15)&(~15) does if blah is signed and has a negative value.
one need only think in binary...
in this case, it rounds up to the next 16 boundary, headed towards 0.

of course, it does assume 2's complement, but I will argue this is near
universal...

I suppose one can avoid 2's complement dependency by using plain arithmetic
instead:
'((i+15)/16)*16'.

>my case:
I usually detect, using 'int' on x86 and 'long long' on x86-64.

If you have <stdint.h>, you can use intptr_t or uintptr_t (if they
exists). If you don't, I'll mention that I've never used a system on
which different pointer types have different sizes, or on which
sizeof(void*) ! sizeof(long). Neither assumption is guaranteed, of
course, and I have no doubt that systems exist that violate them.
yes, windows x64.

sizeof(void *)==8
sizeof(long)==4

'stdint', hadn't thought of using it in this case...

--
Keith Thompson (The_Other_Keith) ks***@mib.org
<http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*>
<http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Aug 23 '07 #18

P: n/a
In article <ln************@nuthaus.mib.org>,
Keith Thompson <ks***@mib.orgwrote:
>>mmap is not portable.
>it exists on linux...
good enough for if running on linux, just have to detect and use.
>That's irrelevant here in comp.lang.c.
And more to the point, irrelevant to this thread. We're not discussing
a practical problem here, just an interesting exercise: seeing just
how much of the standard library can be defined in terms of standard C.

-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
Aug 23 '07 #19

P: n/a
cr88192 wrote:
>
"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...
"cr88192" <cr*****@hotmail.comwrites:
"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...
"cr88192" <cr*****@hotmail.comwrites:
"Kenneth Brody" <ke******@spamcop.netwrote in message
news:46***************@spamcop.net...
[...]
How do you portably guarantee proper alignment?

if grabbed from malloc, it is aligned to whatever malloc's alignment
[...]
ifdef powers, ifdef fixes everything...
Hardly. If mmap isn't supported, you still have to find some
alternative.

on windows, I use malloc.
[...]

But wasn't the original question along the lines of "how can one
write a replacement for (not a wrapper around) malloc()"?

(Okay, it was actaully more along the lines of "which standard
library functions could be implemented by an end user, rather
than the implementor".)

--
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody | www.hvcomputer.com | #include |
| kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h|
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:Th*************@gmail.com>
Aug 23 '07 #20

P: n/a
Kenneth Brody <ke******@spamcop.netwrites:
cr88192 wrote:
>"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...
"cr88192" <cr*****@hotmail.comwrites:
"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...
"cr88192" <cr*****@hotmail.comwrites:
"Kenneth Brody" <ke******@spamcop.netwrote in message
news:46***************@spamcop.net...
[...]
How do you portably guarantee proper alignment?

if grabbed from malloc, it is aligned to whatever malloc's alignment
[...]
>ifdef powers, ifdef fixes everything...

Hardly. If mmap isn't supported, you still have to find some
alternative.

on windows, I use malloc.
[...]

But wasn't the original question along the lines of "how can one
write a replacement for (not a wrapper around) malloc()"?

(Okay, it was actaully more along the lines of "which standard
library functions could be implemented by an end user, rather
than the implementor".)
Yes. Here's the original post, by Fr************@googlemail.com:
| One interesting thing to come out of the recent "Alignment" thread is
| that it is impossible to write a portable replacement for malloc in
| "user space" (not sure what the right term is - I mean an ordinary
| programmer, not an implementor) - even a naive method using a large
| array isn't guaranteed to work if there's no way of having a variable
| of strictest alignment. Oh, for the sake of the pedants, let's
| discount
| void *my_malloc(size_t size) { return 0; }
| :)
|
| Of course, for most standard library functions, say something like
| strlen, it's perfectly possible to provide a completely equivalent
| implementation yourself.
|
| So as an academic exercise, which other standard library functions
| share the same property as malloc, that the ordinary programmer is
| powerless to write an equivalent function without dipping into non-
| Standard implementation details?

Obviously using mmap and using malloc (!) are not responsive to the
original question.

Thread topics do drift, and that's ok, but we shouldn't let them drift
away from *both* the topic of the newsgroup and relevance to the
original question.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Aug 23 '07 #21

P: n/a
pete wrote:
Harald van =?UTF-8?B?RMSzaw==?= wrote:
>>
santosh wrote:
Fr************@googlemail.com wrote:

One interesting thing to come out of the recent "Alignment" thread is
that it is impossible to write a portable replacement for malloc in
"user space" (not sure what the right term is - I mean an ordinary
programmer, not an implementor) - even a naive method using a large
array isn't guaranteed to work if there's no way of having a variable
of strictest alignment. Oh, for the sake of the pedants, let's
discount
void *my_malloc(size_t size) { return 0; }
:)

Of course, for most standard library functions, say something like
strlen, it's perfectly possible to provide a completely equivalent
implementation yourself.

So as an academic exercise, which other standard library functions
share the same property as malloc, that the ordinary programmer is
powerless to write an equivalent function without dipping into non-
Standard implementation details?

From the top of my head:

free, fopen, fclose, freopen, fread, fwrite, fgetc,
exit, signal, raise,
the is* character test functions, perror, sterror, locale functions,
setjmp/longjmp, fflush, remove, tmpfile, abort, system,
the va_* macros,
time functions.

fread/fwrite can be implemented portably by calling to fgetc/fputc, or
fgetc/fputc can be implemented portably by calling fread/fwrite;

fgetc and fputc are much easier to implement than that:
Fair point, fgetc/fputc can also be implemented portably by calling
getc/putc. And getc/putc can be implemented portably by calling fgetc/fputc
or fread/fwrite or fscanf/fprintf or vfscanf/vfprintf, but whichever way
you choose, you have one of fread/fgetc/getc/fscanf/vfscanf and
fwrite/fputc/putc/fprintf/vfprintf that cannot be implemented portably. I
hope I didn't accidentally overlook any other input or output functions
that would form yet another alternative base I/O function. :)
Aug 23 '07 #22

P: n/a
Harald van =?UTF-8?B?RMSzaw==?= wrote:
>
pete wrote:
fgetc and fputc are much easier to implement than that:

Fair point, fgetc/fputc can also be implemented portably by calling
getc/putc.
But the definitions that I showed,
would actually be efficient in cases where getc and putc
were also implemented as macros, which is not uncommon.

--
pete
Aug 24 '07 #23

P: n/a

"Kenneth Brody" <ke******@spamcop.netwrote in message
news:46***************@spamcop.net...
cr88192 wrote:
>>
"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...
"cr88192" <cr*****@hotmail.comwrites:
"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...
"cr88192" <cr*****@hotmail.comwrites:
"Kenneth Brody" <ke******@spamcop.netwrote in message
news:46***************@spamcop.net...
[...]
How do you portably guarantee proper alignment?

if grabbed from malloc, it is aligned to whatever malloc's alignment
[...]
>ifdef powers, ifdef fixes everything...

Hardly. If mmap isn't supported, you still have to find some
alternative.

on windows, I use malloc.
[...]

But wasn't the original question along the lines of "how can one
write a replacement for (not a wrapper around) malloc()"?
well, often they can be interrelated, in particular, in that malloc (by
itself) typically has a few major limitations:
it is inefficient for a large number of small objects (say, doing several
million 8 byte allocations);
it does not do garbage collection;
it is not possible to store or retrieve type information from objects;
....

doing a wrapper, oner can address these goals, and others...
how does it classify?:
one uses malloc simply to gain large chunks of memory (in much the same way
malloc itself gains memory through means such as mmap or sbrk).
and, if we detect a favorable situation (running on a certain known OS), we
can bypass this and gain the same memory in much the same way as the
original implementation (via mmap, or maybe sbrk). in all practical sense it
is a replacement.

if one didn't even want this much library dependency, they could bypass
functions like mmap, and generate the interrupts themselves, thus directly
accessing the OS kernel.

the exact means employed may not matter too much.
one does their own custom allocator over this new memory (with whatever
algos they feel appropriate).

it works...

(Okay, it was actaully more along the lines of "which standard
library functions could be implemented by an end user, rather
than the implementor".)
ok.

in a strict sense, none can, since they are, after all, already implemented
by the standard library.
and in a non-strict sense, all can...

--
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody | www.hvcomputer.com | #include |
| kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h|
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:Th*************@gmail.com>


Aug 24 '07 #24

P: n/a
cr88192 wrote, On 24/08/07 07:02:
"Kenneth Brody" <ke******@spamcop.netwrote in message
news:46***************@spamcop.net...
<snip>
>(Okay, it was actaully more along the lines of "which standard
library functions could be implemented by an end user, rather
than the implementor".)

ok.

in a strict sense, none can, since they are, after all, already implemented
by the standard library.
and in a non-strict sense, all can...
In a strict sense a lot can. memset, memcpy...
--
Flash Gordon
Aug 24 '07 #25

P: n/a
Flash Gordon said:
cr88192 wrote, On 24/08/07 07:02:
>"Kenneth Brody" <ke******@spamcop.netwrote in message
news:46***************@spamcop.net...

<snip>
>>(Okay, it was actaully more along the lines of "which standard
library functions could be implemented by an end user, rather
than the implementor".)

ok.

in a strict sense, none can, since they are, after all, already
implemented by the standard library.
and in a non-strict sense, all can...

In a strict sense a lot can. memset, memcpy...
<pedant>
Nope, none can - because all the standard library functions have names
that are reserved for use by the implementation.
</pedant>

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Aug 24 '07 #26

P: n/a
"cr88192" <cr*****@hotmail.comwrote:
"Keith Thompson" <ks***@mib.orgwrote in message
"cr88192" <cr*****@hotmail.comwrites:
"Keith Thompson" <ks***@mib.orgwrote in message
"cr88192" <cr*****@hotmail.comwrites:
"Kenneth Brody" <ke******@spamcop.netwrote in message
[...]
How do you portably guarantee proper alignment?

if grabbed from malloc, it is aligned to whatever malloc's alignment
is (on x86 and friends, usually at least 8 or 16 I think...).

and, if from mmap, it is aligned to a page boundary.

mmap is not portable.

it exists on linux...
good enough for if running on linux, just have to detect and use.
That's irrelevant here in comp.lang.c.

but is relevant for actual coding, where most non-trivial code ends up
having to deal with the underlying implementation in one non-standard way or
another...

unless you mean to say: c.l.c is only for theory, not for actual practice...
No, ISO C (and therefore, c.l.c) _is_ for practice. That's _why_ we
don't assume that All The World Is A Bitty-Box. In particular in the
present thread, which was about _portably_ implementing standard library
functions. Of course you can implement every single library function on
any system if you're allowed to use extensions. Since most systems have
at least one implementation which allows you to use some (but wildly
varying) kind of assembler from within C, C-plus-any-extension-you-
desire is trivially able to do anything which assembler can, including
implementing the Standard Library. But that wasn't the point of this
thread.
ifdef powers, ifdef fixes everything...
Hardly. If mmap isn't supported, you still have to find some
alternative.

on windows, I use malloc.
To implement malloc() itself? Nice. For the next trick, please lift
yourself clear off the ground.

Richard
Aug 24 '07 #27

P: n/a
Richard Heathfield wrote:
>
Flash Gordon said:
cr88192 wrote, On 24/08/07 07:02:
"Kenneth Brody" <ke******@spamcop.netwrote in message
news:46***************@spamcop.net...
<snip>
>(Okay, it was actaully more along the lines of "which standard
library functions could be implemented by an end user, rather
than the implementor".)

ok.

in a strict sense, none can, since they are, after all, already
implemented by the standard library.
and in a non-strict sense, all can...
In a strict sense a lot can. memset, memcpy...

<pedant>
Nope, none can - because all the standard library functions have names
that are reserved for use by the implementation.
</pedant>
Well, you could call them my_memset() and my_memcpy(). But, could
one write a portable my_malloc() which properly handles alignment?

Actually, I suppose the answer is "yes, as long as you edit a header
file to properly #define my_ALIGNMENT as needed". But, can you do
it in such a way that the system self-determines the value? (Even
if that "self determination" involves running another program which
generates the #define for you.)

--
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody | www.hvcomputer.com | #include |
| kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h|
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:Th*************@gmail.com>
Aug 24 '07 #28

P: n/a
Richard Bos wrote:
"cr88192" <cr*****@hotmail.comwrote:
.... snip ...
>
>on windows, I use malloc.

To implement malloc() itself? Nice. For the next trick, please
lift yourself clear off the ground.
That is definitely a bootstrap :-) (or hydrogen)

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

--
Posted via a free Usenet account from http://www.teranews.com

Aug 25 '07 #29

P: n/a
On 2007-08-22 10:49, Richard Heathfield <rj*@see.sig.invalidwrote:
pete said:
>santosh wrote:
>So as an academic exercise, which other standard library functions
share the same property as malloc, that the ordinary programmer is
powerless to write an equivalent function without dipping into non-
Standard implementation details?
[...]
>isdigit can be implemented.
It is not locale dependent.

The same applies to isxdigit, and (without looking it up) probably
isspace - and perhaps one or two others in the same vein.
Only if you stick to the basic execution character set. There may be
other digits, xdigits, whitespace characters, etc.

OTOH, all the isx... and other locale-dependent function can be
implemented in portable C by moving the knowledge about the locales to
files which are read at runtime. The filenames could be passed
via the environment to avoid needing knowledge about the filesystem
layout.

hp
--
_ | Peter J. Holzer | I know I'd be respectful of a pirate
|_|_) | Sysadmin WSR | with an emu on his shoulder.
| | | hj*@hjp.at |
__/ | http://www.hjp.at/ | -- Sam in "Freefall"
Aug 25 '07 #30

P: n/a
Peter J. Holzer said:
On 2007-08-22 10:49, Richard Heathfield <rj*@see.sig.invalidwrote:
>pete said:
<snip>
>>isdigit can be implemented.
It is not locale dependent.

The same applies to isxdigit, and (without looking it up) probably
isspace - and perhaps one or two others in the same vein.

Only if you stick to the basic execution character set. There may be
other digits, xdigits, whitespace characters, etc.
I just looked up isspace, and it is indeed locale-dependent. But isdigit
and isxdigit are not. The isdigit function is required to return true
(non-zero) for *only* the ten decimal digit characters '0' through '9',
regardless of which character set is in use. For any other character,
it must return 0, regardless of the locale or the character set in use.
The isxdigit function is required to return true (non-zero) for the ten
decimal digit characters, and for 'a', 'b', 'c', 'd', 'e', 'f', 'A',
'B', 'C', 'D', 'E', and 'F'. For any other character, it must return 0,
regardless of the locale or the character set in use.
<snip>

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Aug 25 '07 #31

P: n/a
On 2007-08-25 20:57, Richard Heathfield <rj*@see.sig.invalidwrote:
I just looked up isspace, and it is indeed locale-dependent. But isdigit
and isxdigit are not. The isdigit function is required to return true
(non-zero) for *only* the ten decimal digit characters '0' through '9',
regardless of which character set is in use. For any other character,
it must return 0, regardless of the locale or the character set in use.
The isxdigit function is required to return true (non-zero) for the ten
decimal digit characters, and for 'a', 'b', 'c', 'd', 'e', 'f', 'A',
'B', 'C', 'D', 'E', and 'F'. For any other character, it must return 0,
regardless of the locale or the character set in use.
You are right. That means that a hypothetical C implementation with a 16
bit char and the Unicode BMP as the execution character set would have
the problem that isdigit doesn't map to the unicode Nd (Numeric,
decimal) property.

I'm also not sure if the wording for iswdigit "The iswdigit function
tests for any wide character that corresponds to a decimal-digit
character (as defined in 5.2.1)." allows more than 10 digits (i.e.,
several wide characters could correspond to each decimal digit). glibc
doesn't seem to think so.

hp
--
_ | Peter J. Holzer | I know I'd be respectful of a pirate
|_|_) | Sysadmin WSR | with an emu on his shoulder.
| | | hj*@hjp.at |
__/ | http://www.hjp.at/ | -- Sam in "Freefall"
Aug 26 '07 #32

This discussion thread is closed

Replies have been disabled for this discussion.