Valgrind Memcheck检测到int level定义处及后续代码存在Invalid read of size 4错误的原因排查

Hey there, let's break down the Valgrind error you're hitting at int level = head->height - 1; and the code below. This "Invalid read of size 4" typically means your code is accessing memory it shouldn't—either a null pointer, an out-of-bounds array, or uninitialized memory. Here are the most likely culprits and fixes:

1. Null head Pointer Dereference #

The very first line of your function accesses head->height. If you ever call sl_set with a NULL head pointer (e.g., before initializing your skip list), this will immediately trigger an invalid read.

Fix: Add a null check at the start of the function:

void sl_set(leapList *head, int *key, int *value) {
    if (head == NULL) {
        // Handle initialization error—either return or initialize the list here
        fprintf(stderr, "Error: Null head pointer passed to sl_set\n");
        return;
    }
    // Rest of your code...
}

2. Out-of-Bounds Access to the prev Array #

Your prev array is sized MAX_SKIPLIST_HEIGHT, but if head->height exceeds this value, level = head->height - 1 will be an index larger than the array can hold. This leads to out-of-bounds memory access, which Valgrind flags as an invalid read.

Fix:

• Ensure your skip list's head is initialized with height <= MAX_SKIPLIST_HEIGHT.
• Add a safeguard to cap the initial level:

  int level = head->height - 1;
  if (level >= MAX_SKIPLIST_HEIGHT) {
      level = MAX_SKIPLIST_HEIGHT - 1;
      fprintf(stderr, "Warning: Head height exceeds MAX_SKIPLIST_HEIGHT, capping level\n");
  }
  

3. Incorrect Key Comparison (Pointer vs. Value) #

You commented out the string comparison and replaced it with pointer equality checks like (curr->next[level]->key) == key. This compares the memory addresses of the key pointers, not the actual integer values they point to.

This logic error can cause your search loop to behave unpredictably: it might fail to find existing keys, leading to unnecessary inserts, or traverse to invalid parts of the list. Over time, this can lead to accessing uninitialized or freed memory.

Fix: Compare the integer values instead of the pointers:

// Replace pointer comparisons with value comparisons
int curr_key = *(curr->next[level]->key);
int target_key = *key;

if (curr_key == target_key) {
    // Found match—replace value
    free(curr->next[level]->value);
    curr->next[level]->value = value;
    return;
} else if (curr_key > target_key) {
    // Move down a level
    --level;
} else {
    // Move forward on current level
    curr = curr->next[level];
}

4. Incomplete Initialization of new_entry->next #

Your loop to initialize new_entry->next has an off-by-one error. Right now, it only sets pointers to NULL when i > new_entry->height, but the index equal to new_entry->height remains uninitialized (garbage memory). When this uninitialized pointer is accessed later, Valgrind will flag it as an invalid read.

Fix: Adjust the loop condition to cover all indices >= new_entry->height:

// Fix: Use >= instead of > to include the index equal to new_entry->height
for (i = MAX_SKIPLIST_HEIGHT - 1; i >= new_entry->height; --i) {
    new_entry->next[i] = NULL;
}

5. Uninitialized prev Entries (Edge Case) #

In rare cases, if your search loop skips levels without setting prev[level], you might end up accessing uninitialized values in the prev array during insertion. While your current loop sets prev[level] = curr at the start of each iteration, double-check that all levels from 0 to new_entry->height - 1 have valid entries in prev. If head->height is smaller than new_entry->height, you'll need to ensure those higher levels in prev point to the head node.

Quick Check: Before insertion, verify that for all i from 0 to new_entry->height - 1, prev[i] is not NULL. If not, set prev[i] = head for those levels.

内容的提问来源于stack exchange，提问作者JamesJohn990