Path: utzoo!attcan!uunet!iscuva!carlp
From: carlp@iscuva.ISCS.COM (Carl Paukstis)
Newsgroups: comp.lang.c
Subject: address of structure == address of first member? (long)
Summary: portability considerations for general-purpose search
Message-ID: <2172@iscuva.ISCS.COM>
Date: 21 Nov 88 19:45:40 GMT
Organization: ISC Systems Corporation, Spokane, WA
Lines: 131


In my H&S, 5.7.3 (p. 108) says "... C compilers are constrained to assign
components increasing memory addresses in a strict left-to-right order,
with the first component starting at the beginning address of the structure
itself."

Fine. I want to write a general-purpose search function.  I have several
arrays of (different) structures; each structure contains a pointer to a char
string identifier as its first member.  The search function takes a
character (string) pointer to a search argument, a pointer to one of the
arrays of structures, the size the structure entry, and the number of
entries in the table.  It finds the table entry containing the (pointer to)
string specified, and returns a pointer to the matching table entry.

By H&S, that part of the code which gets the pointer to the string to do
the compare must work.  And the following compiles and runs clean under
gcc (1.30) under Ultrix and another (semi-)ANSI(draft)compliant compiler
on a SYS V system.  What other portability problems will I run into with
this code?  How can I fix them?

 1	#include <stdio.h>
 2
 3	struct mumble {
 4	    char *dopey;
 5	    float sneezy;
 6	    int doc;
 7	    };
 8
 9	struct fumble {
10	    char *bashful;
11	    char grumpy;
12	    float sleepy;
13	    };
14
15	const struct mumble m[10] = {
16	    { "abc", 1.3, 4 },
17	    { "def", 2.5, 2 },
18	    { "ghi", 2.6, 1 },
19	    { "ghj", 2.67, 0 },
20	    { "zzzkl", 9.4, -2 }
21	    };
22
23	const struct fumble f[12] = {
24	    { "annapolis", 'b', 907.4 },
25	    { "brainerd", 'c', 821.0 },
26	    { "collinston", 'd', 1243.6},
27	    { "detroit", 'e', 3.2 },
28	    { "evanston", 'f', 1.1054 },
29	    { "fargo", 'g', 1204.0 },
30	    { "gonzaga", 'z', 3.1415926 },
31	    { "zulu", 'a', 92203.1 }
32	    };
33
34	main()
35	{
36	    void * mybsearch(const char *, void const *, const int, const int);
37	    struct mumble *pm;
38	    struct fumble *pf;
39
40	    pm = (struct mumble *)mybsearch ("ghj",
41	            (void *)m,
42	            sizeof(m)/sizeof(struct mumble),
43	            sizeof(struct mumble));
44
45	    if (0 == pm)
46	        {
47	        printf("Not found in m!\n");
48	        exit(1);
49	        }
50	    printf("Value for ghj is %f\n",pm->sneezy);
51
52	    pf = (struct fumble *)mybsearch ("evanston",
53	            (void *)f,
54	            sizeof(f)/sizeof(struct fumble),
55	            sizeof(struct fumble));
56
57	    if (0 == pf)
58	        {
59	        printf("Not found in f!\n");
60	        exit(1);
61	        }
62	    printf("Value for evanston is %f\n",pf->sleepy);
63
64	    printf("OK, found both!\n");
65	    exit(0);
66	}
67
68	/**
69	**  simple-minded binary search routine:
70	**      Find a table entry which matches the desired string.
71	**      Table entries are assumed to be structures, the first
72	**      member of which is a pointer to a character string key.
73	**/
74
75	void * mybsearch (const char * key,     /* value to match against */
76	                void const * table,     /* first table entry */
77	                const int count,        /* number of table entries */
78	                const int size)         /* size (char's) of each entry */
79	{
80	    int l, m, r;
81	    int code;
82	    for (l = 0, r = count - 1; l <= r;)
83	    {
84	        m = (l + r) / 2;
85
86	        code = strcmp (key, *(char **)((char *)table + (m * size)));
87
88	        if (code == 0)      /* found it! */
89	            return ((void *)((char *)table + (m * size)));
90
91	        if (code < 0)
92	            r = m - 1;      /* search left half */
93	        else
94	            l = m + 1;      /* search right half */
95	    }
96
97	    return ((void *) 0);    /* not found */
98	}
99

Line 86 bothers me.  Is it permissible to cast a void* into a char* and do
arithmetic on it like this?  Line 89 would have the same problem (if any).

On machines (environments?) with non-byte-sized chars, is there a better
way to do the necessary arithmetic?  Or what else have I missed?

-- 
Carl Paukstis    +1 509 927 5600 x5321  |"I met a girl who sang the blues
                                        | and asked her for some happy news
UUCP:     carlp@iscuvc.ISCS.COM         | but she just smiled and turned away"
          ...uunet!iscuvc!carlp         |                    - Don MacLean