qsort() 导致分段错误

Question

我的任务是在 C 中实现类型安全的动态向量结构；但是，我似乎遇到了一个问题：每次我使用 qsort() 然后尝试将变量转换为 int* （在 erase_value() 和 print_vector_int() 中）我得到一个分段错误。

示例输入：

这按预期工作，但是，一旦我使用 qsort()，erase_value() 或 print_vector_int() 中断。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_STR_LEN 64

typedef struct Vector {
    void **data;
    size_t element_size;
    size_t size;
    size_t capacity;
} Vector;

// Allocate vector to initial capacity (block_size elements),
// Set element_size, size (to 0), capacity
void init_vector(Vector *vector, size_t block_size, size_t element_size) {
    vector->data = (void **)malloc(sizeof(void *) * block_size);
    vector->element_size = element_size;
    vector->capacity = block_size;
    vector->size = 0;
}

// If new_capacity is greater than the current capacity,
// new storage is allocated, otherwise the function does nothing.
void reserve(Vector *vector, size_t new_capacity) {
    if (vector->capacity < new_capacity) {
        vector->capacity = new_capacity;
        vector->data = (void **)realloc(vector->data, sizeof(void *) * (vector->capacity));
    }
}

// Resizes the vector to contain new_size elements.
// If the current size is greater than new_size, the container is
// reduced to its first new_size elements.

// If the current size is less than new_size,
// additional zero-initialized elements are appended
void resize(Vector *vector, size_t new_size) {
    if (new_size <= vector->size) {
        for (size_t i = vector->size; i > new_size; --i) {
            free(vector->data[i]);
        }
        vector->size = new_size;
    } else {
        if (new_size > vector->capacity) {
            vector->capacity = (vector->capacity) * 2;
            vector->data = (void **)realloc(vector->data, sizeof(void *) * vector->capacity);
        }
        for (size_t i = vector->size; i < new_size; ++i) {
            vector->data[i] = (void *)calloc(1, vector->element_size);
        }
        vector->size = new_size;
    }
}

// Insert new element at index (0 <= index <= size) position
void insert(Vector *vector, int index, void *value) {
    if (index >= vector->capacity) {
        vector->capacity = vector->capacity * 2;
        vector-> data = (void **)realloc(vector->data, sizeof(void *) * (vector->capacity));
    }
    
    if (index >= 0 && index <= vector->size) {
        vector->data[vector->size] = (void *)malloc(vector->element_size);
       for (size_t i = vector->size; i > index; --i) {
           memcpy(vector->data[i], vector->data[i - 1], vector->element_size);
       }
       memcpy(vector->data[index], value, vector->element_size);
       ++(vector->size);
    }
}

// Add element to the end of the vector
void push_back(Vector *vector, void *value) {
    if (vector->size == 0)
        insert(vector, 0, value);
    else
        insert(vector, vector->size, value);
}

// Remove all elements from the vector
void clear(Vector *vector) {
    for (int i = (vector->size) - 1; i >= 0; --i) {
        free(vector->data[i]);
    }
    vector->size = 0;
}

// Erase element at position index
void erase(Vector *vector, int index) {
    for (size_t i = index; i < vector->size - 1; ++i) {
        memcpy(vector->data[i], vector->data[i + 1], vector->element_size);
    }
    free(vector->data[vector->size - 1]);
    --(vector->size);
}

// Erase all elements that compare equal to value from the container
void erase_value(Vector *vector, void *value, int(*cmp)(const void *, const void *)) {
    for(size_t i = 0; i < vector->size; ++i) {
        if (cmp(vector->data[i], value) == 0)
            erase(vector, i);
    }
}

// Erase all elements that satisfy the predicate from the vector
void erase_if(Vector *vector, int (*predicate)(void *)) {
    for (size_t i = 0; i < vector->size; ++i) {
        if (predicate(vector->data[i]))
            erase(vector, i);
    }
}

// Request the removal of unused capacity
void shrink_to_fit(Vector *vector) {
    vector->capacity = vector->size;
    vector->data = (void **)realloc(vector->data, sizeof(void *) * (vector->capacity));
}

// Print integer vector
void print_vector_int(Vector *vector) {
    printf("%ld\n", vector->capacity);
    for (int i = 0;i < vector->size; ++i) {
        int item = *(int *)vector->data[i];
        printf("%d ", item);
    }
}

int int_cmp(const void *v1, const void *v2) {
    const int aa = *(const int *)v1;
    const int bb = *(const int *)v2;
    return aa - bb;
}

int is_even(void *value) {
    const int aa = *(int *)value;
    return aa % 2 == 0;
}

void read_int(void *value) {
    scanf("%d", (int *)value);
}

void vector_test(Vector *vector, int n, void (*read)(void *),
         int (*cmp)(const void *, const void *), int (*predicate)(void *)) {
    char op[2];
    int index;
    size_t size;
    void *v = malloc(vector->element_size);
    for (int i = 0; i < n; ++i) {
        scanf("%s", op);
        switch (op[0]) {
          case 'p': // push_back
            read(v);
            push_back(vector, v);
            break;
          case 'i': // insert
            scanf("%d", &index);
            read(v);
            insert(vector, index, v);
            break;
          case 'e': // erase
            scanf("%d", &index);
            read(v);
            erase(vector, index);
            erase_value(vector, v, cmp);
            break;
          case 'd': // erase (predicate)
            erase_if(vector, predicate);
            break;
          case 'r': // resize
            scanf("%zu", &size);
            resize(vector, size);
            break;
          case 'c': // clear
            clear(vector);
            break;
          case 'f': // shrink
            shrink_to_fit(vector);
            break;
          case 's': // sort
            qsort(vector->data, vector->size,
                  vector->element_size, cmp);
            break;
          default:
            printf("No such operation: %s\n", op);
            break;
        }
    }
    free(v);
}

int main(void) {
    int n;
    Vector vector_int;
    scanf("%d", &n);
    init_vector(&vector_int, 4, sizeof(int));
    vector_test(&vector_int, n, read_int, int_cmp, is_even);
    print_vector_int(&vector_int);
    free(vector_int.data);
    return 0;
}

我怀疑这可能是 int_cmp() 的问题，因为对排序列表进行 q 排序不会导致段错误。

Answer 1

您的代码中存在多个问题：

您在指向已分配块的指针数组而不是元素数组上使用 qsort。您的向量的几何形状不适合 qsort 具有编码的比较功能。
在函数 resize 中，释放元素的循环从 vector->size 开始，并访问未分配的此偏移量处的元素。向下循环的正确写法是：
```
  for (size_t i = vector->size; i-- > new_size;) {
      free(vector->data[i]);
  }
```
在erase_value和erase_if中你不应该在删除匹配元素时递增i。
int_cmp 不应依赖于减去值：对于相反符号的大值，此减法可能会溢出。

您应该更改向量的实现以分配元素数组而不是指向已分配字节数组的指针数组。

这是修改后的版本：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Vector {
    void *data;
    size_t element_size;
    size_t size;
    size_t capacity;
} Vector;

#define VP(v, i)  ((void *)((unsigned char *)(vector)->data + (i) * (vector)->element_size))

// Allocate vector to initial capacity (block_size elements),
// Set element_size, size (to 0), capacity
void init_vector(Vector *vector, size_t capacity, size_t element_size) {
    vector->data = calloc(capacity, element_size);
    vector->element_size = element_size;
    vector->capacity = capacity;
    vector->size = 0;
}

// Free vector data
void free_vector(Vector *vector) {
    free(vector->data);
    vector->data = NULL;
    vector->size = vector->capacity = 0;
}

// If new_capacity is greater than the current capacity,
// new storage is allocated, otherwise the function does nothing.
void reserve(Vector *vector, size_t new_capacity) {
    if (vector->capacity < new_capacity) {
        vector->data = realloc(vector->data, new_capacity * vector->element_size);
        vector->capacity = new_capacity;
    }
}

// Resizes the vector to contain new_size elements.
// If the current size is greater than new_size, the container is
// reduced to its first new_size elements.
// If the current size is less than new_size,
// additional zero-initialized elements are appended
void resize(Vector *vector, size_t new_size) {
    if (new_size > vector->size) {
        if (new_size > vector->capacity) {
            size_t new_capacity = vector->capacity * 2;
            while (new_size > new_capacity) {
                new_capacity = new_capacity * 2;
            }
            vector->data = realloc(vector->data, new_capacity * vector->element_size);
            vector->capacity = new_capacity;
        }
        memset(VP(vector, vector->size), 0, (new_size - vector->size) * vector->element_size);
    }
    vector->size = new_size;
}

// Insert new element at index (0 <= index <= size) position
void insert(Vector *vector, size_t index, void *value) {
    if (index <= vector->size) {
        if (vector->size == vector->capacity) {
            resize(vector, vector->size + 1);
        }
        memmove(VP(vector, index + 1), VP(vector, index),
                (vector->size - index) * vector->element_size);
        memmove(VP(vector, index), value, vector->element_size);
        vector->size += 1;
    }
}

// Add element to the end of the vector
void push_back(Vector *vector, void *value) {
    insert(vector, vector->size, value);
}

// Remove all elements from the vector
void clear(Vector *vector) {
    vector->size = 0;
}

// Erase element at position index
void erase(Vector *vector, size_t index) {
    if (index < vector->size) {
        memmove(VP(vector, index), VP(vector, index + 1),
                (vector->size - index - 1) * vector->element_size);
        vector->size -= 1;
    }
}

// Erase all elements that compare equal to value from the container
void erase_value(Vector *vector, void *value, int (*cmp)(const void *, const void *)) {
    for (size_t i = 0; i < vector->size;) {
        if (cmp(VP(vector, i), value) == 0) {
            erase(vector, i);
        } else {
            i++;
        }
    }
}

// Erase all elements that satisfy the predicate from the vector
void erase_if(Vector *vector, int (*predicate)(void *)) {
    for (size_t i = 0; i < vector->size;) {
        if (predicate(VP(vector, i))) {
            erase(vector, i);
        } else {
            i++;
        }
    }
}

// Print all elements of the vector
void print_vector(Vector *vector, void (*print)(void *)) {
    printf("%zu %zu {", vector->size, vector->capacity);
    for (size_t i = 0; i < vector->size; i++) {
        printf(" ");
        print(VP(vector, i));
    }
    printf(" }\n");
}

// Request the removal of unused capacity
void shrink_to_fit(Vector *vector) {
    vector->capacity = vector->size;
    vector->data = realloc(vector->data, vector->capacity * vector->element_size);
}

// Print integer vector
void int_print(void *p) {
    int item = *(int *)p;
    printf("%d", item);
}

int int_cmp(const void *v1, const void *v2) {
    const int aa = *(const int *)v1;
    const int bb = *(const int *)v2;
    return (aa > bb) - (aa < bb);
}

int is_even(void *value) {
    const int aa = *(const int *)value;
    return aa % 2 == 0;
}

void read_int(void *value) {
    int *vp = (int *)value;
    *vp = 0;
    scanf("%d", vp);
}

void vector_test(Vector *vector, int n,
                 void (*read)(void *),
                 int (*cmp)(const void *, const void *),
                 int (*predicate)(void *),
                 void (*print)(void *))
{
    char op[2];
    size_t index, size;
    void *v = malloc(vector->element_size);
    for (int i = 0; i < n; ++i) {
        if (scanf("%1s", op) != 1)
            break;
        switch (op[0]) {
        case 'p': // push_back
            read(v);
            push_back(vector, v);
            break;
        case 'i': // insert
            scanf("%zu", &index);
            read(v);
            insert(vector, index, v);
            break;
        case 'e': // erase
            scanf("%zu", &index);
            read(v);
            erase(vector, index);
            erase_value(vector, v, cmp);
            break;
        case 'd': // erase (predicate)
            erase_if(vector, predicate);
            break;
        case 'r': // resize
            scanf("%zu", &size);
            resize(vector, size);
            break;
        case 'c': // clear
            clear(vector);
            break;
        case 'f': // shrink
            shrink_to_fit(vector);
            break;
        case '=': // print
            print_vector(vector, print);
            break;
        case 's': // sort
            qsort(vector->data, vector->size,
                  vector->element_size, cmp);
            break;
        default:
            printf("No such operation: %s\n", op);
            break;
        }
    }
    free(v);
}

int main() {
    Vector vector_int[1];
    int n = 0;

    if (scanf("%d", &n) == 1) {
        init_vector(vector_int, 4, sizeof(int));
        vector_test(vector_int, n, read_int, int_cmp, is_even, int_print);
        print_vector(vector_int, int_print);
        free_vector(vector_int);
    }
    return 0;
}

qsort() 导致分段错误

qsort() results in segmentation fault

c

casting

vector

segmentation-fault

dynamic-memory-allocation