Programming Forums > Application Development > C

deanosrs · Apr 10th, 2006, 5:14 PM

Hi.

I'm writing an assembler for the mips32 processor in C for a coursework assignment, for which I'm going to store the instruction set in a hash table. As a collision strategy I'm going to use lists.

So I have a function I call at the start of the program, once for every instruction. This hash function generates the hash key then attempts to add the data into the hash table.

As my hash table is an array of lists, I then call the insert list function which works fine so the content is irrelevant to this problem, but it's defined like this:

(Toggle Plain Text)

instr *insertinstrlist(instr *instrlist, char opcode[], int args, char type) {
...
}

The list I have defined like this:

(Toggle Plain Text)

typedef struct instrcontent {
	char opcode[5];
	int args;
	char type;
	struct instrcontent *next;
} instr;

and the call to the insert function like this where isa is the hash table:

(Toggle Plain Text)

isa[key] = insertinstrlist(isa[key], opcode, args, type);

The table I have initialised like this (this is where I think I'm going wrong):

(Toggle Plain Text)

instr isa[30];

So the problem is when I compile in GCC it says that the call to insertinstrlist is invalid because isa[key] is not the correct data type.

I hope I've explained this clearly enough! Any help any of you guys could give me would be much appreciated.

DaWei · Apr 10th, 2006, 5:30 PM

isa [key] is the address of an instr. So is an *instr pointer. They are NOT precisely the same thing though they have a certain equivalence (see the link to the pointer material in my sig for more on that subject). I think you'll be fine if you just cast the return. I'm surprised that you didn't get a warning or error about the usage as a passed parameter, also.

deanosrs · Apr 10th, 2006, 6:11 PM

Yes sorry it does give me an error for the parameter as well.

I'm sorry for also being dim and not fully understanding yet! I've programmed loads in Java and PHP, so most of C I find reasonably easy - apart from pointers! I've read through your excellent tutorial which has helped explain alot - thank you! - but where I get confused, is that if isa[key] is a pointer, then did instr isa[30] actually do anything in the first place?! Because that's the only line I have to initialise the hash table array. I'm also not down with the C lingo yet and am embarrassed to admit I don't know what "cast" means. I know it sounds pathetic but if you could post what the code should be that would help a lot. Thanks for your help so far !

DaWei · Apr 10th, 2006, 6:36 PM

isa [key] is not a pointer. It's the address of an element in the array. Because it's an address, it has certain equivalencies with a pointer. However, the CONTENTS at the address are the value of the element. The contents at the address contained in a pointer are another address; the contents there are the value of the element. It's a matter of one level of indirection difference. The compiler can deal with this if it has enough information. Otherwise, it doesn't know whether to store/retrieve something from that address, or follow that address and fetch from there.

When you pass the address of an element (isa [key]), it is a pointer as a parameter. When you pass the address of a pointer to isa [key], it is also a pointer, but one level of indirection removed, still. At runtime there is no indication of how that should be handled. The compiler would appreciate it if you would leave a hint (cast).

grumpy · Apr 10th, 2006, 7:00 PM

isa[key] is not a pointer, and it is not the address of an element in the array. isa is an array. In C++ speak isa[key] would be described as a reference, which is a different thing from an address. I C-speak it would be described as a dereferenced address (or a dereferenced pointer in cases where pointers and arrays are equivalent).

Try converting the offending line to this;

(Toggle Plain Text)

   isa[key] = *insertinstrlist(&isa[key], opcode, args, type);

or (more simply using equivalent pointer notation);

(Toggle Plain Text)

   isa[key] = *insertinstrlist(isa + key, opcode, args, type);

EDIT: The C concept of pointer does not map directly into Java (as Java is designed to avoid the perceived evils associated with C/C++ pointers, so does not support the concept). Using Java techniques will therefore get you into trouble in C or C++ when manipulating pointers.

deanosrs · Apr 10th, 2006, 7:14 PM

Wow, ok well that correction has got it working but I can't say I understand - obviously need to do some reading on this from some textbooks! I can deal with pointers and addresses, but this dereferenced address stuff I can't yet! Thanks for all the help, much appreciated.

grumpy · Apr 10th, 2006, 8:05 PM

That's because you come from a background in languages (eg Java) that are designed to hide the evils associated with pointers.

A quick bit of "array pointer equivalence" 101 follows. You need to read it slowly, as some of the earlier examples need to be grasped before you can understand the later ones.

Let's assume that we have some arrays and pointers to some_type declared (the actual size of the arrays doesn't matter), and a function which accepts a pointer as an argument.

(Toggle Plain Text)

   some_type  array[2] = {1,2}, array2[2] = {3,4};
   some_type  *pointer, *pointer2;
   void Function(some_type *x);

In some contexts, pointers and arrays are equivalent. This equivalence means that the following operations are all valid;

(Toggle Plain Text)

    pointer = array;    /*  logically equivalent to pointer = &array[0]; */
    pointer2 = array2; /*  logically equivalent to pointer2 = &array2[0] */
    pointer[1] = 42;   /* changes array[1] */
    *(pointer + 1) = 42;  /* equivalent to previous line */
    pointer2[1] = 42;      /* changes array2[1] */
    pointer = array2;  /* pointers can be reassigned */
    pointer[1] = 10;  /*  NOW changes array2[1] */
    pointer = array + 1;   /* equivalent to pointer = &array[1] */
    pointer[0] = 15;       /* now equivalent to array[1] = 15 based on value of pointer*/
    *(pointer + 0) = 15;  /* equivalent to last line */
    *pointer = 15           /* equivalent to last line */

    Function(array);    /*  OK;  equivalent to Function(&array[0]) */
    Function(array2);
    pointer = array;
    Function(pointer);

    array[1] = 5;
    *(array + 1) = 5;    /*   pointer equivalent of last line */
    array[0] = 5;
    *(array + 0) = 5;    /*   pointer equivalent of last line */
    *array = 5;            /*   simplified version of last line as index == 0 */

but the following are not allowed because they clash with areas where pointers and arrays are not the same thing;

(Toggle Plain Text)

    array = array2;      /*   Cannot assign arrays */
    array = pointer;      /*   Cannot assign an array to a pointer */

Now, in terms of jargon.

*pointer is said to be a dereferenced pointer. It is technically an indirect reference (or an alias) for an object of some_type. If we assume

(Toggle Plain Text)

    pointer = array;   /* syntactically equivalent to pointer = &array[0] */

then the lines;

(Toggle Plain Text)

    pointer[0] = 42;  
    *pointer = 42;
    *(pointer + 0) = 42;

all (equivalently) change the value of array[0]. The reason is that pointer contains the address of array[0], and accessing elements via array notation or by the *pointer notation directly accesses the element array[0].

So a derefenced pointer (*pointer) is technically referred to as a C reference, as it is an alias for the actual object pointed at by pointer.

In C++, we also have reference types. One of the purposes of reference types was to support aliases for objects without having to use pointer notation (i.e. elements accessed directly by their name or alias, with no need to use the * or array notations).

The Dark · Apr 10th, 2006, 8:12 PM

If the insertinstrlist function creates a new object using "malloc", shouldn't the list array be

(Toggle Plain Text)

  instr *isa[30];

(you will then need to explicitly initialise the array elements to NULL).

Otherwise the first entry in each of the lists will be allocated by insertstrlist, then copied into the list of objects (using the *), then the pointer to the original memory allocated will be lost, causing a memory leak.

If the insertstrlist function only allocates memory for the subsequent elements in the list and not for the first one (which seems an odd way to behave), then ignore this post.

DaWei · Apr 10th, 2006, 8:14 PM

My apologies; isa [key] represents the contents of isa at location key, as Grumpy says. The compiler delivers it by referring to that location, addressed as determined by the operation Grumpy mentions: isa + key.

grumpy · Apr 10th, 2006, 8:52 PM

Quote:

Originally Posted by The Dark

If the insertinstrlist function creates a new object using "malloc", shouldn't the list array be

(Toggle Plain Text)

  instr *isa[30];

(you will then need to explicitly initialise the array elements to NULL).

Otherwise the first entry in each of the lists will be allocated by insertstrlist, then copied into the list of objects (using the *), then the pointer to the original memory allocated will be lost, causing a memory leak.

It depends on how insertinstrlist() works.

If the pointer returned is the ONLY reference to something that has been malloc'ed, then the caller needs to keep track of it and clean up or face a memory leak.

If insertinstrlist() keeps a table internally, and the return value of insertinstrlist() always an entry from that table, then there is no need for the caller to keep track of the return values (assuming, of course, that there is some means to clean up that internal table).

The question was about why the code didn't compile. Getting the code working correctly (eg eliminating memory leaks) is a separate issue. Albeit a pretty important one.

Apr 10th, 2006, 5:14 PM	#1
deanosrs Programmer Join Date: Apr 2006 Location: Bristol, UK Posts: 31 Rep Power: 0	Assigning an array of lists Hi. I'm writing an assembler for the mips32 processor in C for a coursework assignment, for which I'm going to store the instruction set in a hash table. As a collision strategy I'm going to use lists. So I have a function I call at the start of the program, once for every instruction. This hash function generates the hash key then attempts to add the data into the hash table. As my hash table is an array of lists, I then call the insert list function which works fine so the content is irrelevant to this problem, but it's defined like this: (Toggle Plain Text) instr insertinstrlist(instr instrlist, char opcode[], int args, char type) { ... } instr insertinstrlist(instr instrlist, char opcode[], int args, char type) { ... } The list I have defined like this: (Toggle Plain Text) typedef struct instrcontent { char opcode[5]; int args; char type; struct instrcontent next; } instr; typedef struct instrcontent { char opcode[5]; int args; char type; struct instrcontent next; } instr; and the call to the insert function like this where isa is the hash table: (Toggle Plain Text) isa[key] = insertinstrlist(isa[key], opcode, args, type); isa[key] = insertinstrlist(isa[key], opcode, args, type); The table I have initialised like this (this is where I think I'm going wrong): (Toggle Plain Text) instr isa[30]; instr isa[30]; So the problem is when I compile in GCC it says that the call to insertinstrlist is invalid because isa[key] is not the correct data type. I hope I've explained this clearly enough! Any help any of you guys could give me would be much appreciated.

Apr 10th, 2006, 5:30 PM	#2
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	isa [key] is the address of an instr. So is an instr pointer. They are NOT precisely the same thing though they have a certain equivalence (see the link to the pointer material in my sig for more on that subject). I think you'll be fine if you just cast the return. I'm surprised that you didn't get a warning or error about the usage as a passed parameter, also. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers*

Apr 10th, 2006, 6:36 PM	#4
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	isa [key] is not a pointer. It's the address of an element in the array. Because it's an address, it has certain equivalencies with a pointer. However, the CONTENTS at the address are the value of the element. The contents at the address contained in a pointer are another address; the contents there are the value of the element. It's a matter of one level of indirection difference. The compiler can deal with this if it has enough information. Otherwise, it doesn't know whether to store/retrieve something from that address, or follow that address and fetch from there. When you pass the address of an element (isa [key]), it is a pointer as a parameter. When you pass the address of a pointer to isa [key], it is also a pointer, but one level of indirection removed, still. At runtime there is no indication of how that should be handled. The compiler would appreciate it if you would leave a hint (cast). __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Apr 10th, 2006, 7:00 PM	#5
grumpy Programming Guru Join Date: Jun 2005 Location: Adelaide, South Australia Posts: 1,209 Rep Power: 5	isa[key] is not a pointer, and it is not the address of an element in the array. isa is an array. In C++ speak isa[key] would be described as a reference, which is a different thing from an address. I C-speak it would be described as a dereferenced address (or a dereferenced pointer in cases where pointers and arrays are equivalent). Try converting the offending line to this; (Toggle Plain Text) isa[key] = insertinstrlist(&isa[key], opcode, args, type); isa[key] = insertinstrlist(&isa[key], opcode, args, type); or (more simply using equivalent pointer notation); (Toggle Plain Text) isa[key] = insertinstrlist(isa + key, opcode, args, type); isa[key] = insertinstrlist(isa + key, opcode, args, type); EDIT: The C concept of pointer does not map directly into Java (as Java is designed to avoid the perceived evils associated with C/C++ pointers, so does not support the concept). Using Java techniques will therefore get you into trouble in C or C++ when manipulating pointers. Last edited by grumpy; Apr 10th, 2006 at 7:14 PM.

Apr 10th, 2006, 8:05 PM	#7
grumpy Programming Guru Join Date: Jun 2005 Location: Adelaide, South Australia Posts: 1,209 Rep Power: 5	That's because you come from a background in languages (eg Java) that are designed to hide the evils associated with pointers. A quick bit of "array pointer equivalence" 101 follows. You need to read it slowly, as some of the earlier examples need to be grasped before you can understand the later ones. Let's assume that we have some arrays and pointers to some_type declared (the actual size of the arrays doesn't matter), and a function which accepts a pointer as an argument. (Toggle Plain Text) some_type array[2] = {1,2}, array2[2] = {3,4}; some_type pointer, pointer2; void Function(some_type x); some_type array[2] = {1,2}, array2[2] = {3,4}; some_type pointer, pointer2; void Function(some_type x); In some contexts, pointers and arrays are equivalent. This equivalence means that the following operations are all valid; (Toggle Plain Text) pointer = array; /* logically equivalent to pointer = &array[0]; / pointer2 = array2; / logically equivalent to pointer2 = &array2[0] / pointer[1] = 42; / changes array[1] / (pointer + 1) = 42; /* equivalent to previous line / pointer2[1] = 42; / changes array2[1] / pointer = array2; / pointers can be reassigned / pointer[1] = 10; / NOW changes array2[1] / pointer = array + 1; / equivalent to pointer = &array[1] / pointer[0] = 15; / now equivalent to array[1] = 15 based on value of pointer/ (pointer + 0) = 15; /* equivalent to last line / pointer = 15 /* equivalent to last line / Function(array); / OK; equivalent to Function(&array[0]) / Function(array2); pointer = array; Function(pointer); array[1] = 5; (array + 1) = 5; /* pointer equivalent of last line / array[0] = 5; (array + 0) = 5; /* pointer equivalent of last line / array = 5; /* simplified version of last line as index == 0 / pointer = array; / logically equivalent to pointer = &array[0]; / pointer2 = array2; / logically equivalent to pointer2 = &array2[0] / pointer[1] = 42; / changes array[1] / (pointer + 1) = 42; /* equivalent to previous line / pointer2[1] = 42; / changes array2[1] / pointer = array2; / pointers can be reassigned / pointer[1] = 10; / NOW changes array2[1] / pointer = array + 1; / equivalent to pointer = &array[1] / pointer[0] = 15; / now equivalent to array[1] = 15 based on value of pointer/ (pointer + 0) = 15; /* equivalent to last line / pointer = 15 /* equivalent to last line / Function(array); / OK; equivalent to Function(&array[0]) / Function(array2); pointer = array; Function(pointer); array[1] = 5; (array + 1) = 5; /* pointer equivalent of last line / array[0] = 5; (array + 0) = 5; /* pointer equivalent of last line / array = 5; /* simplified version of last line as index == 0 / but the following are not allowed because they clash with areas where pointers and arrays are not the same thing; (Toggle Plain Text) array = array2; / Cannot assign arrays / array = pointer; / Cannot assign an array to a pointer / array = array2; / Cannot assign arrays / array = pointer; / Cannot assign an array to a pointer / Now, in terms of jargon. pointer is said to be a dereferenced pointer. It is technically an indirect reference (or an alias) for an object of some_type. If we assume (Toggle Plain Text) pointer = array; /* syntactically equivalent to pointer = &array[0] / pointer = array; / syntactically equivalent to pointer = &array[0] / then the lines; (Toggle Plain Text) pointer[0] = 42; pointer = 42; (pointer + 0) = 42; pointer[0] = 42; pointer = 42; (pointer + 0) = 42; all (equivalently) change the value of array[0]. The reason is that pointer contains the address of array[0], and accessing elements via array notation or by the pointer notation directly accesses the element array[0]. So a derefenced pointer (pointer) is technically referred to as a C reference, as it is an alias for the actual object pointed at by pointer. In C++, we also have reference types. One of the purposes of reference types was to support aliases for objects without having to use pointer notation (i.e. elements accessed directly by their name or alias, with no need to use the or array notations).

Apr 10th, 2006, 6:11 PM	#3
deanosrs Programmer Join Date: Apr 2006 Location: Bristol, UK Posts: 31 Rep Power: 0	Yes sorry it does give me an error for the parameter as well. I'm sorry for also being dim and not fully understanding yet! I've programmed loads in Java and PHP, so most of C I find reasonably easy - apart from pointers! I've read through your excellent tutorial which has helped explain alot - thank you! - but where I get confused, is that if isa[key] is a pointer, then did instr isa[30] actually do anything in the first place?! Because that's the only line I have to initialise the hash table array. I'm also not down with the C lingo yet and am embarrassed to admit I don't know what "cast" means. I know it sounds pathetic but if you could post what the code should be that would help a lot. Thanks for your help so far !

Apr 10th, 2006, 7:14 PM	#6
deanosrs Programmer Join Date: Apr 2006 Location: Bristol, UK Posts: 31 Rep Power: 0	Wow, ok well that correction has got it working but I can't say I understand - obviously need to do some reading on this from some textbooks! I can deal with pointers and addresses, but this dereferenced address stuff I can't yet! Thanks for all the help, much appreciated.

Apr 10th, 2006, 8:12 PM	#8
The Dark Expert Programmer Join Date: Jun 2005 Posts: 825 Rep Power: 4	If the insertinstrlist function creates a new object using "malloc", shouldn't the list array be (Toggle Plain Text) instr isa[30]; instr isa[30]; (you will then need to explicitly initialise the array elements to NULL). Otherwise the first entry in each of the lists will be allocated by insertstrlist, then copied into the list of objects (using the *), then the pointer to the original memory allocated will be lost, causing a memory leak. If the insertstrlist function only allocates memory for the subsequent elements in the list and not for the first one (which seems an odd way to behave), then ignore this post.

Apr 10th, 2006, 8:14 PM	#9
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	My apologies; isa [key] represents the contents of isa at location key, as Grumpy says. The compiler delivers it by referring to that location, addressed as determined by the operation Grumpy mentions: isa + key. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Programming Forums > Application Development > C

Assigning an array of lists