Re: array inside a array!?

From: Flash Gordon (spam_at_flash-gordon.me.uk)
Date: 12/14/04 

Date: Tue, 14 Dec 2004 12:57:45 +0000

On Tue, 14 Dec 2004 17:25:56 +0530
sathya <sathya@nomail.com> wrote:

> sathya wrote:
>
> > I was going through an Boyer-Moore-Horspool pattern match, I saw
> > a
> > array inside a array, like the below,
> >
> > skip[pat[i] ] = patlen - i - 1;
> >
> > The array is decleared as
> >
> > int skip[UCHAR_MAX+1];
> >
> > unsigned char *pat;
> >
> > I have seen function call inside the array such as calling strlen()
> > inside a array, but the above one is
> > strange and new to me as a beginner. Can anybody spend a little time
> > to explain the above.
> > BTW, if this a FAQ please refer the question number.
> >
>
> Sorry I must be more precise in my question. The bellow properties
> is well known with the array:
>
> "In an array, LOGICAL ADJACENCY (B follows A) is modeled by
> PHYSICAL ADJACENCY (B occurs just after A in memory.)"
>
> As in the case of the above "array inside a array" I cannot figure
> out the possibility of logical and
> physical adjacency. And is the above kind of "array inside a array"
> is UD in std?

It's simple. You do *not* have an array inside an array, you are just
looking in one array to find an index in to the other. It is basically
equivalent to:

 int skip[UCHAR_MAX+1];
 unsigned char *pat;
 unsigned char tmp;

 tmp = pat[i];
 skip[ tmp ] = patlen - i - 1;

<pedantic>
C does not guarantee physical adjacency, only logical adjacency. For
example, on a system with paged memory one location in the array might
be in physical memory whilst the next location, on the other side of a
page boundary, might have been swapped out to disk and not exist in
physical memory at all.
</pedantic>

If you want to look at formal definitions with respect to C you really
need to look at the C standard in my opinion. Google for N869 to find
the publicly available last draft of the C99 standard. 

-- 
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.

Relevant Pages

  • Re: 3 questions about arrays
    ... In order to print the elements of the array doesn't the ... If yes then it's undefined behavior. ... choosing the size of fixnums not the maximum size of arrays. ... That's already the case in plenty of CL implementations -- unless a lot of people have 60 bits of physical memory they're not telling anyone about. ...
    (comp.lang.lisp)
  • Re: Maximum Array int is 330 M, not 2.1 billion
    ... I simply filled an array of this size with ints...I got as far as 320 ... What is relevant is the address space limit of your application, which happens to be 2 GiB on 32-bit Windows, which happens to be the maximum value of a signed 32-bit int as well -- but this is coincidental. ... You can make Windows run with a 3 GiB virtual address space for each application, for example, and 64-bit applications have a unfathomably bigger limit that I can't recall right now, but you'll hit the limits of your physical memory far sooner than that. ... There is no extra per-element overhead for managed arrays. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Reversing Array Elements?
    ... Depends what you mean by "actually reverse the array". ... rather than a specification of the language. ... could make such a reordered copy in physical memory as an optimization. ...
    (comp.lang.fortran)
  • Re: Accessing Physical memory in windows 64bit
    ... No need to parse physical memory. ... The operative system provides that informtation via WMI In kernel-mode, ... and in user mode as an array of bytes already extracted for you. ...
    (microsoft.public.development.device.drivers)
  • Re: Are array members guaranteed to be contiguous in physical memory?
    ... The Standard demands it. ... In 6.2.5 clause 20 the Standard guarantees that the array is ... not the physical memory of the hosting ... terrible burden on the compiler runtime environment as it has to have ...
    (comp.lang.c)