learning-cc4e

Solution to https://cc4e.com/. If you copy these you're not right in the head.
git clone https://kaka.farm/~git/learning-cc4e
Log | Files | Refs

solution.c (2897B)

      1 void __TreeMap_put(struct TreeMap* self, char *key, int value) {
      2   struct TreeMapEntry *cur, *left, *right;
      3   int cmp;
      4   struct TreeMapEntry *old, *new;
      5   char *new_key;
      6 
      7   cur = self->__root;
      8   left = NULL;
      9   right = NULL;
     10 
     11   /* TODO: Loop through the tree from the root.  If the matches
     12    * the node, update the value and return.  Ad the tree is scanned,
     13    * keep track of the node containing largest key less than "key"
     14    * in the variable left and the node containing the smallest key
     15    * greater than "key" in the variable "right".  So if the key is
     16    * not found, left will be the closest lower neighbor or null
     17    * and right will be the closest greater neighbor or null.
     18    */
     19 
     20   while (cur != NULL) {
     21     cmp = strcmp(key, cur->key);
     22     if (cmp == 0) {
     23       cur->value = value;
     24       return;
     25     }
     26 
     27     old = cur;
     28 
     29     if (cmp < 0) {
     30       right = cur;
     31       cur = cur->__left;
     32     }
     33 
     34     if (cmp > 0) {
     35       left = cur;
     36       cur = cur->__right;
     37     }
     38   }
     39 
     40   ++self->__count;
     41 
     42   /* Not found - time to insert into the linked list after old */
     43   new = malloc(sizeof(*new));
     44 
     45   /* TODO: Set up the new node with its new data. */
     46   new_key = malloc(sizeof(*new_key) * (strlen(key) + 1));
     47   new_key = strcpy(new_key, key);
     48   new->key = new_key;
     49   new->value = value;
     50   new->__next = NULL;
     51   new->__left = NULL;
     52   new->__right = NULL;
     53 
     54   /* Empty list - add first entry */
     55   if ( self->__head == NULL ) {
     56     self->__head = new;
     57     self->__root = new;
     58     return;
     59   }
     60 
     61   /* Keep this in here - it will help you debug the above code */
     62   __Map_check(self, left, key, right);
     63 
     64   /* TODO: Insert into the sorted linked list */
     65   if (left == NULL) {
     66     new->__next = self->__head;
     67     self->__head = new;
     68   } else if (right == NULL) {
     69     left->__next = new;
     70   } else {
     71     new->__next = right;
     72     left->__next = new;
     73   }
     74 
     75   /* TODO: Insert into the tree */
     76   if (cmp > 0) {
     77     old->__right = new;
     78   } else {
     79     old->__left = new;
     80   }
     81 }
     82 
     83 int __TreeMap_get(struct TreeMap* self, char *key, int def)
     84 {
     85   int cmp;
     86   struct TreeMapEntry *cur;
     87 
     88   if ( self == NULL || key == NULL || self->__root == NULL ) return def;
     89 
     90   cur = self->__root;
     91 
     92   /* TODO: scan down the tree and if the key is found, return the value.
     93    * If the key is not found, return the default value (def).
     94    */
     95 
     96   while (cur != NULL) {
     97     cmp = strcmp(key, cur->key);
     98     if (cmp == 0) {
     99       return cur->value;
    100     } else if (cmp < 0) {
    101       cur = cur->__left;
    102     } else {
    103       cur = cur->__right;
    104     }
    105   }
    106 
    107   return def;
    108 }
    109 
    110 struct TreeMapEntry* __TreeMapIter_next(struct TreeMapIter* self)
    111 {
    112   /* Advance the iterator.  Recall that when we first
    113    * create the iterator __current points to the first item
    114    * so we must return an item and then advance the iterator.
    115    */
    116   struct TreeMapEntry *cur = self->__current;
    117   if (self->__current != NULL) {
    118     self->__current = cur->__next;
    119   }
    120   return cur;
    121 }