{"id":6678,"date":"2024-11-30T00:01:37","date_gmt":"2024-11-30T08:01:37","guid":{"rendered":"https:\/\/c-for-dummies.com\/blog\/?p=6678"},"modified":"2024-12-02T21:02:49","modified_gmt":"2024-12-03T05:02:49","slug":"sorting-the-hexwords-part-ii","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=6678","title":{"rendered":"Sorting the Hexwords, Part II"},"content":{"rendered":"

The problem with the code from last week’s Lesson<\/a> is obvious: The decimal value of FEED is 1,044,205, not 2,314,885,530,818,453,605 as shown in the output. Before I can sort the list numerically, this error must be addressed.
\n
\nMy first guess was that the strtol()<\/em> function overflowed — which it did so when I tried to calculate a Look-and-Say sequence<\/a>. But overflow isn’t the problem.<\/p>\n

Scoping out the values in the code, I could see that the proper string is being translated, but not stored. So it’s most likely a silly pointer error.<\/p>\n

Check out this line from the code:<\/p>\n

list = realloc( list, sizeof(struct entry) * count+1 );<\/code><\/p>\n

This statement seeks to increase the size of the list<\/code> buffer by count<\/code> items, plus one. But due to the order of precedence, the size is increased by count<\/code> items plus one byte<\/span>. The proper statement is:<\/p>\n

list = realloc( list, sizeof(struct entry) * (count+1) );<\/code><\/p>\n

By enclosing count+1<\/code> in parentheses, the calculation properly increases the size of buffer list<\/code> by count<\/code> items (entry<\/em> structures), plus one. This new size creates enough room to store the next item in the dynamic array. The proper value is then saved, which makes the list valid. Problem solved.<\/p>\n

With the memory properly allocated, the next (and final) task is to sort the hexwords by their values. The value<\/code> member of the entry<\/em> structure is used. Here is the qsort()<\/em> function<\/a> from my code:<\/p>\n

qsort(list,count,sizeof(struct entry),compare);<\/code><\/p>\n

The items to sort are at address list<\/code>. There are count<\/code> items in the list. Each item is the size of an entry<\/em> structure. The final argument is the compare()<\/em> function, which can prove to be a bit of a pickle to code.<\/p>\n

The qsort()<\/em> compare()<\/em> function accepts two arguments, but const void<\/em> pointers, a<\/code> and b<\/code>. In the function, the trick is to convert these const void<\/em> pointers into entry<\/em> structure pointers for comparison. I cover this technique in a blog post<\/a> from two years ago. Here’s the compare()<\/em> function required:<\/p>\n

int compare(const void *a, const void *b)
\n{
\n    struct entry *x,*y;
\n 
\n    x = (struct entry *)a;
\n    y = (struct entry *)b;
\n 
\n    return( x->value - y->value );
\n}<\/code><\/p>\n

Two entry<\/em> structure pointers are declared, *x<\/code> and *y<\/code>. These are initialized to the const void<\/em> pointers a<\/code> and b<\/code> (the address arguments), but typecast to entry<\/em> structure pointers. The return value is the difference between a<\/code> and b<\/code>, but translated into the proper data type.<\/p>\n

Here is the full code:<\/p>\n

2024_11_30-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\n\/* move this outside *\/<\/span>\r\nstruct entry {\r\n    char hex[SIZE];\r\n    long value;\r\n};\r\n\r\nint compare(const void *a, const void *b)\r\n{\r\n    struct entry *x,*y;\r\n\r\n    x = (struct entry *)a;\r\n    y = (struct entry *)b;\r\n\r\n    return( x->value - y->value );\r\n}\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 *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 && 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    \/* sort the list *\/<\/span>\r\n    qsort(list,count,sizeof(struct entry),compare);\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
And the output:<\/p>\n
  1: abed            44013
\n  2: aced            44269
\n  3: babe            47806
\n  4: bade            47838
\n  5: bead            48813
\n...
\n 38: efface       15727310
\n 39: facade       16435934
\n 40: acceded     181202413
\n 41: defaced     233811181
\n 42: effaced     251636973<\/code><\/p>\n
You can’t see it in the abbreviated output above, but the value for feed<\/code> is properly translated. Though it’s the last value output alphabetically, numerically hexword effaced<\/code> has the highest value.<\/p>\n
I truly enjoyed the process of creating this program. Finding and fixing the various puzzles and addressing the unintended errors was fun! This delight is why I enjoy programming. I hope that you do as well.<\/p>\n","protected":false},"excerpt":{"rendered":"
The final program reads valid hexwords and sorts them by their values. 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-6678","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\/6678","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=6678"}],"version-history":[{"count":9,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/6678\/revisions"}],"predecessor-version":[{"id":6749,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/6678\/revisions\/6749"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=6678"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=6678"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=6678"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}