{"id":6673,"date":"2024-11-23T00:01:22","date_gmt":"2024-11-23T08:01:22","guid":{"rendered":"https:\/\/c-for-dummies.com\/blog\/?p=6673"},"modified":"2024-11-30T09:17:05","modified_gmt":"2024-11-30T17:17:05","slug":"sorting-the-hexwords-part-i","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=6673","title":{"rendered":"Sorting the Hexwords, Part I"},"content":{"rendered":"

The Linux dictionary stores its words sorted alphabetically. Therefore, the output from the program presented in last week’s Lesson<\/a> shows valid hexwords (letters A through F, four letters or longer) in alphabetic order. But what if I want the words output in numerical order?
\n
\nNo correlation exists between a hexadecimal value’s alphabetic sort and its numeric sort. For example DECAF is 912,559 but DEED is 57,069. Alphabetically, DEED is higher but numerically DEFAC is higher. If I desire to sort the hexword output by value, I must collect all the words first, then sort them by value before outputting the results. Accomplishing this task requires some rewriting of the code from last week’s Lesson.<\/p>\n

To build a list of valid hexwords I define a structure:<\/p>\n

struct entry {
\n    char hex[SIZE];
\n    long value;
\n}<\/code><\/p>\n

The entry<\/em> structure contains members for both the hexword as well as its value. This second member (value<\/code>) may seem redundant because the hex[SIZE]<\/code> member is a hex value, albeit in a string. However, storing only the hexword string requires a double-pointer if I’m creating a dynamic list. No, using a structure requires fewer brain cells.<\/p>\n

Based on last week’s Lesson, I know that just over 40 valid hexwords exist in the Linux dictionary. Even so, I opted to dynamically allocate the structures: Each time a valid hexword is found, storage for a new structure is allocated in memory. I could have worked this operation as a linked list, but opted instead to use offsets within a single memory chunk — like a dynamic array.<\/p>\n

Here’s the code:<\/p>\n

2024_11_23-Lesson.c<\/a><\/h3>\n
\r\n\/* Hex Words *\/<\/span>\r\n#include <stdio.h>\r\n#include <stdlib.h>\r\n#include <string.h>\r\n\r\n\/* this code assumes the following path is valid *\/<\/span>\r\n#define DICTIONARY \"\/usr\/share\/dict\/words\"\r\n#define SIZE 32\r\n\r\nint main()\r\n{\r\n    FILE *dict;\r\n    char word[SIZE],hexword[SIZE],*r,*w;\r\n    int count,x;\r\n    struct entry {\r\n        char hex[SIZE];\r\n        long value;\r\n    } *list;\r\n\r\n    \/* open the dictionary *\/<\/span>\r\n    dict = fopen(DICTIONARY,\"r\");\r\n    if( dict==NULL )\r\n    {\r\n        fprintf(stderr,\"Unable to open %s\\n\",DICTIONARY);\r\n        exit(1);\r\n    }\r\n\r\n    \/* read the dictionary *\/<\/span>\r\n    count = 0;\r\n    while( !feof(dict) )\r\n    {\r\n        \/* read a word from the dictionary *\/<\/span>\r\n        r = fgets(word,SIZE,dict);\r\n        if( r==NULL )    \/* no word, done *\/<\/span>\r\n            break;\r\n\r\n        \/* remove newline *\/<\/span>\r\n        w = word;\r\n        while(*w)\r\n        {\r\n            if( *w=='\\n' )\r\n            {\r\n                *w = '\\0';\r\n                break;\r\n            }\r\n            w++;\r\n        }\r\n\r\n        \/* pull out only hex characters *\/<\/span>\r\n        sscanf(word,\"%[ABCDEFabcdef]\",hexword);\r\n\r\n        \/* compare hexword with original word *\/<\/span>\r\n        if( strcmp(word,hexword)==0 )\r\n        {\r\n            if( strlen(hexword) > 3 )\r\n            {\r\n                if( count==0 )\r\n                {\r\n                    list = malloc( sizeof(struct entry) );\r\n                    if( list==NULL )\r\n                    {\r\n                        fprintf(stderr,\"Unable to allocate memory\\n\");\r\n                        exit(1);\r\n                    }\r\n                    strcpy( list->hex,hexword );\r\n                    list->value = strtol(hexword,NULL,16);\r\n                }\r\n                else\r\n                {\r\n                    list = realloc( list, sizeof(struct entry) * count+1 );\r\n                    if( list==NULL )\r\n                    {\r\n                        fprintf(stderr,\"Unable to reallocate memory\\n\");\r\n                        exit(1);\r\n                    }\r\n                    strcpy( (list+count)->hex,hexword );\r\n                    (list+count)->value = strtol(hexword,NULL,16);\r\n                }\r\n                count++;\r\n            }\r\n        }\r\n    }\r\n\r\n    \/* output the list *\/<\/span>\r\n    for( x=0; x<count; ++x )\r\n        printf(\"%3d: %-10s %10ld\\n\",\r\n                x+1,\r\n                (list+x)->hex,\r\n                (list+x)->value\r\n              );\r\n\r\n    \/* clean-up *\/<\/span>\r\n    fclose(dict);\r\n    free(list);\r\n    return(0);\r\n}<\/pre>\n
The entry<\/em> structure is declared as a pointer, *list<\/code>. This pointer isn’t accessed until the first valid hexword is found. (Line 55 in the code.)<\/p>\n
An if<\/em> statement tests whether variable count<\/code> is equal to zero, which means the list is just starting. When true, the malloc()<\/em> function initially allocates storage for one entry<\/em> structure at address list<\/code>. The hexword is copied into the list->hex<\/code> member and its value converted and stored in list->value<\/code>.<\/p>\n
The else<\/em> condition uses the realloc()<\/em> function to expand the list beyond the first entry. It adds new hexwords and their values as encountered:<\/p>\n
list = realloc( list, sizeof(struct entry) * count+1 );<\/code><\/p>\n
The word and its value are copied into the structure at an offset (count<\/code>) within the list<\/code> memory chunk.<\/p>\n
After the dictionary is scanned, and the list built, a for<\/em> loop outputs the contents, names and values of all the hexwords in the list. The list<\/em> buffer is then freed. Stuff is cleaned up. The program ends.<\/p>\n
Here is the output, which should match the same output as shown in last week’s Lesson:<\/p>\n
  1: Bede            48862
\n  2: Beebe          782014
\n  3: DECed          912621
\n  4: Dacca          896202
\n  5: Dada            56026
\n...
\n 38: face            64206
\n 39: faced         1027309
\n 40: fade            64222
\n 41: faded         1027565
\n 42: feed       2314885530818453605<\/code><\/p>\n
The output is almost the same . . . except for that final value. Obviously, hex value FEED<\/code> isn’t equal to 2,314,885,530,818,453,605!<\/p>\n
See if you can find the error in the code. It took me a while, but it’s in there. I’ll reveal where in next week’s Lesson<\/a>. I’ll also add the code that sorts the output numerically.<\/p>\n","protected":false},"excerpt":{"rendered":"
Sorting the list of hexwords requires a bit more work than I originally anticipated. Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-6673","post","type-post","status-publish","format-standard","hentry","category-main"],"_links":{"self":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/6673","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=6673"}],"version-history":[{"count":6,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/6673\/revisions"}],"predecessor-version":[{"id":6726,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/6673\/revisions\/6726"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=6673"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=6673"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=6673"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}