C / C++ / 系统课时

删除任务并同步多个结构

删除任务并同步多个结构

一个内存任务管理器往往同时用链表保存任务、哈希表按 ID 定位、最大堆负责优先级调度。删除任务时只改其中一个结构会留下悬空指针或“幽灵任务”。本节用同一任务对象被多个结构引用的方式,完成一次一致的删除操作。

学习目标

  • 理解多种数据结构共享同一批任务时的一致性风险。
  • 实现“哈希定位 → 移出堆 → 移除索引 → 脱链 → 释放内存”的删除流程。
  • 能通过不变量和验证步骤发现悬空指针、重复记录与遗漏更新。

一致性问题的本质

链表、哈希表和优先队列解决的是不同问题:链表便于遍历全部任务,哈希表便于按 ID 查找,最大堆便于取得最高优先级。最安全的做法不是在三个结构里复制三份 Task,而是只分配一个 Task 对象,让各结构保存它的指针。

删除时必须先让所有结构停止引用该对象,最后才能 free。如果先释放内存,再去更新堆或哈希表,后续访问就是未定义行为;如果漏掉某个结构,则查询结果和调度结果会互相矛盾。

删除任务时同步三个结构的流程

把位置元数据放回任务对象

为了让最大堆删除任意任务仍保持 O(log⁡n)O(\log n),任务对象记录 heapIndex。堆交换两个元素时同步更新这两个索引,因此通过哈希表拿到 Task * 后,可以直接定位它在堆中的位置,不必再做 O(n)O(n) 扫描。

下面的完整示例使用双向链表保存全部任务、拉链哈希表按 ID 索引、最大堆调度优先级。删除函数本身不申请新内存,因此找到任务后,各更新步骤都可以在已有数据上完成。

c
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define HEAP_CAPACITY 16
#define HASH_SIZE 17

typedef struct Task {
    int id;
    const char *title;
    int priority;
    size_t heapIndex;
    struct Task *prev;
    struct Task *next;
    struct Task *hashNext;
} Task;

typedef struct {
    Task *items[HEAP_CAPACITY];
    size_t size;
} MaxHeap;

typedef struct {
    Task *head;
    Task *buckets[HASH_SIZE];
    MaxHeap heap;
    size_t count;
} TaskManager;

static size_t hash_id(int id) {
    return (size_t)id % HASH_SIZE;
}

static void heap_swap(MaxHeap *heap, size_t a, size_t b) {
    Task *tmp = heap->items[a];
    heap->items[a] = heap->items[b];
    heap->items[b] = tmp;
    heap->items[a]->heapIndex = a;
    heap->items[b]->heapIndex = b;
}

static void sift_up(MaxHeap *heap, size_t index) {
    while (index > 0) {
        size_t parent = (index - 1) / 2;
        if (heap->items[parent]->priority >= heap->items[index]->priority) {
            break;
        }
        heap_swap(heap, parent, index);
        index = parent;
    }
}

static void sift_down(MaxHeap *heap, size_t index) {
    for (;;) {
        size_t left = index * 2 + 1;
        size_t right = index * 2 + 2;
        size_t largest = index;

        if (left < heap->size &&
            heap->items[left]->priority > heap->items[largest]->priority) {
            largest = left;
        }
        if (right < heap->size &&
            heap->items[right]->priority > heap->items[largest]->priority) {
            largest = right;
        }
        if (largest == index) {
            break;
        }

        heap_swap(heap, index, largest);
        index = largest;
    }
}

static bool heap_push(MaxHeap *heap, Task *task) {
    if (heap->size == HEAP_CAPACITY) {
        return false;
    }

    task->heapIndex = heap->size;
    heap->items[heap->size] = task;
    heap->size++;
    sift_up(heap, task->heapIndex);
    return true;
}

static void heap_remove(MaxHeap *heap, Task *task) {
    size_t index = task->heapIndex;
    size_t last = heap->size - 1;

    if (index != last) {
        heap_swap(heap, index, last);
    }
    heap->size--;

    if (index < heap->size) {
        size_t parent = index == 0 ? 0 : (index - 1) / 2;
        if (index > 0 &&
            heap->items[index]->priority > heap->items[parent]->priority) {
            sift_up(heap, index);
        } else {
            sift_down(heap, index);
        }
    }
}

static Task *hash_find(TaskManager *manager, int id) {
    Task *cur = manager->buckets[hash_id(id)];
    while (cur != NULL && cur->id != id) {
        cur = cur->hashNext;
    }
    return cur;
}

static void hash_insert(TaskManager *manager, Task *task) {
    size_t bucket = hash_id(task->id);
    task->hashNext = manager->buckets[bucket];
    manager->buckets[bucket] = task;
}

static void hash_remove(TaskManager *manager, Task *task) {
    size_t bucket = hash_id(task->id);
    Task **link = &manager->buckets[bucket];

    while (*link != NULL && *link != task) {
        link = &(*link)->hashNext;
    }
    if (*link == task) {
        *link = task->hashNext;
    }
}

static bool add_task(TaskManager *manager, int id,
                     const char *title, int priority) {
    if (hash_find(manager, id) != NULL) {
        return false;
    }

    Task *task = malloc(sizeof(*task));
    if (task == NULL) {
        return false;
    }

    *task = (Task){
        .id = id,
        .title = title,
        .priority = priority,
        .prev = NULL,
        .next = manager->head,
        .hashNext = NULL
    };

    if (!heap_push(&manager->heap, task)) {
        free(task);
        return false;
    }

    if (manager->head != NULL) {
        manager->head->prev = task;
    }
    manager->head = task;
    hash_insert(manager, task);
    manager->count++;
    return true;
}

static bool delete_task(TaskManager *manager, int id) {
    Task *task = hash_find(manager, id);
    if (task == NULL) {
        return false;
    }

    /* 先清理所有外部引用,最后才释放任务对象。 */
    heap_remove(&manager->heap, task);
    hash_remove(manager, task);

    if (task->prev != NULL) {
        task->prev->next = task->next;
    } else {
        manager->head = task->next;
    }
    if (task->next != NULL) {
        task->next->prev = task->prev;
    }

    manager->count--;
    free(task);
    return true;
}

static void destroy_manager(TaskManager *manager) {
    Task *cur = manager->head;
    while (cur != NULL) {
        Task *next = cur->next;
        free(cur);
        cur = next;
    }
}

int main(void) {
    TaskManager manager = {0};

    if (!add_task(&manager, 201, "修复支付告警", 100) ||
        !add_task(&manager, 202, "整理周报", 30) ||
        !add_task(&manager, 203, "更新依赖", 70)) {
        fprintf(stderr, "初始化任务失败\n");
        destroy_manager(&manager);
        return 1;
    }

    printf("删除前最高优先级: #%d %s\n",
           manager.heap.items[0]->id,
           manager.heap.items[0]->title);

    printf("删除 #201: %s\n",
           delete_task(&manager, 201) ? "成功" : "失败");

    printf("哈希索引查找 #201: %s\n",
           hash_find(&manager, 201) == NULL ? "不存在" : "仍存在");

    printf("删除后最高优先级: #%d %s\n",
           manager.heap.items[0]->id,
           manager.heap.items[0]->title);

    printf("当前任务数: %zu\n", manager.count);

    destroy_manager(&manager);
    return 0;
}

预期输出

text
删除前最高优先级: #201 修复支付告警
删除 #201: 成功
哈希索引查找 #201: 不存在
删除后最高优先级: #203 更新依赖
当前任务数: 2

删除顺序为什么重要

推荐顺序是先通过哈希表定位对象,再从最大堆移除、从哈希索引移除、从链表脱链,最后释放内存。这里最重要的规则不是某个具体容器先于另一个,而是 free 必须最后发生,并且函数返回成功前,所有结构都不再引用目标对象。

heap_remove 还要维护另一个不变量:每次交换堆元素,都必须同步两个任务的 heapIndex。只交换指针却忘记更新索引,会让下一次按 ID 删除任务时定位到错误位置,随后可能删除无关任务。

如何验证多个结构已经同步

删除成功至少要验证三个维度:哈希查找不到该 ID;堆顶和后续调度中不再出现该任务;链表遍历计数与管理器的 count 一致。示例已经验证前两项和总数,项目中还可以在调试构建里加入遍历断言,持续检查“链表任务数 = 哈希可达任务数 = 堆元素数”。

如果以后加入“修改优先级”“批量删除”或“持久化”,仍应先定义这些跨结构不变量,再设计更新顺序。单个数据结构的操作正确,不等于整个任务管理器状态一致;真正需要维护的是多个视图对同一个任务集合的共同约束。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

删除任务并同步多个结构

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通