Structured Data

Last modified Wednesday, 01-Mar-2023 19:59:23 UTC.

Enumerated types
- An enumeration type is a set of identifiers called enumeration constants. The syntax is the same as for structures and unions.
```
enum [enumeration_tag] {<list of identifiers>} <variables>; 
```
- The enumeration constants may not also be used as other names.
- EnumPet.c - Enumerated type for pets
- Enumeration types are implemented by assigning integer values to the enumeration constants, the first constant being assign 0, then 1 etc. This may be overridden by explicitly giving the constants signed integer values in the definition. e.g.
```
typdef enum {ben=7,paul=1,andrew=-9,kevin=5} StudentsType;

StudentsType Class; 
```
- It is legal to give two constants the same value but that is bad style. If some constants are not given values, they receive values progressing upwards from the last one that did.
- Variables of this type may be assigned any of the constants.
- Implementations vary, but enumerated variables may usually be used as ints in expressions - it may be necessary to cast them to int.
Structures
- A structure is a collection of one or more variables, possibly of different types, grouped together under a single name for convenience.
```
struct date {
    short Day,Month;
    int Year;
    int YearDay;
    char MonthName[10];
} Today,Tommorrow,Doomsday; 
```
  This definition declares a type struct date which is a structure, and variables of that type.
- The structure tag which follows the struct is optional, but is useful as future variables of this type can be defined using struct <tag> as the type.
- Variables need not be defined in a structure definition. The structure definition itself is called a structure template. In such a case it makes no sense to omit the structure tag.
- Better style is to typedef the structure :
```
typedef struct {
    short Day,Month;
    int Year;
    int YearDay;
    char MonthName[10];
} DateType;

DateType Today,Tommorrow,Doomsday; 
```
- Structure members can have the same names as other variables as they are differentiated by context.
- Structures can be nested, e.g.
```
typedef struct {
    char Name[64],Address[128];
    int Postcode;
    double Salary;
    DateType Birthdate;
} AustraliaCardType;

AustraliaCardType BobHawke,PaulKeating; 
```
Operations on a structure
- To access a structure element, use <structure name>.<member name>. e.g.
```
Tommorrow.Year = 1989;
MonthEnd = Today.Month != Tommorrow.Month; 
```
- The structure member operator is left to right associative. e.g. BobHawke.Birthdate.Year = 1902; is read as (BobHawke.Birthdate).Year = 1902
- Structures may be assigned to another (including passing to and returning from functions), e.g.
```
Tommorrow = Today;
DateType Armagedon(AustraliaCardType Instigator);
         . . . .
Doomsday = Armagedon(BobHawke); 
```
- StructSCUBA1.c - Typedefed structure of SCUBA data
- Note how the Site array gets passed by value.
- Structures may not be compared as a unit, only member by member.
- Structures can be initialised with a list of initialisers in {}, as for arrays. e.g.
```
DateType Tommorow = {28,10,1987,301,"Oct"};
          
```
Pointers to structs
- To get the address of a structure use & as usual.
- The -> operator operates on a pointer to a structure to access a member.
- DatePointer->Year is equivalent to (*DatePointer).Year. Here the () are necessary as . has higher precedence that *.
- Where ever it is legal to take a pointer to a structure, it is legal to take a pointer to one of its elements, e.g. ChangeDate(&Today.Day); may be used to pass the date by reference to ChangeDate.
- StructPointers.c - Program demonstrating pointers to structs
- StructPointerFields.c - Program demonstrating pointer fields in structs
- StructSCUBA2.c - Structure of SCUBA data with input
Arrays of structures.
- Defining a DataBankType
```
#define POPULATION 10000

typedef struct {
    short Day,Month;
    int Year;
    int YearDay;
    char MonthName[4];
} DateType;

typedef struct {
    char Name[64],Address[128];
    int Postcode;
    double Salary;
    DateType Birthdate;
} AustraliaCardType;

typedef AustraliaCardType DataBankType[POPULATION];

DataBankType BigBrother; 
```
- StructSCUBA3.c - Array of structure of SCUBA data with input
- Arrays of structure can be initialised like all arrays, each element of the initialisation list being a structure initialiser.
```
DataBankType BigBrother =
    {{"Adam Ant",
      "10 Hill St, Blues City",
      1984,
      2001.0,
      {29,2,1945,60,"Feb"}},
     {"Brian Bury",
           etc
                         }}}; 
```
  As with arrays, the innner {} may be left out and the array will be initialised in order. Not good style.
- StringsQSort.c - Program sorting structures using qsort
- If the array is initialised the size of the array may be determined by the number of initialsers. For scanning through the array it is still necessary to know how many elements there are. This number can be found by dividing the size of the array by the size of each element. e.g.
```
typedef struct {
    char Name[10];
    long PhoneNumber;
} PhoneBookEntryType;

PhonebookEntryType PhoneBook[] =
    {{"Fred",2726547},
     {"Mary",3107654},
           etc
                    }};

int NumberOfFriends = sizeof(PhoneBook)/sizeof(PhoneBookEntryType); 
```
  Here's an abstracted way of doing that ...
```
#define LENGTH(A) (sizeof(A)/sizeof(A[0]))

int NumberOfFriends = LENGTH(PhoneBook);
```
- The size of a structure is not always the sum of the size of its members as alignment constaints may leave holes in the structure.
Self referential structures
- Pointers inside structs (oooh, look, linked structures)
- It is necessary to use the structure tag to define self-pointers, as the type of the structure is unknown at that point.
- SimpleLinkedList.c - A simple linked list program
- LinkedList.c - A heavier linked list program
- BinaryTree.c - A binary tree program
Unions.
- A union is a variable which may hold (at different times) objects of different types and sizes.
- The syntax and access is based on structures.
```
typedef union {
    int I1;
    float F1;
    char *S1;
} StrangeType;

StrangeType StrangeVariable; 
```
  - The StrangeVariable will be large enough to hold the largest of the three types.
  - Any one of the fields may be assigned a value and the value retrieved as long as the usage is consistent.
  - The programmer is responsible for maintaining this consistency.
- The access is again via the . and -> operators.
- The same operations are allowed on unions as on structures.
- The addresses of the members will all be the same as the address of the union.
- SimpleUnion.c
- Unions may be initialised via the first member of the union.
- It is not possible to have a union that has "either two integers or a float" (as in Pascal), without nesting a structure in the union.
- UnionSport.c - Union of wild sports
Bit fields.
- Bit fields are a set of adjacent bits, which can be used as members of structures and unions.
```
typedef struct {
    char Name[20];
    int Type:4;
    signed int Class:3;
    unsigned int UsedYet:1;
    int NumberOfUses;
} SymbolType;

SymbolType SymbolDetails; 
```
- The field type is always one of int, unsigned int, or signed int.
- Bits fields are packed into implementation dependant allocation units, and may be packed in either direction. If a bit field does not fit into the allocation unit, it may be split or moved into the next unit.
- BitFields.c - Bit fields of a byte
- Unnamed fields may be used as padding - useful when accessing machine defined bits.
- The field width 0 will force the next field to the next allocation unit boundary.
- The & operator may not be applied to bit fields.
- Bit fields and ordinary fields may be freely intermixed. Ordinary fields will always start at the next allocation unit boundary.
- Example: Device control
  - Frequently device controllers (e.g. disk drives) and the operating system need to communicate at a low level. Device controllers contain several registers which may be packed together in one integer:
  - We could define this register easily with bit fields:
```
typedef struct {
     unsigned Ready:1;
     unsigned ErrorOccured:1;
     unsigned DiskSpinning:1;
     unsigned WriteProtect:1;
     unsigned HeadLoaded:1;
     unsigned ErrorCode:8;
     unsigned Track:9;
     unsigned Sector:5;
     unsigned Command:5;
} DiskRegisterType; 
```
  - To access values stored at a particular memory address, DiskRegisterMemory we can assign a pointer of the above structure to access the memory via:
```
DiskRegisterType *DiskRegister = (DiskRegisterType *) DiskRegisterMemory;
               
```
  - The disk driver code to access this is now relatively straightforward:
```
//----Define sector and track to start read 
DiskRegister->Sector = NewSector;
DiskRegister->Track = NewTrack;
DiskRegister->Command = READ;

//----Wait until operation done, ready will be true
while (! DiskRegister->Ready) {
}

//----Check for errors
if (DiskRegister->ErrorOccured) {
//----Interrogate error_code for error type
    switch (DiskRegister->ErrorCode) {
        ....
    }
} 
```
  - A note of caution: Bit fields are a convenient way to express many difficult operations. However, bit fields do suffer from a lack of portability between platforms: integers may be signed or unsigned. Many compilers limit the maximum number of bits in the bit field to the size of an integer which may be either 16-bit or 32-bit varieties. Some bit field members are stored left to right others are stored right to left in memory. If bit fields too large, next bit field may be stored consecutively in memory (overlapping the boundary between memory locations) or in the next word of memory. If portability of code is a premium you can use bit shifting and masking to achieve the same results but not as easy to express or read. For example:
```
unsigned int  *DiskRegister = (unsigned int *) DiskRegisterMemory;

//----See if disk error occured
DiskErrorOccured = (DiskRegister & 0x40000000) >> 31; 
```

Exercises

Write a program that gets the high and low order bytes of an unsigned int.
Write a suite of functions for manipulating queues. You should provide functions to add to the queue, remove from the queue, and test if the queue is empty. Each member of the queue may hold either an int, a double or a string. Use a bit field to indicate the nature of the contents.
Write an interactive program that allows the user to place items (as above) into, or remove items from, a queue.
Exercise 12386
Write program using enumerated types which when given today's date will print out tomorrow's date in the for 31st January, for example.
Exercise 12387
Write a simple database program that will store a persons details such as age, date of birth, address etc.
Exercise 12507
Write a function that prints out an 8-bit (unsigned char) number in binary format.
Exercise 12514
Write a function setbits(x,p,n,y) that returns x with the n bits that begin at position p set to the rightmost n bits of an unsigned char variable y (leaving other bits unchanged). E.g. if x = 10101010 (170 decimal) and y = 10100111 (167 decimal) and n = 3 and p = 6 say then you need to strip off 3 bits of y (111) and put them in x at position 10xxx010 to get answer 10111010. Your answer should print out the result in binary form although input can be in decimal form. Your output should be like this:
```
x = 10101010 (binary)
y = 10100111 (binary)
setbits n = 3, p = 6 gives x = 10111010 (binary)
     
```
Exercise 12515
Write a function that inverts the bits of an unsigned char x and stores answer in y. Your answer should print out the result in binary form although input can be in decimal form. Your output should be like this:
```
x = 10101010 (binary)
x inverted = 01010101 (binary)
     
```
Exercise 12516
Write a function that rotates (NOT shifts) to the right by n bit positions the bits of an unsigned char x, i.e. no bits are lost in this process. Your answer should print out the result in binary form although input can be in decimal form. Your output should be like this:
```
x = 10100111 (binary)
x rotated by 3 = 11110100 (binary)
     
```
Exercise 12478
Write a program that reads the following structure and sorts the data by keyword using qsort
```
typedef struct {
            char keyword[10];
            int other_data;
        } Record;
     
```

Exam Style Questions

Any of the short exercises.
typedef a structure suitable for holding information about a radio station, including it's 4 character code name (e.g., ZETA), it's catch phrase (e.g., "ZETA Rocks"), it's frequency (e.g., 94.9), and the number of employees (e.g., 27).

Given the structure definitions

typedef struct {
    int Counter;
    float Average;
} hit_rate_type;
typdef struct {
    char *Name;
    hit_rate_type Killer;
} murder_type;

murder_type *JackTheRipper;

write code that mallocs memory for JackTheRipper, stores the name "Jack the Ripper" in the Name field, and stores 99 in the Counter.

Explain the difference between a union and struct

Assuming that an int occupies 2 bytes, what is the output from the following code?

typedef union {
     int WholeThing;
     struct {
          unsigned Top:8;
          unsigned Middle:4;
          unsigned Bottom:4;
          } Parts;
} int_parts_type;

int_parts_type MyParts;

MyParts.WholeThing = 0x1BB2;
printf("%d\n",MyParts.Parts.Middle);

What is an enumerated type?