How to increment several numeric keys of a hash-table

Question

Q: How to programmatically increment several numeric keys of a hash-table.

Background:

I am working on a modificion of speedbar to support the concept of speedbar-get-marked-files -- speedbar -- mark/unmark directories/files -- `speedbar-get-marked-files` I have setup a hash-table that consists of buffer line numbers for the keys, and the values are absolute filenames or directories.

When clicking on a + sign to expand directories, speedbar inserts additional files and directories underneath the expanded node. It is at this point that the hash-table needs to be modified, since puthash replaces existing entries. Programmatically, I already know how many new lines will be inserted.

Example:

A buffer contains 9 lines (in this case all directories), with a corresponding hash-table.

1  "/usr/"
2  "/usr/bin"
3  "/usr/include"
4  "/usr/lib"
5  "/usr/libexec"
6  "/usr/local"
7  "/usr/man"
8  "/usr/sbin"
9  "/usr/share"

We click on the expandable directory /usr/lib and programmatically we know that 8 new directories and 27 new files will be inserted. Therefore, a total of 35 new lines will be added underneath line 4 -- the previous hash-table entries of 5, 6, 7, 8 and 9 all need to be renumbered by adding 35 to each one. The new hash-table should become:

1  "/usr/"
2  "/usr/bin"
3  "/usr/include"
4  "/usr/lib"
40  "/usr/libexec"
41  "/usr/local"
42  "/usr/man"
43  "/usr/sbin"
44  "/usr/share"

Hash table entries aren't in any defined order, so "previous" entries is kind of meaningless. Maybe hash tables are the wrong data structure for this? — npostavs, Jul 12 '15 at 17:34
@npostavs -- Thank you for helping me understand that hash-table entries are not in any particular order. I still need to please learn how to programmatically efficiently change 5 to 40, 6 to 41, 7 to 42, 8 to 43, and 9 to 44. The data structure is used by a different major-mode that is analogous to several components of speedbar, and I'm already familiar with how to obtain the line number if I know the absolute filename, and how to obtain the absolute filename if I know the line number. I would prefer not relying upon querying text-properties to obtain the line number or filename. — lawlist, Jul 12 '15 at 17:54
Sounds like want you need is an array, no renumbering needed. — politza, Jul 12 '15 at 21:25

wvxvw · Answer 1 · 2015-07-12T18:43:56.557

As npostavs said, it would probably make more sense to use another datastructure, perhaps a B-tree or some other kind of tree, where you wouldn't need to do massive insert / remove operations. Below, however, is a simple example of how one can go about doing this while still using a hash-table:

(let ((example (make-hash-table))
      (offset 5)
      (increment 3))
  (cl-loop for i below 10 do (puthash i (format "value: %d" i) example))
  (cl-loop for k being the hash-keys of example using (hash-values v) do
           (message "before %s => %s" k v))
  (cl-loop for (k . v) in
           (cl-loop for k being the hash-keys of example using (hash-values v)
                    when (> k offset) do
                    (remhash k example)
                    and collect (cons k v))
           do (puthash (+ k increment) v example))
  (cl-loop for k being the hash-keys of example using (hash-values v) do
           (message "after %s => %s" k v)))

;; before 0 => value: 0
;; before 1 => value: 1
;; before 2 => value: 2
;; before 3 => value: 3
;; before 4 => value: 4
;; before 5 => value: 5
;; before 6 => value: 6
;; before 7 => value: 7
;; before 8 => value: 8
;; before 9 => value: 9

;; after 0 => value: 0
;; after 1 => value: 1
;; after 2 => value: 2
;; after 3 => value: 3
;; after 4 => value: 4
;; after 5 => value: 5
;; after 12 => value: 9
;; after 11 => value: 8
;; after 10 => value: 7
;; after 9 => value: 6

Note that there's a caveat: if you increase the key in the same loop, you may accidentally overwrite the value with higher key value.

All three (3) answers work, but I could only choose one. I will continue to study your example to eventually understand what makes it tick -- it's got a few components that are beyond my present level. I'll review and work on it in my spare time. As always, your help is greatly appreciated! — lawlist, Jul 12 '15 at 20:32

npostavs · Accepted Answer · 2015-07-13T07:48:07.903

1

If you know the top index, and you know that the indices are consecutive it might be more efficient to loop over those specific indices:

(let ((table #s(hash-table size 65 test eql rehash-size 1.5 rehash-threshold 0.8 data
                           (1 "/usr/" 2 "/usr/bin" 3 "/usr/include" 4 "/usr/lib" 5 "/usr/libexec"
                              6 "/usr/local" 7 "/usr/man" 8 "/usr/sbin" 9 "/usr/share")))
      (lo 5)
      (hi 9)
      (inc 35))
  (if (cl-plusp inc)
      (cl-loop for i from hi downto lo
               do (puthash (+ i inc) (gethash i table) table))
    (cl-loop for i from lo upto hi
             do (puthash (+ i inc) (gethash i table) table))))
 ;; assuming 5..34 are set later

edited Jul 13 '15 at 07:48

answered Jul 12 '15 at 18:34

npostavs

9,033
1
21
53

1

I'm not sure if this can happen in OP's case, but in general, consider the situation when `lo + inc = some key in the hash-table`, in that case you'd overwrite it, but it is also possible that at the same time `lo + inc < hi`, in which case you are meant to keep it. (This is a famous problem with `memmove`, one that started a flame war between Linux Kernel devs and GCC devs). – wvxvw Jul 12 '15 at 21:47
@wvxvw: oops, very good point, and I believe it *does* apply to OP's case (suppose `/usr/lib` contains only 1 file). Updated to handle this. – npostavs Jul 13 '15 at 07:49

lawlist · Answer 3 · 2015-07-12T20:16:02.467

(let* ((current-line (line-number-at-pos))
       (increment 35)
       (copied-line-to-node-table (copy-hash-table speedbar-line-to-node-table))
       (copied-node-to-line-table (copy-hash-table speedbar-node-to-line-table)))
  (maphash
    (lambda (line filename)
      (when (> line current-line)
        (puthash (+ line increment) filename speedbar-line-to-node-table)))
    copied-line-to-node-table)
  (maphash
    (lambda (filename line)
      (when (> line current-line)
        (puthash filename (+ line increment) speedbar-node-to-line-table)))
    copied-node-to-line-table))

How to increment several numeric keys of a hash-table

3 Answers3